Цепи Маркова (1121219), страница 16
Текст из файла (страница 16)
Если l = 1 (случай единственного замкнутого класса), то цепь неприводима. Выходя из открытогоr=1bpir hkr .bir — это вероятность перехода из класса Oi в класс Or или Cr , и дляЗдесь pr = j + 1, . . . , j + l выполняются равенства hkr = rk .Цепь имеет единственное стационарное распределение (r) , сосредоточенное на Cr , при каждом r = j + 1, . . . , j + l (следовательно, единственноестационарное распределение при l = 1).
Любое стационарное распределение представляет собой смесь стационарных распределений (r) .Если цепь выходит из Cr , то для любой функции f на Cr выполняютсяусловияnX (r)1Xf(Xt) →i f(i) почти наверное.nt=0i∈Cr(n)Более того, в апериодическом случае (когда НОД {n : p aa > 0} = 1 длянекоторого a ∈ Cr) для любого i0 ∈ Cr имеемP (Xn = i | X0 = i0) →ri,и скорость сходимости геометрическая.XjДалее, векторXi6 Ср.bij =pipji ;с названием фильма «Reversal of Fortune».(1.10.1)j pji1=ijX=j pji=ijXi= 1.pji =j.i•сквозь произведение:P (XN = iN , .
. . , X0 = i0) = P (X0 = i0 , . . . , XN = iN) = i0 pi0 i1 . . . piN−1 iN =b i 1 i 0 i 1 . . . p i N −1 i N = bb i2 i1 i2 . . . = pb i N i N −1 i N = i N bb i1 i0 .b i1 i0 . . . p=ppi 1 i 0 pp i N i N −1 . . . pbМы видим, что (XN−n) является ( , P)-цепьюМаркова.2) Если P неприводима, то любые два состояния i, j сообщаются, т. е.существует такой путь i = i0 , i1 , . . . , in = j, что1i0i 0 pi 0 i 1=Пусть (X0 , X1 , .
. .) — ц.м.д.в. и зафиксировано N > 1. Что можносказать об обращенной во времени цепи (Xn), т. е. о семействе (XN−n , n == 0, 1, . . . , N) = (XN , XN−1 , . . . , X0)?= ( i) —Теорема 1.10.1. Пусть (Xn) — это ц.м.д.в. ( , P), гдестационарное распределение для P и i > 0 ∀ i ∈ I. Тогда 1) для любого N > 1 обращенная во времени цепь (XN , XN−1 , . . . , X0) являетсяb где Pb = (pbij) задается равенствомц.м.д.в.
( , P),jbijip«Протащим» теперь множитель§ 1.10. Детальный баланс и обратимостьИз серии «Фильмы, которые не вышли на большой экран».ibявляется P-инвариантным:0 < pi0 i1 . . . pin−1 in =Поворот времени, поворот судьбы61 Xbij =p. . . pin−1 in =1i0b i1 i0pi1. . . pin−1 in = . . . =1j+lXb2) если матрица P неприводима, то таковой является и P.bД о к а з а т е л ь с т в о. 1) Во-первых, заметим, что P является стохаbij > 0 истической матрицей, т. е. phki =99класса, скажем Oi , цепь попадет в замкнутый класс Ck с вероятностью hki .Эти вероятности удовлетворяют уравнению§ 1.10. Детальный баланс и обратимостьГлава 1.
Цепи Маркова с дискретным временем98i0bbin in−1pi 1 i 0 . . . pin .bin in−1 > 0, и состояния j, i являются сообщающиТаким образом, bpi 1 i 0 . . . pbмися и для P.Случай, когда цепь (XN−n) имеет то же распределение, что и цепь (Xn),представляет особый интерес.Теорема 1.10.2.
Пусть (Xn) — ц.м.д.в. Следующие два свойстваэквивалентны:1) для любого n > 1 и любых состояний i0 , . . . , inP (X0 = i0 , . . . , Xn = in) = P (X0 = in , . . . Xn = i0);(1.10.2)2) ц.м.д.в. (Xn) находится в состоянии равновесия, т. е. (Xn) ∼∼ ( , P) где — инвариантное распределение для P иi pij=j pjiдля любых состояний i, j ∈ I.(1.10.3)100Глава 1. Цепи Маркова с дискретным временемД о к а з а т е л ь с т в о. 1) ⇒ 2).
Пусть n = 1,P (X0 = i, X1 = j) = P (X0 = j, X1 = i).Просуммируем по j:XP (X0 = i, X1 = j) = P (X0 = i) =i,jXP (X0 = j, X1 = i) = P (X1 = i) = ( P) i .jТаким образом, i = ( P) i ∀ i, т. е. P = . Следовательно, цепь находитсяв состоянии равновесия с = . Далее,P (X0 = i, X1 = j) =i pij= P (X0 = j, X1 = i) =2) ⇒ 1). ЗапишемP (X0 = i0 , . .
. , Xn = in) =i 0 pi 0 i 1j pji∀ i, j.. . . pin−1 inи воспользуемся уравнениями (1.10.3) чтобы «протащить»изведение:•сквозь про-. . . pin−1 in = pi0 i1 i1 . . . pin−1 in = . . . == pi0 i1 . . . pin in−1 in = in pin in−1 . . . pi0 i1 = P (X0 = in , . . . , Xn = i0).i 0 pi 0 i 1Определение 1.10.3. Цепь Маркова (Xn), удовлетворяющая соотношению (1.10.2), называется обратимой. Уравнения (1.10.3) называютуравнениями детального баланса. Таким образом, утверждение теоремы 1.10.2 гласит: цепь Маркова обратима тогда и только тогда, когда онанаходится в состоянии равновесия и имеют место уравнения детальногобаланса.Уравнения детального баланса являются мощным средством для отыскания инвариантного распределения.Теорема 1.10.4.
Если и P удовлетворяют уравнениям детального балансаi pij = j pji , i, j ∈ I,тоявляется стационарным распределением для P, т. е. P = .Д о к а з а т е л ь с т в о. Просуммируем по j:Xpij = i ,iXjjj pji= ( P) i .§ 1.10. Детальный баланс и обратимость101Эти два выражения равны между собой для любого i, откуда и следуетутверждение теоремы.Таким образом, если для заданной матрицы P удается решить уравнения равновесия (т. е. найти вероятностное распределение, которое имудовлетворяет), то решение является стационарным распределением.
Более того, соответствующая ц.м.д.в. обратима.Интересным и важным классом цепей Маркова являются случайныеблуждания на графах. Мы уже встречали примеры таких цепей: процессрождения и гибели (случайное блуждание на множестве Z 1 или его подмножестве), случайное блуждание на квадратной решетке на плоскости Z 2 и,в общем случае, случайное блуждание на d-мерной кубической решетке Zd .Общей чертой этих примеров является то, чтоблуждающая частица может совершить скачокв любую из соседних точек; в симметричном случае все скачки равновероятны. Эту идею можнораспространить на графы общего вида с ориентированными или неориентированными ребрами.Рассмотрим ненаправленные графы; под графомбудем понимать набор G вершин, некоторыеиз которых соединены ненаправленными ребраРис. 1.29ми, возможно несколькими.
Ненаправленностьозначает, что движение по ребру возможно в обоих направлениях; иногдаудобно представлять, что ребро образовано парой стрелок с противоположными направлениями.Граф называется связным, если для любых двух вершин существуетсвязывающий их путь, составленный из ребер. Кратность v i вершины iопределяется как число ребер в этой вершине.
Связность v ij — это числоребер, соединяющих вершины i и j.Случайное блуждание на графе имеет матрицу перехода P = (p ij)следующего вида:( vij vi , если i и j соединены ребром,(1.10.4)pij =0в противном случае.Матрица P неприводима тогда и только тогда, когда граф связный. Векторv = (vi) удовлетворяет уравнениям детального баланса, т.
е. для любыхвершин i, j выполняются равенстваvi pij = vij = vj pji ,(1.10.5)и, следовательно, он является P-инвариантным. Немедленно получаемследующую теорему.102Глава 1. Цепи Маркова с дискретным временемТеорема 1.10.5. Случайное блуждание на графе с матрицей перехода P вида (1.10.4) всегда имеет положительную или нулевуювозвратность. Оно положительно возвратнотогда и только тоPvi конечна, и в этом случаегда, когда суммарная кратностьiPvi является стационарным распределением. Более того,j = vj§ 1.10.
Детальный баланс и обратимость103Другой важный пример — это правильный куб размерности d с 2dвершинами. Тут кратность равна d и граф имеет d2d−1 (по-прежнемуненаправленных) ребер, соединяющих соседние вершины. См. рис. 1.32.iцепь со стационарным распределением обратима.Простым, но хорошо известным примером графа является l-точечныйсегмент одномерной решетки: в этом случае кратность каждой вершиныравна 2, за исключением крайних точек, кратность которых равна 1. См.рис.
1.30 a).Рис. 1.32Популярными примерами бесконечных графов с постоянной кратностью являются решетки и деревья.В случаеобщего конечного графа с постоянными кратностями v i = vPvi равняется v × |G| где |G| — число вершин. Тогда pij = pji =суммаiРис. 1.30Интересным классом является класс графов с постоянной кратностью:vi ≡ v; как простой пример приведем случай v = 2, в котором l вершинпомещены на круг (или на правильный многоугольник). См. рис.
1.30 б).Хорошо известным примером графа с постоянной кратностью являетсяполностью связный граф с заданным числом вершин, скажем {1, . . . , m}:здесь кратности равны m − 1, и граф состоит из m(m − 1) /2 (ненаправленных) ребер. См. рис. 1.31.= vij /v, для любых соседних вершин i, j. Это означает, что матрицапереходных вероятностей P = (pij) эрмитова: P = PT . Более того, стационарное распределение = ( i) равномерно: i = 1/|G|.В курсе линейной алгебры доказывается, что (комплексная) эрмитоваматрица имеет ортонормированный базис из собственных векторов и всеее собственные числа положительны. Это очень полезное свойство, которое было бы желательно сохранить.
Для марковских цепей с дискретнымвременем даже в случае, когда исходная матрица P неэрмитова, мы можем«преобразовать» ее в эрмитову, введя новое скалярное произведение. Мыбудем использовать этот подход в § 1.12–1.14.Time present and time pastAre both perhaps present in the future,And time future contained in time past.Настоящее и прошедшее,Вероятно, наступят в будущем.И время будущее присутствует в прошедшем.Т. С. Элиот (1888–1965), английский поэт (пер. А. Сергеева)Рис. 1.31Пример 1.10.6. а) Пусть задано конечное число аэропортов. Предположим, что любые два аэропорта i и j связаны ежедневными рейсами,причем aij = aji , где aij — ежедневное число рейсов из i в j, а aji — из j в i.Рассеянный путешественник ежедневно совершает перелет, выбирая рейсслучайным образом из всех возможных.
Подсчитайте, спустя сколько днейiление. Покажем, что 1/i, где — единственное инвариантное распреде.PP=ajkaik .j,k∈IВ самом деле,ajkpjk = Pajll∈Iиk∈IXl∈IX ajl pjk =akl pkj .Таким образом, вектор v = (vj), где vj =Pl∈Iajl , находится в состоянииl∈Iiчто случайное блуждание возвратно.Уравнения детального баланса дают мощный метод нахождения стационарного распределения:если мера P > 0 состоит в детальном балансеPс матрицей P иi < ∞, то j = j /i и есть стационарное распредеiiление.Замечание 1.10.7. Свойство обратимости особенно полезно в случаенепрерывного времени, см. гл. 2.Приведем краткую сводку наиболее существенных уравнений, возникающих при анализе ц.м.д.в.Мы познакомились с двумя видами уравнений: (I) для вероятностейдостижения hAi и средних времен достижения kAi и (II) для инвариантныхраспределений = ( i) и среднего времени ki пребывания в состоянии i,прежде чем цепь вернется в k.
Хотя эти уравнения и похожи, существуюттакже и различия между ними, о которых важно помнить.I.1. Уравнения для вероятностей hji = P i (попасть в j) таковы:Xpil hjl = (hj PT) i , i 6= j,hjj = 1, hji =l∈Iдетального баланса с матрицей P. Следовательно,X .Xajkakl .j =k∈I−mЗаметим,и i постоянны внутри блоков длины 2m , чтоP что 2m −1 = 2влечетi = ∞. Отсюда следует, что u1 = 0, т. е. hi = 1 для всех i, так1возвращения в i равногдеk,l∈Iб) Рассмотрим расстояние Xn от корня R в момент времени n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
