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

Определение. Случайный процесс, протекающий в системе S с дискретными состояниями s ₁, s ₂, …, s _i, …, называется марковским, если для любого момента времени t ₀ вероятность каждого из состояний системы в будущем (при t > t ₀), зависит только от ее состояния в настоящем (при t = t ₀), и не зависит от того, как система пришла в это состояние, т.е. не зависит от ее поведения в прошлом (при t < t ₀).

 

Примеры. 1) Система S – счетчик в такси. Состояние системы в момент t характеризуется количеством километров, пройденных автомобилем до данного момента. Пусть в момент t₀ счетчик показывает S₀. Вероятность того, что в момент t > t₀ счетчик покажет то или иное количество километров (точнее, соответствующее количество денег) S₁, зависит только от S₀, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t₀.

2) Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы. Система S – группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившимися на доске в момент t₀. Вероятность того, что в момент t > t₀ перевес будет на стороне одного из игроков, зависит в первую очередь от того, в каком состоянии система находится в данный момент t₀, а не от того, когда и в какой последовательности исчезли фигуры с доски до момента t₀.

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

 

Пусть имеется система S с дискретными состояниями s ₁, s ₂, …, s _n (для простоты ограничимся конечным числом состояний). Предположим, что случайные переходы системы из состояния в состояние могут происходить только в определенные моменты времени t ₀, t ₁, t ₃…. Сам процесс представляет собой случайное блуждание системы S по состояниям: после первого шага система может оказаться в одном (и только одном) из своих возможных состояний s ₁⁽¹⁾, s ₂⁽¹⁾, …, s _n⁽¹⁾, на втором шаге - s ₁⁽²⁾, s ₂⁽²⁾, …, s _n⁽²⁾, и т.д.

Определение. Марковским случайным процессом с дискретными состояниями и дискретным временем или цепью Маркова называется марковский процесс, в котором его возможные состояния можно заранее перечислить, а переход из состояния в состояние происходит мгновенно (скачком), но только в определенные моменты времени t0, t1, t2, …, называемые шагами процесса.

Из определения цепи Маркова следует, что для нее вероятности перехода системы S в состояние s_j на (k +1)–м шаге зависит только от того, в каком состоянии s_i находилась система на предыдущем, k –м шаге, и не зависит от того, как она вела себя до этого. Основной задачей исследования цепей Маркова является нахождение безусловных вероятностей нахождения системы S на любом (k –м) шаге в состоянии s_i; обозначим эту вероятность p_i (k):

p_i (k) = P { S (k) = s_i }, i = 1,2,…, n; k = 0,1,…

Для нахождения этих вероятностей необходимо знать условные вероятности перехода системы S в состояние s_j на k –м шаге, если известно, что на предыдущем (k- 1)–м шаге на была в состоянии s_i. Обозначим эту вероятность

p_ij (k) = P { S (k) = s_j | S (k- 1) = s_i }, i,j = 1,2,…, n.

Вероятности p_ij (k) называются переходными вероятностями марковской цепи на k –м шаге. Вероятность p_ii (k) есть вероятность того, что на k –м шаге система задержится (останется) в состоянии s_i.

Если переходные вероятности p_ij (k) не зависят от номера шага процесса k: p_ij (k) = p_ij, то такая цепь Маркова называется однородной.

Переходные вероятности можно записать в виде квадратной матрицы размерности n x n:

(k = 0,1,2,…) (1)

На главной диагонали матрицы переходных состояний стоят вероятности задержки системы в данном состоянии s_j на k –м шаге - p ₁₁(k), p ₂₂(k),…, p_nn (k).

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

(2)

Естественно, все элементы такой матрицы отвечают условию 0 ≤ p_ij (k) ≤ 1.

В силу условия (2) можно в матрице (1) не задавать вероятности задержки, а получать их как дополнения до единицы суммы всех остальных членов строки:

p_ii (k) =

Для того, чтобы найти безусловные вероятности p_i (k), недостаточно знать матрицу переходных вероятностей (1); нужно еще знать начальное распределение вероятностей, т.е. вероятности состояний p_i (0), соответствующее началу процесса - моменту времени t ₀ = 0: p ₁(0), p ₂(0), …, p_n (0), в сумме образующие единицу

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

.

 

При нахождении вероятностей состояний марковской цепи на k -том шаге p_i (k) (k = 1,2,…) удобно бывает пользоваться так называемым размеченным графом системы S, где возле каждой стрелки, ведущей из состояния s_i в состояние s_j, проставлена переходная вероятность p_ij; вероятности задержки на размеченном графе не проставляются, а просто получаются дополнением до единицы суммы вероятностей, стоящих у всех стрелок, ведущих из данного состояния s_i.

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

 

Для этого графа вероятности задержек равны:

р ₁₁ = 1 – р ₁₂, р ₂₂ = 1 – (р ₁₂ + р ₂₄), р ₃₃ = 1 – р ₃₁, р ₄₄ = 1 – (р ₄₃ + р ₄₅), р ₅₅ = 1 – р ₅₁.

 

Если состояние s_i является поглощающим (на графе из него не идет ни одной стрелки), то вероятность задержки в этом состоянии равна 1.

Теперь покажем, как найти для однородной цепи Маркова безусловную вероятность нахождения системы S на k -том шаге в состоянии s_j (j = 1,2,…, n): p_i (k) = P{ S (k) = s_j }, если задана матрица переходных вероятностей и начальное распределение вероятностей.

Пусть задана однородная цепь Маркова, имеющая матрицу переходных состояний и начальное распределение вероятностей p_i (0) (i = 1,2,…, n), Сделаем гипотезу, состоящую в том, что в начальный момент (k =0) система находилась в состоянии s_i. Вероятность этой гипотезы известна из начальных условий и равна p_i (0) = P { S (0) = s_i }. В предположении, что эта гипотеза имеет место, условная вероятность того, что система S на первом шаге будет в состоянии s_j, равна переходной вероятности p_ij = P { S (1) = s_j | S (0) = s_i }.

По формуле полной вероятности получим

p_j (1) = (j = 1,2,…, n).

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

Опять сделаем гипотезу, состоящую в том, что на первом шаге система находится в состоянии s_i; вероятность этой гипотезы нам уже известна и равна p_j (1) = P { S (1) = s_i }(i = 1,2,…, n). При этой гипотезе условная вероятность того, что система S на втором шаге будет в состоянии s_j, равна

p_ij = P { S (2) = s_j | S (1) = s_i }.

По формуле полной вероятности находим

p_j (2) = (j = 1,2,…, n).

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

p_j (k) = (k = 1,2,…; j = 1,2,…, n).

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

Убедимся в том, что, зная все вероятности перехода р_ij = р_{i j}(1), т.е. матрицу перехода Р ₁ из состояния в состояние за один шаг, можно найти вероятность р_ij (2), т.е. матрицу Р ₂ перехода из состояния в состояние за два шага. А зная матрицу Р ₂ – найти матрицу Р ₃ перехода из состояния в состояние за 3 шага и т.д.

Действительно, полагая в равенстве Маркова k = 2

р_j (2) = = .

Полученное равенство означает, что Р ₂ = Р ₁ ∙ Р ₁ = .

Полагая k = 3, аналогично получаем Р ₃ = Р ₁ ∙ Р ₂ = Р ₁ ∙ = , а в общем случае

Р _n = .

 

Теперь сформулируем теорему, позволяющую вычислить вероятности состояний системы от любого k -го до (k +1)-го шага, зная начальное распределение вероятностей p ₁(0), …, p_n (0) и матрицу переходных вероятностей.

Теорема. Для однородной марковской цепи вектор-строка вероятностей состояний от k -го до (k +1)-го шага равна произведению вектор-строки вероятностей состояний от (k- 1)-го до k -го шага на матрицу переходных вероятностей:

(p ₁(k), …, p_n (k)) = (p ₁(k -1), …, p_n (k -1))∙ Р.

Следствие. Для однородной марковской цепи имеет место следующая формула

(p ₁(k), …, p_n (k)) = (p ₁(0), …, p_n (0))∙ Рⁿ.

 

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

(p ₁(k), …, p_n (k)) = (p ₁(0), …, p_n (0))∙ Р (1)∙…∙ P (k),

где P (k) – матрица переходных вероятностей от k -го до (k +1)-го шага.