3. Цепи Маркова
Литература. [8], гл. 8, § 1—3, задачи 1—6, 8, 9.
Цепью Маркова называют последовательность испытаний, в каждом из которых система принимает одно из k состояний, образующих полную группу, причем условная вероятность Pij(s) того, что в s-м испытании система будет находиться в состоянии j, при условии, что в (s—1)-м испытании она находилась в состоянии i, не зависит от результатов остальных, ранее произведенных испытаний.
Однородной называют цепь Маркова, если условная вероятность pij(s) появления событий А, в s-м испытании при условии, что в предшествующем (s—1)-м испытании наступило событие At, не зависит от номера испытания (или, что то же, от времени). Поэтому вместо pij(s) пишут просто рij.
Вероятностью перехода (или переходной вероятностью) pij называют условную вероятность того, что из состояния i (в котором система оказалась в результате некоторого испытания, безразлично с каким номером) в итоге следующего испытания система перейдет в состояние j. Таким образом, в обозначении рij; первый индекс указывает номер предшествующего, а второй — номер последующего состояния. Например, р11 — вероятность «перехода» из первого состояния в первое; p23 — вероятность перехода из второго состояния в третье.
Пусть число всех возможных состояний конечно и равно k.
Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:
В каждой строке матрицы помещены вероятности событий (перехода системы из состояния i в состояние j), которые образуют полную группу, поэтому сумма вероятностей этих событий равна единице:
Обозначим через pij(n) вероятность того, что в результате n шагов (испытаний) система перейдет из состояния i в состояние j. Например, р25(10)—вероятность перехода за 10 шагов из второго состояния в пятое. Отметим, что при n=1 получаем переходные вероятности pij(1)=pij.
Поставим задачу: зная переходные вероятности рij, найти вероятности pij(n) перехода системы из состояния i в состояние j за n шагов. Для этого введем промежуточное (между i и j) состояние r. Другими словами, будем считать, что из первоначального состояния i за m шагов система перейдет в промежуточное состояние r с вероятностью pij(m), после чего за оставшиеся n—м шагов из промежуточного состояния r она перейдет в конечное состояние j с вероятностью рij(n—m). По формуле полной вероятности получаем
Эту формулу называют равенством Маркова.
Покажем, что, зная все переходные вероятности pij=pij(1), т. е. зная матрицу Р1 перехода из состояния в состояние за один шаг, можно найти вероятности рij(2) перехода из состояния в состояние за два шага, а следовательно, и саму матрицу перехода Р2; по известной матрице Р2 можно найти матрицу Р3 перехода из одного состояния в другое состояние за три шага и т. д. Действительно, полагая n=2, m=1 в равенстве Маркова, получим
или
С помощью этой формулы можно найти все вероятности pij(2), а следовательно, и саму матрицу Р2. Так как матричное исчисление ведет к цели быстрее, запишем вытекающее из полученной формулы соотношение в матричной форме:
Полагая n=3, m=2, аналогично получим
В общем случае Рn= Рπ1
Пример 8. Задана матрица перехода
Найти матрицу перехода
Решение.
Воспользуемся формулой
:
Перемножив матрицы, окончательно получим
Вопросы для самопроверки
Дайте определение цепи Маркова и сформулируйте ее основные свойства.
Что называется переходной вероятностью (вероятностью перехода)?
Что называется стационарным распределением?
Сформулируйте теорему о предельных вероятностях.