Уравнение Маркова

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

Введем следующие обозначения для безусловных (абсолютных) условных вероятностей

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

Очевидно, что введенные вероятности неотрицательны и удовлетворяют условию нормировки:

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

На основании теоремы полной вероятности для безусловной вероятности , можем написать

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

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

Это функциональное уравнение для дискретных цепей с конечным числом состояний было установлено Марковым и поэтому носит название уравнении Маркова. Оно является частным случаем общего уравнения Колмогорова — Чэпмена, которое справедливо и для цепей с бесконечным числом .

Если ввести квадратную матрицу , элементами которой являются вероятности перехода , и матрицу-строку с элементами то в матричной форме формулы (15) и (16) можно записать так (см. Приложение 1):

Квадратная матрица , элементы которой неотрицательны и сумма элементов, стоящих в каждой строке (или столбце), равна единице, называется стохастической матрицей.

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

Здесь — матрицы-столбцы.

Расписывая последовательно формулу (18), имеем

Отсюда видно, что для определения матрицы при всех достаточно знать последовательность матриц одношаговых вероятностей перехода

Полагая в уравнении (18) , имеем

где - матрица-строка вероятностей начального состояния.

С учетом соотношений (22), (20) и (6) приходим к заключению, что полное вероятностное описание простой цепи Маркова достигается заданием вероятностей начального состояния и последовательности матриц вероятностей одношаговых переходов (21).

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

Поэтому для однородной цепи Маркова матрица вероятностей перехода должна иметь вид

При этом получаем следующую матричную форму записи уравнения Маркова (18)

Рассмотрим подробнее простые однородные цепи Маркова. Применительно к однородной цепи введем обозначение матрицы перехода за один шаг и обозначим одношаговые вероятности перехода этой матрицы просто через :

Следовательно,

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

Между матрицами с разными аргументами существует простое соотношение. Так, полагая в (25) , имеем

Полагая затем , и т.д, окончательно получаем

Итак, для простой однородной цепи Маркова матрица вероятностей перехода за шагов равна степени матрицы одношаговых вероятностей перехода.

Если в формуле (17) положить и учесть свойство однородной цепи (24), то можем написать

где — матрица-строка абсолютныхгвероятностей состояний на шаге. В частности, при формула (30) принимает вид

Здесь — матрица-строка вероятностей начального состояния (при )

Формулы (30) и (29) показывают, что исчерпывающее вероятностное описание простой однородной цепи Маркова дается указанием вероятностей начального состояния (при ) и матрицы одношаговых вероятностей перехода (27).

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

В противном случае цепь называется нестационарной. Для однородной стационарной цепи

Полагая в формуле (30) и учитывая равенство (33), для однородной стационарной цепи получаем формулу

Это матричное уравнение эквивалентно следующей системе К линейных алгебраических уравнений

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

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

начиная с некоторого , существуют предельные (финальные) вероятности

Эти финальные вероятности не зависят от начального распределения .

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

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

Эти финальные вероятности образуют стационарное распределение .

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

Как видно из (35) и (38), для определения неизвестных финальных вероятностей имеется линейное уравнение. Однако первые уравнений являются линейно-зависимыми Действительно, суммируя обе части всех равенств (35) и учитывая соотношение (14), придем к тождеству.

Поэтому K финальных веротностей следует определять из уравнения (35) и уравнения (38).

Теория цепей Маркова разработана достаточно полно и хорошо изложена во многих книгах [4—6, 10—12]. Обычно приводится развернутая классификация цепей, основанная на классификация матриц переходных вероятностей , характеризующих эволюцию процесса во времени. Здесь мы укажем лишь основные определения состояний марковской цепи.

Рис. 2.1. Граф цепи Маркова с пятью состояниями.

Рис. 2.2. Цепь маркова с двумя состояниями.

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

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

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

Цели Маркова можно поставить в соответствие так называемый ориентированный граф [18], позволяющий наглядно представить возможный характер развития процесса. Вершины графа определяются состояниями цепи. Каждой дуге из состояния в состояние ставится в соответствие число , если (т. е. когда возможен одношаговый переход из ).

В качестве примера на рис. 2.1 показан граф цепи Маркова с пятью состояниями. Если текущее состояние системы есть , то она переходит в состояния или остается в , с вероятностями 0,2; 0,3 и 0.5 соответственно. Аналогично интерпретируются другие дуги. Из графа следует, что состояние является невозвратным, а — поглощающим.