Определение. Однородной называют цепь Маркова, если условная вероятность (переход из состояния в состоянии) не зависит от номера испытания. Поэтому вместо пишут просто.

Пример 1. Случайное блуждание. Пусть на прямой в точке с целочисленной координатой находится материальная частица. В определенные моменты времени частица испытывает толчки. Под действием толчка частица с вероятностью смещается на единицу вправо и с вероятностью - на единицу влево. Ясно, что положение (координата) частицы после толчка зависит от того, где находилась частица после непосредственно предшествующего толчка, и не зависит от того, как она двигалась под действием остальных предшествующих толчков.

Таким образом, случайное блуждание? пример однородной цепи Маркова с дискретным временем.

Переходной вероятностью называют условную вероятность того, что из состояния (в котором система оказалась в результате некоторого испытания, безразлично какого номера) в итоге следующего испытания система перейдет в состояние.

Таким образом, в обозначении первый индекс указывает номер предшествующего, а второй? номер последующего состояния. Например, - вероятность перехода из второго состояния в третье.

Пусть число состояний конечно и равно.

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

Так как в каждой строке матрицы помещены вероятности событий (перехода из одного и того же состояния в любое возможное состояние), которые образуют полную группу, то сумма вероятностей этих событий равна единице. Другими словами, сумма переходных вероятностей каждой строки матрицы перехода равна единице:

Приведем пример матрицы перехода системы, которая может находиться в трех состояниях; переход из состояния в состояние происходит по схеме однородной цепи Маркова; вероятности перехода задаются матрицей:

Здесь видим, что если система находилось в состоянии, то после изменения состояния за один шаг она с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,2 перейдет в состояние, то после перехода она может оказаться в состояниях; перейти же из состояния в она не может. Последняя строка матрицы показывает нам, что из состояния перейти в любое из возможных состояний с одной и той же вероятностью 0,1.

На основе матрицы перехода системы можно построить так называемый граф состояний системы, его еще называют размеченный граф состояний. Это удобно для наглядного представления цепи. Порядок построения граф рассмотрим на примере.

Пример 2. По заданной матрице перехода построить граф состояний.

Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.

На графе не отмечаются вероятности перехода системы из одного состояния в то же самое. При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы.

Цепи Маркова

Введение

§ 1. Цепь Маркова

§ 2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода

§3. Равенство Маркова

§4. Стационарное распределение. Теорема о предельных вероятностях

§5. Доказательство теоремы о предельных вероятностях в цепи Маркова

§6. Области применения цепей Маркова

Заключение

Список использованной литературы

Введение

Тема нашей курсовой работы цепи Маркова. Цепи Маркова названы так в честь выдающегося русского математика, Андрея Андреевича Маркова, который много занимался случайными процессами и внес большой вклад в развитие этой области. В последнее время можно услышать о применении цепей Маркова в самых разных областях: современных веб-технологиях, при анализе литературных текстов или даже при разработке тактики игры футбольной команды. У тех, кто не знает что такое цепи Маркова, может возникнуть ощущение, что это что-то очень сложное и почти недоступное для понимания.

Нет, все как раз наоборот. Цепь Маркова это один из самых простых случаев последовательности случайных событий. Но, несмотря на свою простоту, она часто может быть полезной даже при описании довольно сложных явлений. Цепью Маркова называют такую последовательность случайных событий, в которой вероятность каждого события зависит только от предыдущего, но не зависит от более ранних событий.

Прежде чем углубиться, нужно рассмотреть несколько вспомогательных вопросов, которые общеизвестны, но совершенно необходимы для дальнейшего изложения.

Задача моей курсовой работы – более подробно изучить приложения цепей Маркова, постановку задачи и проблемы Маркова.

§1. Цепь Маркова

Представим, что производится последовательность испытаний.

Определение. Цепью Маркова называют последовательность испытаний, в каждом из которых появляется одно и только одно из

несовместных событий полной группы, причем условная вероятность того, что в -м испытании наступит событие , при условии, что в -м испытании наступило событие , не зависит от результатов предшествующих испытаний.

Например, если последовательность испытаний образует цепь Маркова и полная группа состоит из четырех несовместных событий

, причем известно, что в шестом испытании появилось событие , то условная вероятность того, что в седьмом испытании наступит событие , не зависит от того, какие события появились в первом, втором, …, пятом испытаниях.

Заметим, что независимые испытания являются частным случаем цепи Маркова. Действительно, если испытания независимы, то появление некоторого определенного события в любом испытании не зависит от результатов ранее произведенных испытаний. Отсюда следует, что понятие цепи Маркова является обобщением понятия независимых испытаний.

Часто при изложении теории цепей Маркова придерживаются иной терминология и говорят о некоторой физической системе

, которая в каждый момент времени находится в одном из состояний: , и меняет свое состояние только в отдельные моменты времени то есть система переходит из одного состояния в другое (например из в ). Для цепей Маркова вероятность перейти в какое-либо состояние в момент зависит только от того, в каком состоянии система находилась в момент , и не изменяется от того, что становятся известными ее состояния в более ранние моменты. Так же в частности, после испытания система может остаться в том же состоянии («перейти» из состояния в состояние ).

Для иллюстрации рассмотрим пример.

Пример 1. Представим, что частица, находящаяся на прямой, движется по этой прямой под влиянием случайных толчков, происходящих в моменты

. Частица может находиться в точках с целочисленными координатами: ; в точках и находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью и влево с вероятностью , если только частица не находится у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка между стенками. Здесь мы видим, что этот пример блуждания частицы представляет собой типичную цепь Маркова.

Таким образом, события называют состояниями системы, а испытания – изменениями ее состояний.

Дадим теперь определение цепи Маркова, используя новую терминологию.

Цепью Маркова с дискретным временем называют цепь, изменение состояний которой происходит в определенные фиксированные моменты времени.

Цепью Маркова с непрерывным временем называют цепь, изменение состояний которой происходит в любые случайные возможные моменты времени.

§2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода

Определение. Однородной называют цепь Маркова, если условная вероятность

(переход из состояния в состоянии ) не зависит от номера испытания. Поэтому вместо пишут просто .

Пример 1. Случайное блуждание. Пусть на прямой

в точке с целочисленной координатой находится материальная частица. В определенные моменты времени частица испытывает толчки. Под действием толчка частица с вероятностью смещается на единицу вправо и с вероятностью – на единицу влево. Ясно, что положение (координата) частицы после толчка зависит от того, где находилась частица после непосредственно предшествующего толчка, и не зависит от того, как она двигалась под действием остальных предшествующих толчков.

Таким образом, случайное блуждание − пример однородной цепи Маркова с дискретным временем.

1 июня 2016 в 16:31

Разработка класса для работы с цепями Маркова

• C++ ,
• Алгоритмы

Сегодня я хотел бы поведать вам о написании класса для упрощения работы с цепями Маркова.

Прошу под кат.

Начальные знания:

Представление графов в форме матрицы смежности, знание основных понятий о графах. Знание C++ для практической части.

Теория

Це́пь Ма́ркова - последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего).

Если говорить простыми словами, то Цепь Маркова - это взвешенный граф. В его вершинах находятся события, а в качестве веса ребра, соединяющего вершины A и B - вероятность того, что после события A последует событие B.

О применении цепей Маркова написано довольно много статей, мы же продолжим разработку класса.

Приведу пример цепи Маркова:

В дальнейшем мы будем рассматривать в качестве примера эту схему.

Очевидно, что если из вершины A есть только одно исходящее ребро, то его вес будет равен 1.

Обозначения

В вершинах у нас находятся события (от A, B, C, D, E...). На ребрах вероятность того, что после i-го события будет событие j > i. Для условности и удобства я пронумеровал вершины (№1, №2 и т.д).

Матрицей будем называть матрицу смежности ориентированного взвешенного графа, которым изображаем цепь Маркова. (об этом далее). В данном частном случае эта матрица называется также матрицей переходных вероятностей или просто матрицей перехода.

Матричное представление цепи Маркова

Представлять цепи Маркова мы будем при помощи матрицы, именно той матрицы смежности, которой представляем графы.

Напомню:

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) - это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Подробнее о матрицах смежности - в курс дискретной математики.

В нашем случае матрица будет иметь размер 10x10, напишем ее:

0 50 0 0 0 0 50 0 0 0
0 0 80 20 0 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 0 100 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 70 30 0
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 100 0 0 0 0

Идея

Посмотрите внимательнее на нашу матрицу. В каждой строке у нас есть ненулевые значения в тех столбцах, чей номер совпадает с последующим событием, а само ненулевое значение - вероятность, что это событие наступит.

Таким образом, мы имеем значения вероятности наступления события с номером, равным номеру столбца после события с номером, равным строки .

Те кто знают теорию вероятностей могли догадаться, что каждая строка - это функция распределения вероятностей.

Алгоритм обхода цепи Маркова

1) инициализируем начальную позицию k нулевой вершиной.
2) Если вершина не конечная, то генерируем число m от 0...n-1 на основе распределения вероятности в строке k матрицы, где n - число вершин, а m - номер следующего события (!). Иначе выходим
3) Номер текующей позиции k приравниваем к номеру сгенерированной вершине
4) На шаг 2

Замечание: вершина конечная если распределение вероятностей нулевое (см. 6-ю строку в матрице).

Довольно изящный алгоритм, так ведь?

Реализация

В эту статью я хочу отдельно вынести код реализации описанного обхода. Инициализация и заполнение цепи Маркова не несут особого интереса (полный код см. в конце).

Реализация алгоритма обхода

template Element *Markov::Next(int StartElement = -1) { if (Markov::Initiated) // если матрица смежности создана { if (StartElement == -1) // если стартовый элемент по умолчанию StartElement = Markov::Current; // то продолжаем (в конструкторе Current = 0) std::random_device rd; std::mt19937 gen(rd()); std::discrete_distribution<> dicr_distr(Markov::AdjacencyMatrix.at(Current).begin(), Markov::AdjacencyMatrix.at(Current).end()); // инициализируем контейнер для генерации числа на основе распределения вероятности int next = dicr_distr(gen); // генерируем следующую вершину if (next == Markov::size()) // тонкости работы генератора, если распределение вероятностей нулевое, то он возвращает количество элементов return NULL; Markov::Current = next; // меняем текущую вершину return &(Markov::elems.at(next)); // возвращаем значение в вершине } return NULL; }

Данный алгоритм выглядит особенно просто благодаря особенностям контейнера discrete_distribution . На словах описать, как работает этот контейнер довольно сложно, поэтому возьмем в пример 0-ю строку нашей матрицы:

0 50 0 0 0 0 50 0 0 0

В результате работы генератора он вернет либо 1, либо 6 с вероятностями в 0.5 для каждой. То есть возвращает номер столбца (что эквивалентно номеру вершины в цепи) куда следует продолжить движение дальше.

Пример программы, которая использует класс:

Реализация программы, которая делает обход цепи Маркова из примера

#include #include "Markov.h" #include #include using namespace std; int main() { Markov chain; ofstream outs; outs.open("out.txt"); ifstream ins; ins.open("matrix.txt"); int num; double Prob = 0; (ins >> num).get(); // количество вершин string str; for (int i = 0; i < num; i++) { getline(ins, str); chain.AddElement(str); // добавляем вершину } if (chain.InitAdjacency()) // инициализируем матрицу нулями { for (int i = 0; i < chain.size(); i++) { for (int j = 0; j < chain.size(); j++) { (ins >> Prob).get(); if (!chain.PushAdjacency(i, j, Prob)) // вводим матрицу { cerr << "Adjacency matrix write error" << endl; } } } outs << chain.At(0) << " "; // выводим 0-ю вершину for (int i = 0; i < 20 * chain.size() - 1; i++) // генерируем 20 цепочек { string *str = chain.Next(); if (str != NULL) // если предыдущая не конечная outs << (*str).c_str() << " "; // выводим значение вершины else { outs << std::endl; // если конечная, то начинаем с начала chain.Current = 0; outs << chain.At(0) << " "; } } chain.UninitAdjacency(); // понятно } else cerr << "Can not initialize Adjacency matrix" << endl;; ins.close(); outs.close(); cin.get(); return 0; }

Пример вывода, который генерирует программа:

Однородной называют цепь Маркова, для которой условная вероятностьперехода из состоянияв состояниене зависит от номера испытания. Для однородных цепей вместо
используют обозначение
.

Примером однородной цепи Маркова могут служить случайные блуждания. Пусть на прямой Oxв точке с целочисленной координатойx=nнаходится материальная частица. В определенные моменты времени
частица скачкообразно меняет свое положение (например, с вероятностьюpможет сместиться вправо и с вероятностью 1 –p– влево). Очевидно, координата частицы после скачка зависит от того, где находилась частица после непосредственно предшествующего скачка, и не зависит от того, как она двигалась в предшествующие моменты времени.

В дальнейшем ограничимся рассмотрением конечных однородных цепей Маркова.

Переходные вероятности. Матрица перехода.

Переходной вероятностью
называют условную вероятность того, что из состоянияв итоге следующего испытания система перейдет в состояние. Таким образом, индексотносится к предшествующему, а- к последующему состоянию.

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

, где представляют вероятности перехода за один шаг.

Отметим некоторые особенности матрицы перехода.

Равенство Маркова

Обозначим через
вероятность того, что в результатеnшагов (испытаний) система перейдет из состоянияв состояние. Например,
- вероятность перехода за 10 шагов из третьего состояния в шестое. Отметим, что приn= 1 эта вероятность сводится просто к переходной вероятности
.

Возникает вопрос, как, зная переходные вероятности
, найти вероятности перехода состоянияв состояниезаnшагов. С этой целью вводится в рассмотрение промежуточное (междуи) состояниеr. Другими словами, полагают, что из первоначального состояниязаmшагов система перейдет в промежуточное состояниеrс вероятностью
, после чего за оставшиесяn–mшагов из промежуточного состоянияrона перейдет в конечное состояниес вероятностью
. Используя формулу полной вероятности, можно показать, что справедлива формула

Эту формулу называют равенством Маркова .

Зная все переходные вероятности
, т.е. зная матрицу переходаиз состояния в состояние за один шаг, можно найти вероятности
перехода из состояние в состояние за два шага, а значит, и саму матрицу перехода, далее – по известной матрице- найтии т.д.

Действительно, полагая в равенстве Маркова n= 2,m= 1 получим

или
. В матричном виде это можно записать как
.

Полагая n=3,m=2, получим
. В общем случае справедливо соотношение
.

Пример . Пусть матрица переходаравна

Требуется найти матрицу перехода
.

Умножая матрицу саму на себя, получим
.

Для практических применений чрезвычайно важным является вопрос о расчете вероятности нахождения системы в том или ином состоянии в конкретный момент времени. Решение этого вопроса требует знания начальных условий, т.е. вероятностей нахождения системы в определенных состояниях в начальный момент времени. Начальным распределением вероятностей марковской цепи называется распределение вероятностей состояний в начале процесса.

Здесь через
обозначена вероятность нахождения системы в состояниив начальный момент времени. В частном случае, если начальное состояние системы в точности известно (например
), то начальная вероятность
, а все остальные равны нулю.

Если для однородной цепи Маркова заданы начальное распределение вероятностей и матрица перехода, то вероятности состояний системы на n-м шаге
вычисляются по рекуррентной формуле

.

Для иллюстрации приведем простой пример. Рассмотрим процесс функционирования некоторой системы (например, прибора). Пусть прибор в течение одних суток может находиться в одном из двух состояний – исправном () и неисправном (). В результате массовых наблюдений за работой прибора составлена следующая матрица перехода
,

где - вероятность того, что прибор останется в исправном состоянии;

- вероятность перехода прибора из исправного в неисправное состояние;

- вероятность перехода прибора из неисправного в исправное состояние;

- вероятность того, что прибор останется в состоянии "неисправен".

Пусть вектор начальных вероятностей состояний прибора задан соотношением

, т.е.
(в начальный момент прибор был неисправен). Требуется определить вероятности состояния прибора через трое суток.

Решение : Используя матрицу перехода, определим вероятности состояний после первого шага (после первых суток):

Вероятности состояний после второго шага (вторых суток) равны

Наконец, вероятности состояний после третьего шага (третьих суток) равны

Таким образом, вероятность того, что прибор будет находиться в исправном состоянии равна 0,819, и того, что в неисправном – соответственно 0,181.

Все возможные состояния системы в однородной цепи Маркова, а - определяющая эту цепь стохастическая матрица, составленная из переходных вероятностей (см. стр. 381).

Обозначим через вероятность нахождения системы в состоянии в момент времени если известно, что в момент времени система находилась в состоянии (,). Очевидно, . Пользуясь теоремами о сложении и умножении вероятностей, мы легко найдем:

или в матричной записи

Отсюда, давая последовательно значения , получим важную формулу

Если существуют пределы

или в матричной записи

то величины называются предельными или финальными переходными вероятностями.

Для выяснения, в каких случаях существуют предельные переходные вероятности, и для вывода соответствующих формул введем следующую терминологию.

Мы будем стохастическую матрицу и соответствующую ой однородную цепь Маркова называть правильной, если у матрицы нет характеристических чисел, отличных от единицы и равных по модулю единице, и регулярной, если дополнительно единица является простым корнем характеристического уравнения матрицы .

Правильная матрица характеризуется том, что в ее нормальной форме (69) (стр. 373) матрицы являются примитивными. Для регулярной матрицы дополнительно .

Кроме того, однородная цепь Маркова называется неразложимой, разложимой, ациклической, циклической, если для этой цепи стохастическая матрица является соответственно неразложимой, разложимой, примитивной, импримитивной.

Поскольку примитивная стохастическая матрица является частным видом правильной матрицы, постольку ациклическая цепь Маркова является частным видом правильной цепи.

Мы покажем, что предельные переходные вероятности существуют только у правильных однородных цепей Маркова.

Действительно, пусть - минимальный многочлен правильной матрицы . Тогда

Согласно теореме 10 можно принять, что

На основании формулы (24) гл. V (стр. 113)

(96)

где - приведенная присоединенная матрица и

Если - правильная матрица, то

и потому в правой части формулы (96) все слагаемые, кроме первого, при стремится к нулю. Поэтому для правильной матрицы существует матрица , составленная из предельных переходных вероятностей, и

Обратное положение очевидно. Если существует продел

то матрица не может иметь характеристического числа , для которого , а , так как тогда не существовал бы предел [Этот же предел должен существовать в силу существования предела (97").]

Мы доказали, что для правильной (и только для правильной) однородной цепи Маркова существует матрица . Эта матрица определяется формулой (97).

Покажем, как можно выразить матрицу через характеристический многочлен

и присоединенную матрицу .

Из тождества

в силу (95), (95") и (98) вытекает:

Поэтому формулу (97) можно заменить формулой

(97)

Для регулярной цепи Маркова, поскольку она является частным видом правильной цепи, матрица существует и определяется любой из формул (97), (97"). В этом случае и формула (97") имеет вид

2. Рассмотрим правильную цепь общего типа (нерегулярную). Соответствующую матрицу запишем в нормальной форме

(100)

где - примитивные стохастические матрицы, а у неразложимых матриц максимальные характеристические числа . Полагая

,

запишем в виде

(101)

Но , поскольку все характеристические числа матрицы по модулю меньше единицы. Поэтому

(102)

Поскольку - примитивные стохастические матрицы, то матрицы согласно формулам (99) и (35) (стр. 362) положительны

и в каждом столбце любой из этих матриц все элементы равны между собой:

.

Заметим, что нормальному виду (100) стохастической матрицы соответствует разбиение состояний системы на группы:

Каждой группе в (104) соответствует своя группа рядов в (101). По терминологии Л. Н. Колмогорова состояния системы, входящие в , называются существенными, а состояния, входящие в остальные группы - несущественными.

Из вида (101) матрицы следует, что при любом коночном числе шагов (от момента к моменту ) возможен только переход системы а) из существенного состояния в существенное состояние той же группы, б) из несущественного состояния в существенное состояние и в) из несущественного состояния в несущественное состояние той же или предшествующей группы.

Из вида (102) матрицы следует, что в продело при переход возможен только из любого состояния в существенное состояние, т. е. вероятность перехода в любое несущественное состояние при числе шагов стремится к нулю. Поэтому существенные состояния иногда называются и предельными состояниями.

3. Из формулы (97) следует:

.

Отсюда видно, что каждый столбец матрицы является собственным вектором стохастической матрицы для характеристического числа .

Для регулярной матрицы число 1 является простым корнем характеристического уравнения и этому числу соответствует только один (с точностью до скалярного множителя) собственный вектор матрицы . Поэтому в любом -м столбце матрицы все элементы равны одному и тому же неотрицательному числу :

Таким образом, в регулярной цепи предельные переходные вероятности но зависят от начального состояния.

Обратно, если в некоторой правильной однородной цепи Маркова продельные переходные вероятности не зависят от начального состояния, т. е. имеют место формулы (104), то в схеме (102) для матрицы обязательно . Но тогда и цепь является регулярной.

Для ациклической цепи, которая является частным случаем регулярной цепи, - примитивная матрица. Поэтому при некотором (см. теорему 8 на стр. 377). Но тогда и .

Обратно, из следует, что при некотором , а это по теореме 8 означает примитивность матрицы и, следовательно, ацикличность данной однородной цепи Маркова.

Полученные результаты мы сформулируем в виде следующей теоремы:

Теорема 11. 1 .Для того чтобы в однородной цепа Маркова существовали все предельные переходные вероятности, необходимо и достаточно, чтобы цепь была правильной. В этом случае матрица , составленная из предельных переходных вероятностей, определяется формулой (95) или (98).

2. Для того чтобы в правильной однородной цепи Маркова предельные переходные вероятности не зависели от начального состояния, необходимо и достаточно, чтобы цепь была регулярной. В этом случае матрица определяется формулой (99).

3. Для того чтобы в правильной однородной цепи Маркова все предельные переходные вероятности были отличны от нуля, необходимо и достаточно, чтобы цепь была ациклической.

4. Введем в рассмотрение столбцы из абсолютных вероятностей

(105)

где - вероятность нахождения системы в момент в состоянии (,). Пользуясь теоремами сложения и умножения вероятностей, найдем:

(,),

или в матричной записи

где - транспонированная матрица для матрицы .

Все абсолютные вероятности (105) определяются из формулы (106), если известны начальные вероятности и матрица переходных вероятностей

Введем в рассмотрение предельные абсолютные вероятности

Переходя в обоих частях равенства (106) к пределу при , получим:

Заметим, что существование матрицы предельных переходных вероятностей влечет существование предельных абсолютных вероятностей при любых начальных вероятностях и наоборот.

Из формулы (107) и из вида (102) матрицы вытекает, что предельные абсолютные вероятности, соответствующие несущественным состояниям, равны нулю.

Умножая обе части матричного равенства

справа на , мы в силу (107) получим:

т. е. столбец предельных абсолютных вероятностей является собственным вектором матрицы для характеристического числа .

Если данная цепь Маркова регулярна, то является простым корнем характеристического уравнения матрицы . В этом случае столбец предельных абсолютных вероятностей однозначно определяется из (108) (поскольку и ).

Пусть дана регулярная цепь Маркова. Тогда из (104) и из (107) следует:

(109)

В этом случае предельные абсолютные вероятности не зависят от начальных вероятностей .

Обратно, может не зависеть от при наличии формулы (107) тогда и только тогда, когда все строки матрицы одинаковы, т. е.

,

и потому (согласно теореме 11) - регулярная матрица.

Если - примитивная матрица, то , а отсюда в силу (109)

Наоборот, если все и не зависят от начальных вероятностен, то в каждом столбце матрицы все элементы одинаковы и согласно (109) , а это по теореме 11 означает, что - примитивная матрица, т. е. данная цепь ациклична.

Из изложенного вытекает, что теорему 11 можно сформулировать так:

Теорема 11". 1. Для того чтобы в однородной цепи Маркова существовали все предельные абсолютные вероятности при любых начальных вероятностях, необходимо и достаточно, чтобы цепь была правильной.

2. Для того чтобы в однородной цепи Маркова существовали предельные абсолютные вероятности при любых начальных вероятностях и не зависели от этих начальных вероятностей, необходимо и достаточно, чтобы цепь была регулярной.

3. Для того чтобы в однородной цепи Маркова при любых начальных вероятностях существовали положительные предельные абсолютные вероятности и эти предельные вероятности не зависели от начальных, необходимо и достаточно, чтобы цепь была ациклической.

5. Рассмотрим теперь однородную цепь Маркова общего типа с матрицей переходных вероятностей .

Возьмем нормальную форму (69) матрицы и обозначим через индексы импримитивности матриц в (69). Пусть - наименьшее общее кратное целых чисел . Тогда матрица не имеет характеристических чисел, равных по модулю единице, но отличных от единицы, т. е. - правильная матрица; при этом - наименьший показатель, при котором - правильная матрица. Число назовем периодом данной однородной цепи Маркова и.. Обратно, если и , определяемые формулами (110) и (110").

Средние предельные абсолютные вероятности, соответствующие несущественным состояниям, всегда равны нулю.

Если в нормальной форме матрицы число (и только в этом случае), средние предельные абсолютные вероятности не зависят от начальных вероятностей и однозначно определяются из уравнения (111).

Предыдущая статья: Чему равна скорость света Следующая статья: Гармонические колебания Физика формула частоты колебаний