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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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, . .

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций