Цепи Маркова (1121219), страница 23
Текст из файла (страница 23)
К лучшей оценкеприводит неравенство Чигера (см. формулу (1.13.18)).В модифицированной постановке задачи последнее собственное значение 2d −1 = −1 + 2/ (d + 1), и результат «геометрического оценивания»щели от −1 является точныммод−1>2.d+1(1.13.12)(1.13.15)Перейдем теперь к неравенству Чигера. Рассмотрим вновь случайноеблуждание на общем неориентированном графе с множеством вершин Gбез кратных ребер.
Для заданного множества S ⊂ G определим поток изS в его дополнение Sc = {1, . . . , l} \ S как подмножество стрелок из Sв Sc :X1.(1.13.16)Q(S, Sc) =(i,j); i∈S,j∈Sc , pij >0.(1.13.14)b=−1∗Чтобы вычислить b, используем тот факт, что диаграмма является симметричной и не имеет значения, какую стрелку e мы выберем. Пусть, например,e — это стрелка 0 → l − 1. Предположим, что e содержится в геодезическойлинии, которая начинается в вершине i справа от 0. Тогда i 6 (l − 3) /2,так как общая длина геодезической линии не может превосходить (l − 1) /2.Геодезическая линия может заканчиваться в любой из (l − 1) /2 − i точеккак вне l − 1, так и в l − 1.
ПоэтомуВ примере 1.12.1 при нечетном l имеем(1.13.12) получаем(1.13.8)l−1.2=∗When Harry Met Sigma12E = l, D∗ = 2,13913812 Ср.с названием фильма «When Harry Met Sally».2EГлава 1. Цепи Маркова с дискретным временемЗдесь, как и ранее, E равно числу (неориентированных) ребер графа,а 2E — общее число стрелок. Далее, положимh liminQ(S, Sc) .(1.13.17)h=#SS : 16#S6l/2Неравенство Чигера утверждает, чтоh2626 2h.1(1.13.18)Доказательство неравенства Чигера также дается в § 1.14.В примере 1.12.1 с нечетным l минимум достигается, когда S — множество из (l − 1) /2 последовательных вершин l-угольника, иh=2.l−1(1.13.19)Мы видим, что в неравенстве Чигера нижняя граница задает правильныйпорядок, однако постоянная меньше на множитель 2 .В примере 1.12.2, в его первоначальной (периодической) постановке,минимум достигается, если S является «лицевой гранью» куба, например,S = {xT : x1 = 0}.
Это приводит к равенству1,dh=(1.13.20)и неравенство Чигера превращается в неравенство162d2162.d(1.13.21)Поскольку в этом случае 1 = 1 − 2/d, верхняя оценка является точной,а нижняя оценка имеет тот же порядок, что и в неравенстве Пуанкаре, нопостоянная слегка занижена.Значение постоянной в неравенстве Пуанкаре зависит от структурыграфа; этот факт можно использовать для получения полезных оценок.Ниже мы обсудим одну такую оценку, основанную на разложении пространства состояний на «редко сообщающиеся» подмножества.Пусть ϕ : I → R — это произвольная тестовая функция. Математическое ожидание и дисперсия ϕ относительно инвариантной меры ,очевидно, задаются формуламиX(i) ϕ (i)E ϕ=i∈I§ 1.13. Геометрическая алгебра цепей Маркова, II.
Случайные блуждания на графахиVar ϕ =Xi∈I141(i) (ϕ (i) − E ϕ) 2 .Решающую роль при доказательстве неравенств Пуанкаре и Чигера играет так называемая форма Дирихле (ср. с формулой (1.14.10)), котораяассоциирована с ϕ и матрицей перехода P и определяется как1XE (ϕ) =(ϕ (i) − ϕ (j)) 2 (i)p(i, j).2i,j∈IНеравенство Пуанкаре имеет видE (ϕ) > Var ϕ(1.13.22)и выполняется равномерно по всем ϕ : I → R. Суть состоит в том, чтопостоянная контролирует скорость сходимости ц.м.д.в.
к инвариантномураспределению . Чтобы избежать технических трудностей, возникающихв случае почти периодических цепей, предположим, что вероятности петельравномерно отделены от нуля. Пусть P t (i, .) обозначает распределениецепи на шаге t, при условии, что начальным состоянием является i ∈ I.Если положить111ln+ ln,t(i, ε) = O140то(i)ε||Pt(i,ε) (i, .) − ||TV 6 ε,где ||. ||TV — норма полной вариации, а — постоянная из неравенства(1.13.22).Во многих естественных ситуациях пространство состояний очевиднымобразом может быть разбито на несколько блоков так, что переходы междублоками происходят редко по сравнению с переходами внутри этих блоков.Это упрощает исследование сходимости к состоянию равновесия.
ПустьI = I0 ∪ . . . ∪ Im−1 — разбиение пространства состояний на m непересекающихся множеств. Будем использовать обозначение [m] = (0, 1, . . . , m − 1).Далее определим отображение ¯ ¯ (i) : [m] → [0, 1] посредством формулыX¯ ¯ (i) =(j)(1.13.23)j∈Iiи введем новую матрицу перехода P¯ ¯ : [m] × [m] → [0, 1] следующимобразом:X(k)p(k, l).(1.13.24)p̄(i, j) = ¯ ¯ (i) −1k∈Ii ,l∈Ij142Глава 1. Цепи Маркова с дискретным временемц.м.д.в. на пространстве состояний [m] с матрицей перехода P¯ ¯ являетсяпроекцией исходной ц.м.д.в., индуцированной разбиением (I i).Пример 1.13.1. Проверить, что проекция цепи имеет в качестве своегостационарного распределения ¯ ¯ .Указание.
Это следует из очевидного равенстваi¯ ¯ (i)1¯ ¯ (i)XX(k)p(k, l) =k∈Ii ,l∈IjX(l).l∈IjПри каждом k ∈ [m] сужение ц.м.д.в. на множество Ik имеет переходные вероятности Pk : Ik × Ik → [0, 1] , задаваемые формулойp(i, j),если i 6= j,(1.13.25)pk (i, j) = 1 − P p(i, l), если i = j.§ 1.13. Геометрическая алгебра цепей Маркова, II.
Случайные блуждания на графахисходная ц.м.д.в. удовлетворяет неравенству Пуанкаре с постоянной¯¯¯ ¯ min= min ,.(1.13.27)¯¯3 3 +Д о к а з а т е л ь с т в о. Рассмотрим произвольную тестовую функцию ϕ. Отправной точкой служит разложение Var ϕ относительноразбиения:XX¯ ¯ (i) Var i ϕ +¯ ¯ (i) (E i ϕ − E ϕ) 2 .Var ϕ =(1.13.28)i∈ [m]XE (ϕ) =i∈ [m]гдеCij =¯ ¯ (i) E i (ϕ) +X12Xi,j∈ [m] ,i6=jCij ,(k)p(k, l) (ϕ (k) − ϕ (l)) 2 .k∈Ii ,l∈Ij(1.13.29)(1.13.30)Суммирование здесь и далее производится по i и j из [m] . Для всех такихi, j, что i 6= j и p̄(i, j) > 0, определим ˆ ji : Ii → [0, 1] следующей формулой:ˆji (k)=i (k)Pl∈Ijp(k, l)p̄(i, j).(1.13.31)Заметим, что ˆ ji является вероятностным распределением на Ii .Оценим первое слагаемое в правой части равенства (1.13.28):Потребуем, чтобы и проекция, и сужение цепи были неприводимыми.Тогда набор стационарных распределений ¯ ¯ и 0 , .
. . , m−1 единственный.Предположим, что проекция цепи и ее различные сужения удовлетворяют неравенству Пуанкаре с постоянными ¯ ¯ и 0 , . . . , m−1 соответственно. Определим min = mini i . Наша цель — получить неравенствоПуанкаре для исходной ц.м.д.в. с постоянной Пуанкаре = ( ¯ ¯ , min , ),где — еще один параметр,X= max maxp(k, l).(1.13.26)i∈ [m]Аналогично для формы Дирихле находимl∈Ik \iПример 1.13.2. Докажите, что и проекция цепи, и ее сужение наследуют обратимость во времени исходной цепи.
Кроме того, k (i) = (i) / ¯ ¯ (k)является стационарным распределением сужения цепи.Указание. В силу обратимости для любых i, j ∈ Ik выполняется равенствоk (i)pk (i, j) = k (j)pk (j, i).143Xii∈ [m] k∈Iil∈I\IiX 1ii1 X¯ ¯ (i) E i (ϕ) 6mini¯ ¯ (i) E i (ϕ).(1.13.32)Второе слагаемое мы преобразуем, применив сперва неравенство Пуанкаредля проекции цепи:Наглядно, это вероятность выхода из текущего блока разбиения за одиншаг, максимизированная по всем состояниям.Теорема 1.13.3. Рассмотрим разложение обратимой во времениц.м.д.в.
с конечным пространством состояний на цепь-проекцию и mцепей-сужений, описанное выше. Предположим, что цепь-проекцияудовлетворяет неравенству Пуанкаре с постоянной ¯ ¯ , а цеписужения удовлетворяют неравенствам с одной и той же постоянной min . Пусть параметр определен соотношением (1.13.26). Тогда¯ ¯ (i) Var i ϕ 6Xi6¯ ¯ (i) (E i ϕ − E ϕ) 2 63 X2 ¯¯i6=j1 X¯ ¯ (i) p̄(i, j) (E i ϕ − E j ϕ) 2 62 ¯¯i6=j¯ ¯ (i) p̄(i, j) (E i ϕ − E ˆ j ϕ) 2 + (E ˆ j ϕ − E ˆ ij ϕ) 2 + (E ˆ ij ϕ − E j ϕ) 2 =ii=3[Σ1 + Σ2 + Σ3 ] .2 ¯¯(1.13.33)§ 1.13. Геометрическая алгебра цепей Маркова, II. Случайные блуждания на графахСлагаемые Σ1 , Σ2 и Σ3 вычисляются по соответствующей цепи, например,2X¯ ¯ (i) p̄(i, j) E i ϕ − E ˆ j ϕ .Σ1 =¯ ¯ (i) p̄(i, j)k∈Ii ,l∈Ij¯ ¯ (j) p̄(i, j)k∈Ii ,l∈Ili6=j=XX X(k)p(k, l)(ϕ (k) − ϕ (l)) 2 =¯ ¯ (i) p̄(i, j)X(k)p(k, l) (ϕ (k) − ϕ (l)) 2 =Xi6=jCij ,(i)p(i, j)— совмест¯ ¯ (i) p̄(i, j)где в неравенстве (1.13.34) использован тот факт, чтоminгде p(k, Ij) =X¯ ¯ (i) p̄(i, j)k∈Ii ,l∈Ijпо определению.Чтобы оценить Σ1 , используем стандартный факт: Var = Var( − c)для любой случайной величины и постоянной c.
ЗапишемX jˆ i (k) (ϕ (k) − E i ϕ) 2 − (E ˆ j ϕ − E i ϕ) 2 ,Var ˆ j ϕ =(1.13.37)iik∈Iiтак что наверняка выполнено неравенствоX jˆ i (k) (ϕ (k) − E i ϕ) 2 .(E ˆ j ϕ − E i ϕ) 2 6ik∈Iii=¯ ¯ (i)XXik∈Ii¯ ¯ (i)i (k) (ϕ (k)Xk∈Ii− E i ϕ) 2X ˆ j (k) p̄(i, j)ii (k) (ϕ (k)=XСледовательно, получаем оценкуXX j¯ ¯ (i) p̄(i, j)ˆ i (k) (ϕ (k) − E i ϕ) 2 =Σ1 6i6=j(1.13.38)k∈Iij6=i− E i ϕ) 2Xj6=ii (k)=p(k, Ij) 6l∈Iji¯ ¯ (i) E i (ϕ),i3 X3 X¯ ¯ (i) E i (ϕ).C+ij¯ ¯ min2 ¯¯i6=j(1.13.42)iПодставляя затем соотношения (1.13.28) и (1.13.42)) в формулу (1.13.30),получаемVar ϕ 63 X3 + ¯¯ X¯ ¯ (i) E i (ϕ).Cij + ¯ ¯¯¯2mini6=j(1.13.43)iНаконец, сравнив соотношения (1.13.42) и (1.13.29), видим, чтоE (ϕ) > Var ϕ,таково, как в утверждении теоремы.Пример 1.13.4. Рассмотрим симметричное случайное блуждание награфе-«пенсне» с 2n вершинами (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
