Дискретные цепи Маркова

Тема № 2 Дискретные цепи Маркова Пусть T   0 или T   , т.е. имеется последовательность случайных величин 0 , 1,..., n ,... , определенных на одном вероятностном пространстве , A, P . Пусть En - множество значений n , тогда E   En - множество состояний цепи n Маркова или фазовое пространство. Определение. Последовательность дискретных случайных величин  , n    n называется цепью Маркова, если при любых n   для всех l1  l2  ...  ln 1   0 и для любых i1, i2 ,..., in , in 1  E имеют место равенства:  P l n 1  in 1 | l  i1,,..., l n 1 1    in 1, l  in  P l n   in 1 | l  in , n 1 n если эти вероятности определены. Величина n – это дискретное время. Запись n  in означает «Цепь Маркова в момент времени n находится в состоянии in » По теореме об умножении вероятностей верно равенство P 0  i0,..., n  in   P0  i0  P1  i1 | 0  i0   P2  i2 | 1  i1, 0  i0 ...P n  in | 0  i0,..., n1  in1    P 0  i0  P 1  i1 | 0  i0 ...P n  in | n 1  in 1  . Назовем величину pij(n )  P n  j | n 1  i  переходной вероятность из i -го состояния в j -е за 1 шаг в момент времени n . Определение. Цепь Маркова называется однородной во времени, если ее переходные вероятности не зависят от n , т. е. pij(n )  pij для всех i, j  E ¸ в любой момент времени n . В дальнейшем мы будем рассматривать однородные цепи Маркова. Определение. Цепь Маркова - конечная, если фазовое пространство E – конечно (в противном случае цепь Маркова счетна). Обозначим  || pij ||NN , где N – мощность фазового пространства E , и назовем ее матрицей переходных вероятностей за 1 шаг. Обозначим через p вектор   p  P 0  i  ; i  E . Вектор p - распределение случайной величины 0 . Назовем вектор p начальным вектором (начальным распределением) цепи Маркова. Набор ( p ,П) полностью определяет однородную цепь Маркова. Обозначим через pij n   P l n  j | l  i  переходную вероятность из i – го состояния в j – е за n шагов. В силу однородности цепи Маркова величина pij n  не зависит от l . Введем матрицу переходных вероятностей за n шагов:  n  || pij n  ||N N . С помощью формулы полной вероятности докажите самостоятельно, что pij n    pik n  1 pkj . k E Это равенство называется уравнением Колмогорова – Чепмена. В матричном виде оно будет выглядеть следующим образом:  n    n  1  . Следовательно,  n   n для всех n   . 1, i  j Определим pij 0   , 0, i  j  1  0    .      1  0  0  EN N Очевидно, что выполняется равенство P n  j    i0 ,i1 ,...,in 1 E  P 0  i0  pi i pi i ...pi Определим вектор p n  P n  j ; j  E 01  12 n 1 j . – распределение цепи Маркова в момент времени n . Очевидно, что выполняется равенство Пример. 1. отрезка 1,N  , pn  p 0n  pn1 . Предположим, что некоторая частица, двигаясь по целочисленным точкам в дискретные моменты времени может совершать скачки влево или вправо на один шаг. Вероятность скачка вправо равна p  0 из любой внутренней точки k  2, N  1 , равна 1 из точки 1 и равна 0 из точки N . Вероятность скачка влево равна q  1  p  0 из любой внутренней точки k  2, N  1 , равна 0 из точки 1 и равна 1 из точки N . Пусть n - точка, характеризующая положение частицы в момент времени n   0 . Легко видеть, что последовательность n , n   0  образует цепь Маркова. Эта цепь называется случайным блужданием с отражающими экранами. В качестве левого и правого отражающих экрана выступают концевые точки отрезка 1 иN. Случайное блуждание с отражающими экранами как цепь Маркова n , n   0  имеет следующую матрицу переходных вероятностей: 1 2 3  N 1 N 1 0 1 0  2 p 0 q  3 0 p 0  0.        N 1 0 0 0  q N 0 0 0  1 2. Изменим свойства экранов в предыдущем примере. Пусть теперь из точки 1 можно произвести скачок вправо с вероятностью  , а с вероятностью 1   можно остаться в точке 1. Из точки N можно произвести скачок влево с вероятностью  , а с вероятностью 1   можно остаться в точке N . Остальные условия оставим без изменения. Последовательность n , n   0  так же образует цепь Маркова с матрицей переходных вероятностей: 1 2 3  N 1 N 1 1  0  2 p 0 q  3 p 0         N 1 0 0  q N 0 0   1 Если 0    1 , то это случайное блуждание с упругими экранами, а если   0 - это случайное блуждание с поглощающими экранами. Классификация состояний цепи Маркова Пусть E1, E 2 ,... - состояния цепи Маркова. Определение. Состояние E j называется несущественным, если найдется состояние Ek и натуральное число m такие, что pjk m   0 , но pkj n   0 при любых n   . В противном случае состояние E j - существенное. Пример. При случайном блуждании с поглощающими экранами состояния 1 и N существенные, а остальные – несущественные. При случайном блуждании с упругими и отражающими экранами все состояния существенны. Определение. Существенные состояния E j и Ek называются сообщающимися, если существуют m, n   такие, что pjk m   0 и pkj n   0 . Пример. При случайном блуждании с упругими и отражающими экранами все состояния существенные и сообщающиеся. Докажите самостоятельно, что отношение сообщаемости является отношением эквивалентности. Обозначим через S 0 класс несущественных состояний данной цепи Маркова. Существенные состояния разбиваются на непересекающиеся подклассы по отношению сообщаемости. Обозначим эти подклассы S 1 , S 2 и т.д. Перенумеруем состояния из фазового пространства так, чтобы первые номера были в S 0 , вторые – в S 1 и т. д. Для конечной цепи Маркова это можно сделать. В матрице переходных вероятностей переставятся строки и столбцы, и она приобретет вид: S 0 S1 S2  S0     S1  . S2        Через  мы обозначили те клетки, в которых могут быть ненулевые элементы. Пример. При случайном блуждании с поглощающими экранами S  2,..., N  1  2, N  1 , S  1 , 1 S  N  . 2 Если в матрице класс переходных вероятностей переставятся строки и столбцы, то она приобретет вид 2 3  N 1 1 N 2 0 q  p 0 3 p 0  0 0        N 1 0 0  0 q 1 0 0  1 0 N 0 0  0 1 Определение. Если какой-либо класс сообщающихся состояний состоит из одного состояния, то оно называется поглощающим состоянием. Пример. При случайном блуждании с поглощающими экранами состояния 1 и N поглощающие. Определение. Во введенных выше обозначениях классы S 1, S 2 ,... называются эргодическими подклассами существенных состояний, S 0 – классом несущественных состояний. Определение. Если все фазовое пространство цепи Маркова составляет один эргодический подкласс сообщающихся состояний, то эта цепь называется неприводимой или неразложимой. Пример. При случайном блуждании с упругими или отражающими экранами цепи Маркова являются неприводимыми. Определение. Существенное состояние E j называется периодическим с периодом d j , если d j - это наибольший общий делитель всех таких натуральных n , что pjj n   0 . 1,N  , в   дискретные моменты времени может совершать скачки вправо на один шаг, если она Пример. Пусть некоторая частица, двигаясь по целочисленным точкам отрезка находилась в точке k  1, N  1 , а из состояния N она совершает скачок в 1. Пусть n точка, характеризующая положение частицы в момент времени n   0 . Легко видеть, что последовательность  , n    n образует цепь Маркова, а все ее состояния – существенные и сообщающиеся, а d1  ...  dN  N . Определение. Существенное состояние Ej с периодом dj  1 называется ациклическим. Утверждение (без доказательства). Все состояния неприводимой цепи Маркова имеют одинаковый период. Определение. Неприводимая цепь Маркова, в фазовом пространстве которой все состояния ациклические, называется ациклической. Всякой конечной однородной цепи Маркова с матрицей переходных вероятностей  || pij ||NN , соответствует взвешенный орграф G  , для которого  является матрицей смежности: pij - это вес ребра eij если pij  0 , то ребро eij отсутствует. Такой орграф называется графом переходов. Для неприводимости цепи Маркова необходима сильная связность графа переходов. Эргодические подклассы составляет компоненты сильной связности орграфа, а несущественные состояния лежат на подходах к ним. Смена состояний в конечной однородной цепи Маркова эквивалентна переходу от вершины к вершине в конечном графе в соответствии с вероятностями, заданными весами на дугах. Такие процессы задают случайное блуждание на графе. Пример. При случайном блуждании с поглощающими экранами граф переходов выглядит следующим образом: Эргодическая теорема для неприводимых цепей Маркова Докажем некоторые результаты из теории чисел, играющие важную роль в дальнейшем изложении. Лемма 1. Если наибольший общий делитель чисел m1, m2 ,..., mr равен 1, то существует n 0   такое, что любое натуральное число n  n 0 можно представить в виде линейной комбинации n  k1m1  ...  kr mr , где ki   0 при всех i  1, r . r Доказательство. Возьмем произвольное n   и разделим его с остатком на m i 1 n  k (m1  ...  mr )  d , где Мы получим, что i . 0  d   i 1 mi . По свойствам k наибольшего общего делителя существуют такие li   , i  1, r , что 1  l1m1  ...  lr mr . Тогда n  k (m1  ...  mr )  d (l1m1  ...  lr mr )   (k  dl1 )m1  ...  (k  dlr )mr . Если обозначить ki  k  dli при всех i  1, r , то получим, что если k достаточно большое, то ki  0 .   Лемма доказана. Обозначим M i  n   : pii (n )  0 . Если Ei - состояние неприводимой цепи Маркова с периодом d , то из неприводимости следует, что множество M i не пусто, и d делит любое число n  M i . В множестве M i можно указать числа m1d,..., mrd такие, что наибольший общий делитель чисел m1, m2 ,..., mr равен 1 (иначе период был бы не d , а больше). Из леммы 1 следует, что существует n 0   такое, что любое натуральное число n  n 0 можно представить в виде линейной комбинации n  k1m1  ...  kr mr , где ki   0 при всех i  1, r . Следовательно, nd  k1m1d  ...  kr mrd . Лемма 2. В введенных выше обозначениях получаем, что все достаточно большие числа вида nd принадлежат множеству M i . Доказательство. Верна следующая цепочка неравенств: pii nd   pii k1m1d  ...  kr mrd      pii k1m1d   ...  pii kr mrd   pii m1d  k1    ...  pii m1d  kr  0. Лемма доказана. Следствие 1. Если d  1 , то в введенных выше обозначениях получаем, что все доста   точно большие числа n принадлежат множеству M i  m   : pii m   0 . Следствие 2. Для неприводимой ациклической цепи Маркова существует n 0   такое, что при любом натуральном числе n  n 0 все диагональные элементы матрицы переходных вероятностей за n шагов  n   n положительны. Лемма 3. Для неприводимой ациклической конечной цепи Маркова существует n1   такое, что при любом натуральном числе n  n1 все элементы матрицы n положительны. Доказательство. Из следствия 2 получаем, что достаточно проверить элементы, не стоящие на главной диагонали. Для всех Ei  E j из условий леммы следует, что существует натуральное nij такое, что pij nij   0 . Тогда для всех l   верно неравенство pij l  nij  n 0   pii n 0  l   pij nij   0 . Выберем в качестве n1  n 0  max nij  1 . (i , j ) Лемма доказана. Теперь с использованием этих лемм докажем следующий результат. Теорема (эргодическая для неприводимых ациклических цепей Маркова). Пусть цепь Маркова конечна, неприводима и ациклична (т. е. d  1 ). Тогда при всех i, j  1, N , где N - мощность фазового пространства E , существует ненулевой предел lim pij n  , n  который не зависит от i . Если обозначить lim pij n   p j , то pj  0 . n  Доказательство. Далее мы будем рассматривать такие n , что n  0 (т. е. pij n   0 при всех i, j  1, N ). Сперва введем обозначения. Пусть максимальный и минимальный элементы вероятностей n . Теперь при фиксированном j M j n   max pij n  , m j n   min pij n  i в j -м i столбце матрицы - переходных выберем i так, чтобы выполнялось равенство M j n  1  pij n  1 . Очевидно, что верна следующая цепочка неравенств M j n  1  pij n  1   pik pkj n   M j n   pik  M j n  . (k ) Теперь выберем i Очевидно, что (k ) так, чтобы выполнялось равенство m j n  1  pij n  1 . mj n  1  pij n  1   pik pkj n   mj n   pik  mj n  . (k ) (k ) Следовательно, при любом j верны неравенства 0  M j n  1  M j n  и 1  m j n  1  m j n  .     Последовательности M j n  и m j n  монотонны и ограничены. Следовательно, существуют пределы lim m j n   A и lim M j n   B . n  n  Если мы докажем, что A  B , то так как m j (n )  pij  M j (n) , то мы получим, что существует lim pij n   p j и этот предел из-за конечности фазового пространства цепи n  Маркова больше нуля. Если фазовое пространство состоит из одного элемента, то все очевидно. Мы будем рассматривать случай, когда E  1 . Выбираем состояния Ei  Ei и E j . 1 2 Используя уравнения Колмогорова-Чепмена, pi j n    pi k s  pkj n  s  и pi j n    pi k s  pkj n  s  . Тогда 1 1 (k ) 2 pi j n   pi j n   1 2 что 2 (k )  p n  s p s   p s  kj i1 j (k ) Введем два множества:   E получаем, i2 j  n   0 . E   Ek  E : pi k n   pi k n   0 , E Так 1 k 2  E : pi k n   pi k 1 2  p s   p s   1  1  0 , как i1k (k ) то i2k верно равенство  p s   p s     p s   p s  . Обозначим левую часть этого равенства k : Ek E  i1k i2k как h (i1, i2 ) . Тогда pi j n   pi j n   1 i1k k :Ek E  2  i2k  p s   p s  p n  s   k : Ek E  i1k i2k kj  p s   p s  p n  s   M n  s   h i , i   k : Ek E  i1k i2k kj j  1 2  m j n  s   h i1, i2   h i1, i2  M j n  s   m j n  s  . Так как E   E , то h i1, i2    k : Ek E  pi k s   1 . Обозначим h  max h i1, i2   1 . Тогда i1 ,i2  1    pi j n   pi j n   h M j n  s   m j n  s  . 1 2 Выберем числа i1 и i2 так, чтобы pi j n   M j n  и pi j n   m j n  . Обозначим 1 2 n  s  n / s   z , где z   , 0  z  n / s  . Тогда M j n   m j n   h M j n  s   m j n  s          h 2 M j n  2s   m j n  2s    h  Очевидно, что n /s   M z   m z  . j j M j z   m j z   M j z   1 , следовательно,  M j n   m j n   h  Так как h  1 , то верны неравенства   n /s   . 0  lim M j n   m j n   lim h  n  n /s   n   0. Следовательно, существуют и равны между собой пределы lim M j n   lim m j n   lim pij n   p j  0 . n  n  n  Теорема доказана. Вектор p  p1, p2 ,..., pN  назовем предельным распределением цепи Маркова или эргодическим распределением. Легко видеть, что верно следующее равенство  p p  p   1 2 N  p p  p  2 N  , lim n   1  n          p1 p2  pN  т.е. устремив степень матрицы переходных вероятностей неприводимой конечной ациклической цепи Маркова к бесконечности, мы получим матрицу, в которой все строки одинаковы, и которая не содержит нулевых элементов. Теорема (без доказательства). Предельное распределение конечной неприводимой ациклической цепи Маркова с фазовым пространством мощности N удовлетворяет системе линейных уравнений: N  xk  1  k 1  N  x  x p , j 1, N   j k 1 k kj и является её единственным решением. Если обозначить x  x 1,..., x n  , то эту систему можно записать в виде  N  x  1  k .  k 1 x  x  Определение. Рассмотрим матрицу AN ,N с неотрицательными элементами. Если для всех i  1, N N выполняется равенство a j 1  1, ij то эта матрица называется стохастической. Стохастическая матрица BN ,N называется дважды стохастической, если для всех j  1, N выполняется равенство N b i 1 ij  1. Следствие. Если конечная неприводимая ациклическая цепь Маркова имеет дважды стохастическую матрицу переходных вероятностей, то её предельное распределение имеет вид: 1 1 p   ,...,  . N  N Легко видеть, что такой вектор – решение системы уравнений  N  x  1  k .  k 1 x  x  Стационарные распределения Пусть дана цепь Маркова с матрицей переходных вероятностей  и начальным   распределением p(0)  P 0  j , j  1, N , где N – мощность фазового пространства E . Через p(n ) обозначим распределение цепи Маркова в момент времени n :   p(n )  P n  j , j  1, N , p(n )  p(0)n . Определение. Вектор q с координатами q ,...,q  1 распределением цепи Маркова, если для всех i  1, N N выполняются равенства q i 1 i N называется стационарным верно неравенство qi  0 и  1 и q  q . Заметим, что если в качестве p(0) взять q , то для всех n   выполняется p (n )  qn  qn 1  ...  q . Если цепь Маркова конечна, ациклична и неприводима, то по теореме об эргодичности существует единственное стационарное распределение, совпадающее с предельным: q j  lim pij (n )  pj . n 