Лекция по цепям Маркова (М.Л. Сердобольская) (ПДФ-лекции)

1. КОНЕЧНЫЕ ОДНОРОДНЫЕ ЦЕПИ МАРКОВАРассмотрим последовательность случайных величин ξn , n = 0, 1, . . . , каждая изкоорых распределена дискретно и принимает значения из одного и того же множества {x1 , . . . , xs } с 2 6 s < ∞.1.1. Определение цепи Маркова. Свойства матриц перехода.Определение 1.1. Случайная последовательность ξn , n = 0, 1, 2, . . . , со значениями в множестве {x1 , .

. . , xs } называется однородной цепью Маркова 1 , если ееконечномерные распределения задаются следующим образом:n = 0 : P (ξ0 = xi ) = ai > 0,sXi = 1, . . . , s,ai = 1;(1.1)i=1n > 0 : P (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−1 = xin−1 , ξn = xin ) = ai0 πi0 i1 . .

. πin−1 in , (1.2)где πij – некоторые числа, i, j = 1, . . . , s; здесь значения xi1 , . . . , xin выбраны произвольным образом.Определение 1.2. Значение xi назовём i-м состоянием цепи Маркова. Еслипроизошло событие ξn = xi , то будем говорить, что цепь Маркова на n-м шагепребывала в i-ом состоянии.Равенства (1.1) задают распределение цепи Маркова на первом шаге, или начальное распределение. Видно, что формула (1.1) никак не ограничивает вид этого(дискретного) распределения.Смысл коэффициентов πij в (1.2) раскрывают следующие рассуждения. Дляn = 1, 2 равенства (1.2) принимают видP (ξ0 = xi , ξ1 = xj ) = ai πij ,P (ξ0 = xi , ξ1 = xj , ξ2 = xk ) = ai πij πjk ,отсюда следует, чтоπjk =P (ξ0 = xi , ξ1 = xj , ξ2 = xk )P (ξ0 = xi , ξ1 = x2 , ξ2 = xk )==ai πijP (ξ0 = xi , ξ1 2 = xj )(1.3)= P (ξ2 = xk | ξ1 = xj , ξ0 = xi ).C другой стороны, по определению условной вероятностиP (ξ2 = xk , ξ1 2 = xj )P (ξ2 = xk | ξ1 = xj ) ==P (ξ1 = xj )sPP (ξ0 = xi , ξ1 = xj , ξ2 = xk )i=1sP,P (ξ0 = xi , ξ1 = xj )i=1где мы разложили события {ξ2 = xk , ξ1 = xj } и {ξ1 = xj } по полной группе попарно несовместных событий {ξ0 = xi }, i = 1, .

. . , s. Подставляя определение (1.2),получаемsPai πij πjki=1P (ξ2 = xk | ξ1 = xj ) = P= πjk .(1.4)sai πiji=11) Смыслтермина «однородность» будет раскрыт далее.1Сравнивая формулы (1.3) и (1.4), приходим к выводу, чтоπjk = P (ξ2 = xk | ξ1 = xj ) = P (ξ2 = xk | ξ1 = xj , ξ0 = xi ).Аналогично, для общих значений n > 3 имеемP (ξ0 = xi1 , ξ1 = xi2 , . .

. , ξn−2 = xin−2 , ξn−1 = xin−1 , ξn = xin )=ai0 πi0 i1 . . . πin−2 in−1P (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−2 = xin−2 , ξn−1 = xin−1 , ξn = xin )==P (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−2 = xin−2 , ξn−1 = xin−1 )πin−1 in == P (ξn = xin | ξn−1 = xin−1 , . . . , ξ0 = xi0 ).C другой стороны, разлагая по состояниям на шагах с номерами 0, 1, . . .

, n − 2,получаемP (ξn = xin | ξn−1 = xin−1 ) ==sPP (ξn = xin , ξn−1 = xin−1 )=P (ξn−1 = xin−1 )P (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−2 = xin−2 , ξn−1 = xin−1 , ξn = xin )(i)=1sP=P (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−2 = xin−2 , ξn−1 = xin−1 )(i)=1=sPai0 πi0 i1 . . . πin−2 in−1 πin−1 in(i)=1= πin−1 in ,sPai0 πi0 i1 . .

. πin−2 in−1(i)=1где суммирование по (i) означает (n − 1)-кратное суммирование по всем индексамi0 , . . . , in−2 , изменяющимся от 1 до s.Таким образом,P (ξn = xin | ξn−1 = xin−1 , . . . , ξ0 = xi0 ) = P (ξn = xin | ξn−1 = xin−1 )(1.5)иπij = P (ξn = xj | ξn−1 = xi ),i, j = 1, . . . , s,n = 1, 2, .

. . .(1.6)Условные вероятности (1.6) образуют матрицу π размера s × s, которая называетсяматрицей перехода за один шаг.Равенство (1.5) часто принимают вместо (1.2) за определение цепи Маркова.Нетрудно доказать, что из (1.5) следует (1.2): в самом деле, из определения условнойвероятности следует, чтоP (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−1 = xin−1 , ξn = xin ) == P (ξn = xin | ξn−1 = xin−1 , . .

. , ξ1 = xi1 , ξ0 = xi0 )×× P (ξn−1 = xin−1 , . . . , ξ1 = xi1 , ξ0 = xi0 ),а из (1.5) мы имеемP (ξn = xin | ξn−1 = xin−1 , . . . , ξ1 = xi1 , ξ0 = xi0 ) = P (ξn = xin | ξn−1 = xin−1 ) = πin−1 i .2Таким образом, мы получаемP (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−1 = xin−1 , ξn = xin ) == πin−1 i P (ξn−1 = xin−1 , . . . , ξ1 = xi1 , ξ0 = xi0 ).Применяя аналогичные рассуждения к P (ξn−1 = xin−1 , . .

. , ξ1 = xi1 , ξ0 = xi0 ), получаемP (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−1 = xin−1 ) == πin−2 in−1 P (ξn−2 = xin−2 , . . . , ξ1 = xi1 , ξ0 = xi0 )и, объединяя две последние формулы, имеемP (ξ0 = xi0 , ξ1 = xi1 , . . . , ξn−1 = xin−1 , ξn = xin ) == πin−1 i πin−2 in−1 P (ξn−2 = xin−2 , . . . , ξ1 = xi1 , ξ0 = xi0 ).Продолжая эту процедуру доP (ξ0 = xi0 , ξ1 = xi1 ) = P (ξ1 = xi1 | ξ0 = xi0 )P (ξ0 = xi0 ) = πi0 i1 ai0 ,в конечном итоге приходим к (1.2).Отметим, что в (1.6) условные вероятности P (ξn = xj | ξn−1 = xi ) определяютсятолько индексами i, j и не зависят от n, т. е.

по сути от момента времени tn . Такое свойство называется однородностью цепи Маркова. Итак, мы рассматриваемоднородные цепи Маркова с конечным числом состояний s.Замечание 1.1. Если случайные ξ0 , ξ1 , . . . , ξn независимы при всех n = 1, 2, . . . ,то условие (1.5), очевидно, выполнено, причёмπij = P (ξn = xj | ξn−1 = xi ) = P (ξn = xj ),i, j = 1, 2, . . . , s,(1.7)и мы видим, что в этом случае элементы матрицы перехода не зависят от первогоиндекса, т.

е. в матрице перехода за один шаг все строки одинаковы (как обычно,считаем, что первый индекс элемента матрицы отвечает номеру строки, а второй —номеру столбца).Замечание 1.2. Условие (1.5) означает, что если фиксированы состояния на начальном и первых n − 1 шагах, то вероятность на n-м шаге находиться в определённом состоянии зависит (как функция от своих аргументов) только от состоянияна предыдущем (n − 1)-м шаге и не зависит от более ранних состояний. При этомданное условие не влечёт статистическую независимость случайной величины ξnот случайных величин ξ1 , . .

. , ξn−2 — все шаги цепи Маркова статистическизависимы.По аналогии с (1.6) определим вероятность перехода за m > 1 шагов(m)πij= P (ξn+m = xj | ξn−1 = xi ),i, j = 1, 2, . . . , s,(1.8)и соответствующую матрицу π (m) перехода за m шагов размера s × s с элементами (1.8). Тогда последнее замечание можно переформулировать так: в общемслучае матрица перехода за m шагов не обязана иметь одинаковые строки.3Докажем несколько утверждений, вытекающих непосредственно из определенияцепи Маркова.1. Очевидно, что, как и любая вероятность, условная вероятность лежит в интервале [0, 1], поэтому(n)0 6 πij 6 1,n = 1, 2, .

. . ,i, j = 1, . . . , s.2. Для любого m = 1, 2, . . . и всех i = 1, . . . , ssX(m)πij=sXP (ξm+nj=1j=1j=1=sXP (ξm+n = xj , ξn = xi )== xj | ξ n = xi ) =P (ξn = xi )1P (ξn = xi )sXP (ξm+n = xj , ξn = xi ) =j=1P (ξn = xi )=1P (ξn = xi )в силу того, что последняя сумма отвечает разложению события {ξm+n = xj } пополной группе событий {ξn = xi }, i = 1, . . .

, s. Последняя цепочка равенств показывает, что сумма элементов в каждой из строк матрицы перехода за m шагов равна 1.Это свойство по сути есть условие нормировки условного распределения случайнойвеличины ξm+n (при условии, что ξn = xi ).Матрица π (n) с неотрицательными элементами, удовлетворяющая условиюsX(n)(1.9)πij = 1,j=1называется стохастической.Используя матрицу перехода за n шагов, мы можем записать, что вероятностьтого, что на (n + 1)-м шаге цепь Маркова окажется в k-м состоянии, равнаP (ξn = xk ) =sXP (ξn = xk | ξ0 = xj )P (ξ0 = xj ) =j=1sX(n)aj πjk ,(1.10)j=1C другой стороны, в силу (1.2)P (ξn = xk ) =s XssXX=···P (ξ0 = xj , ξ1 = xj1 , . . . , ξn−1 = xjn−1 , ξn = xk ) =j=1 j2 =1=sXsXj=1 j1 =1jn−1 =1···sXaj πjj1 . . .

πjn−1 k ,jn−1 =1где мы вновь применили разложение события {ξn = xk } по полной группе событий, образованной всевозможными состояниями цепи Маркова на шагах с номерами0, 1, . . . , n − 1. Сравнивая последнее выражение с (1.10), видим, чтоsXj=1(n)aj πjk=s XsX···sXjn−1 =1j=1 j1 =14aj πjj1 . . . πjn−1 k ,причём это равенство имеет место при любых начальных вероятностях a1 , . . .

, as .Положим ai = 1 и ai′ = 0 при i′ 6= i. Отсюда получим(n)πik =s XsXj1 =1 j2 =1···sXπij1 πj1 j2 . . . πjn−1 k .(1.11)jn−1 =1nВидно, что в правой части мы имеем элемент πikматрицы π n = π . . . π, и мы получаем важнейшее свойство матриц перехода в однородных цепях Маркова.3. Матрица перехода за n шагов есть n-я степень матрицы перехода за один шаг,π (n) = π n(1.12)при любых n = 1, 2, . . .

(для красоты формулы мы положили π = π (1) ).4. C учетом последнего свойства, записав равенства π (n+m) = π n+m = π n · π m ,получаем уравнение(n+m)πij= π (n) π (m) ,(1.13)которое связывает различные матрицы в бесконечном семействе матриц перехода{π (n) }n=1,∞ и представляет собой частный случай знаменитого уравнения Чепмена–Колмогорова.1.2. Эргодичность цепи Маркова. Естественно предположить, что системадолжна «забывать» о своём начальном состоянии в пределе бесконечно большогочисла шагов.

С точки зрения матриц перехода это означает, что переходная вероятность не должна зависеть от начального состояния при n → ∞.Определение 1.3. Если для любых i, j = 1, . . . , s существует предел переходнойвероятности(n)(1.14)pj = lim πij ,n→∞и величина этого предела не зависит от i, то будем говорить, что у цепи Марковасуществуют финальные вероятности.Теорема, в которой формулируется достаточное условие существования финальных вероятностей, называется теоремой Маркова. Предпошлём её доказательствутехническую лемму, справедливую для любых стохастических матриц.Лемма 1.1.

Пусть матрица π с неотрицательными элементами удовлетвоPsряет условию стохастичности, т. е. j=1 πij = 1 для любого i = 1, . . . , s. Рассмотрим две строки матрицы π с фиксированными номерами α и β . ПоложимXS + (α, β) =(παk − πβk ).(1.15)k : παk −πβk >0Имеют место следующие утверждения:1) S + (α, β) = S + (β, α);2) если найдется номер столбца j ∈ {1, 2, . . . , s} такой, что πij > δ > 0 для всехi = 1, 2, . . . , s, тоS + (α, β) 6 1 − δ.(1.16)5Доказательство. Заметим, чтоXS + (β, α) =(πβk − παk ) = −k : πβk −παk >0X(παk − πβk ).k : παk −πβk 60Понятно, что из суммы можно исключить слагаемые, равные нулю, т.

е.XS + (β, α) = −(παk − πβk ).(1.17)k : παk −πβk <0Разобьем множество {1, . . . , s} на два подмножестваK+ = k : παk − πβk > 0 , K− = k : παk − πβk < 0(вариант разбиения, конечно, зависит от α и β). В этих обозначениях (1.15) и (1.17)запишутся какXXS + (α, β) =(παk − πβk ),S + (β, α) = −(παk − πβk ).k∈K+k∈K−Отсюда++S (α, β) − S (β, α) = Xk∈K+sXX (παk − πβk ) = 1 − 1 = 0+(παk − πβk ) =k=1k∈K−в силу стохастичности матрицы π, таким образом, равенство S + (α, β) = S + (β, α)доказано.Далее,1=sXk=1παk =Xπαk +k∈K+следовательно,S + (α, β) =Xπαk ,παk = 1 −Xπαk −k∈K+k∈K−XX(παk − πβk ) = 1 −k∈K+k∈K−Xπαk ,k∈K−Xπβk .(1.18)k∈K+Пусть номер столбца j взят из второго утверждения леммы.

Очевидно, что, каковбы ни был этот номер j ∈ {1, . . . , s}, либо j ∈ K+ , либо j ∈ K− . Если j ∈ K+ , тов силу неотрицательности всех элементов матрицы π имеемXXπβk > πβj > δ,παk > 0.k∈K+Если j ∈ K− , то наоборотXk∈K−παk > παj > δ,Xπβk > 0.k∈K+k∈K−В любом случае в (1.18)Xk∈K−παk +Xπβk > δ.k∈K+Подставляя эту оценку в (1.18), получаем неравенство (1.16).6Перейдем к теореме Маркова.Теорема 1.1. Пусть найдется натуральное число n0 такое, что матрица перехода π (n0 ) за n0 шагов цепи Маркова имеет хотя бы один столбец, не содержащий нулевых элементов. Тогда:(n)1) для любого j = 1, . .