Цепи Маркова (1121219), страница 22
Текст из файла (страница 22)
Более того, матрица P является обратимой относительно стационарного распределения = ( i) : i pij = j pji , i, j ∈ G. Если кратность viпостоянна, то матрица перехода P = (pij) является эрмитовой и вышеуказанное стационарное распределение = ( i , i ∈ G) является равномерным:i = 1/|G|. Мы отмечали, что в этом случае матрица P имеет ортонормированный базис из собственных векторов в R |G| и все ее собственныезначения действительны.
Далее, согласно теореме Перрона —Фробениусавсе собственные значения P лежат в замкнутом отрезке [−1, 1] . Инымисловами, спектр матрицы P является подмножеством интервала [−1, 1] ,и 0 = 1 является крайней справа точкой спектра.В общем случае матрицу P можно превратить в эрмитову, если заменитьстандартное скалярное произведение h · , · i в R |G| взвешенным скалярнымпроизведением:Xhx, yi =x i yi i .(Из серии «Как они делают это».)i=(1.13.1)Мы проверили, что равенствоср.
с (1.12.11). Тогда для любого начального распределения= ( 1 , . . . , l)iвершины i существует v стрелок, выходящих из i и ведущих к соседнимвершинам, и v стрелок, выходящих из этих вершин и ведущих к i (v = 2в примере 1.12.1 и v = d в примере 1.12.2). В общем случае кратность v iможет зависеть от i.Граф можно изображать без указания направлений или же рисоватьв каждом ребре две стрелки в противоположных направлениях. Cлучайноеблуждание на графе было определено как ц.м.д.в. с (конечным) пространством состояний G — множеством вершин графа и матрицей вероятностейперехода P с элементамидля любого начального распределения .Если P — периодическая матрица, то l−1 = −1. В этом случаематрица P2 приводима и имеет два сообщающихся класса, скажем C1и C2 , и два инвариантных распределения (1) и (2) = (1) P, сосредоточенных на этих сообщающихся классах.
Геометрическая кратностьзначения l−1 равна единице, а собственный вектор пропорционален векторуΠ = (1) − (2) ,(1.12.35)135стрелки в противоположных направлениях: (i → j) и (j → i). Примеры1.12.1, 1.12.2 попадают в эту категорию.графы в этих примерахP ВдобавокPvij ≡vij ≡ v > 1, т. е. для каждойимеют постоянную кратность: vi ≡jЕсли P — апериодическая матрица, то l−1 (P) > −1 и спектральная щель = (P) = (PT) задается формулой= min [1 −§ 1.13. Геометрическая алгебра цепей Маркова, II.
Случайные блуждания на графахМногие вещи становятся более понятными, если рассмотреть классслучайных блужданий на графах. Определение было приведено в § 1.10;здесь мы ограничимся рассмотрением конечных неориентированных графов без кратных ребер и петель. Иными словами, связность v ij принимаетзначения 0 или 1; в первом случае нет ребра, которое бы связывало i и j,а во втором случае есть единственное ребро, которому приписывают двеi∈GТаким образом, для общего случайного блуждания на графе спектр матрицы P также является подмножеством отрезка [−1, 1] и содержит 0 = 1как свою крайнюю справа точку.§ 1.13. Геометрическая алгебра цепей Маркова, II.Случайные блуждания на графах136Глава 1.
Цепи Маркова с дискретным временем§ 1.13. Геометрическая алгебра цепей Маркова, II. Случайные блуждания на графах137−1 ] ,где1=1−1,−1=1−|min [ 1 ,не является собственным значением, т. е. не принадлежит спектру матрицы P. Следовательно, спектральная щель — это|G|−1 |] .(1.13.4)1Рис. 1.38Если рассматриваемый граф является связным, то случайное блуждание неприводимо, и наоборот. См.
рис. 1.37. В этом случае цепь имеетединственное стационарное распределение и геометрическая кратностьсобственного значения 0 = 1 равна 1. В дальнейшем мы сосредоточим внимание только на случае неприводимых случайных блужданий. Каки в предыдущем параграфе, запишем собственные значения в невозрастающем порядке:(1.13.3)1 = 0 > 1 > . . . > |G| > −1.Точка −1 может либо принадлежать, либо не принадлежать спектруматрицы P: это зависит от того, является цепь периодической или нет.Можно проверить, что при наших условиях цепь может иметь только период 1 (апериодическая цепь) или период 2 (цепь с двумя периодическимиподклассами).
Если −1 является собственным значением матрицы P, тограф является двудольным, т. е. множество вершин G можно разбить надва таких непересекающихся подмножества G (1) и G (2) , так что каждоеребро графа соединяет вершину из G (1) с вершиной из G (2) . В этом случаецепь является периодической и период равен 2.
И наоборот, если цепьпериодична с периодом 2, то −1 является собственным значением. Еслипериодическими подклассами являются G1 и G2 , то собственный вектор,соответствующий собственному значению −1, пропорционален вектору1 G1 − 1 G2 .Здесь 1 Gl — это вектор, компоненты которого равны 1 для состояний изGl и равны 0 для состояний из другого класса.Таким образом, если матрица P является апериодической, то точка −1−1= −1 +1,l−1 .(1.13.5)Для любой пары i, j вершин правильного l-угольника можно определить геодезическую линию от i к j, т. е. кратчайший путь из i в j,составленный из стрелок; так как l нечетно, геодезическая линия определяется единственным образом.
Для случайного блуждания на графе общеговида геодезическая линия Γ между двумя вершинами (состояниями) i и jвновь определяется как путь, начинающийся в i и заканчивающийся в jи имеющий наименьшую длину, т. е. составленный из минимального числастрелок. Этот путь может быть не единственным, но мы выберем однутакую геодезическую линию для любой пары i, j ∈ G и обозначим ееΓij ∼ (i0 , i1 , .
. . , iL); здесь i0 = i, iL = j, и L — длина пути Γij . Заметим, чтогеодезическая линия Γji не обязательно совпадает с геодезической линиейΓij в противоположном направлении: выбирать геодезические линии нужновдумчиво. Всю совокупность выбранных геодезических линий обозначим G .Оказывается, для неприводимой эрмитовой стохастической матрицыP вида (1.13.1), обратимой относительно стационарного распределениявида (1.13.2), имеет место полезное неравенство для 1 , называемоенеравенством Пуанкаре. Это неравенство имеет вид1>2ED2∗∗b.(1.13.6)Мы проведем доказательство этого неравенства в § 1.14, следуя статье:Diaconis P. , Strook D.
Geometric bounds for eigenvalues of Markov chains// Ann. Appl. Probab. 1991. V. 1. P. 36–61.Здесь E — общее число (неориентированных) ребер графа, D ∗ — максимальная кратность вершины, ∗ — максимальное число ребер в геодезической линии этого графа (диаметр направленного графа, составленный изстрелок). Наконец, b — это максимальная мощность пучка геодезическихлиний, содержащих заданную стрелку:Рис. 1.37=1−Вернемся к примеру 1.12.1 и предположим, что l нечетно; в этом случаематрица P является апериодической иb = max [число геодезических линий Γ ∼ (i0 , i1 , . .
. , iL),e= (i→j)содержащих стрелку e] .(1.13.7)Глава 1. Цепи Маркова с дискретным временем§ 1.13. Геометрическая алгебра цепей Маркова, II. Случайные блуждания на графахВ примере 1.12.1 при нечетном l имеем(Из серии «Фильмы, которые не вышли на большой экран».)2 (l − 1) 2(l − 1) (l − 3)l2 − 1−i =−=.488(1.13.9)(1.13.13)что дает правильный порядок по l, но неверную постоянную.В примере 1.12.2, в изначальной (периодической) постановке, последнее собственное значение 2d −1 = −1. Определим путьв 0,, 0 из0заменяя те компоненты в , которые отличаются от , на их дополненияпо модулю 2, продвигаясь слева направо по одному шагу в каждый моментвремени.
(Это полегче, чем изучать геодезические линии.) Очевидно, E == d2d−1 , ∗ = d, D∗ = d, и для такого выбора пути b = 2d−1 . Чтобыпоказать это, рассмотрим ребро (w, z), где w, z отличаются друг тот другалишь одной координатой, например j-й.
Путь xy , содержащий это ребро,может начинаться в любой вершине x, у которой все координаты после(j − 1)-й совпадают с соответствующими координатами w (2 j−1 возможностей), и заканчиваться этот путь может в любой вершине y, у которой всекоординаты до j-й включительно совпадают с соответствующими координатами z (2d−j возможностей).
Таким образом, существует 2d−1 путей xy ,проходящих через заданное ребро. Оценка (1.13.6) приводит к неравенствуТеперь оценка (1.13.6) принимает вид1>8l,(l − 1) 2 (l + 1)(1.13.10)или 1 > 8/l2 при l → ∞. Это менее точная оценка, чем (1.12.12),и поправочный коэффициент равен 2 2 /8 ≈ 2.Далее, имеет место следующая полезная оценка для −1 . Определим(ориентированный) цикл как замкнутый путь вдоль (некоторых) ребернашего графа, который проходит через каждую из своих вершин ровноодин раз, прежде чем вернется в исходную точку, и имеет фиксированное направление обхода (есть в точности два направления для заданногонабора ребер). Иными словами, цикл проходит через заданное ребро неболее одного раза.
Удобно зафиксировать направление, т. е. выбрать одноиз двух: либо по часовой стрелке, либо против часовой стрелки. Рассмотрим множество S таких циклов нечетной длины (по одному для каждойвершины i ∈ G), что цикл Σ = Σi из S начинается и заканчивается в i.Обозначим символом ∗ максимальную длину цикла из Σ (т. е. максимальное число ребер в этом цикле). Далее, пусть b∗ обозначает максимальноечисло циклов из S , содержащих заданное ребро:b∗ = max [число циклов из S , содержащих стрелку e] .e= (i→j)Тогда>2D∗−1∗ b∗(1.13.11)06i6 (l−3) /2l − 11,l2X>= b∗ = l. Из соотношения1>2,d2что не слишком хорошо из-за «линейной» степени d.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
