Цепи Маркова (1121219), страница 18
Текст из файла (страница 18)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .000...1 /m(m − 1) /m111и k = k(m) определяется как наибольшее значение, для которого выполняется неравенство1/j(j − 1) · 1/ (i − 1) · 1/ (in−1 − 1) . . . 1/ (i1 − 1)i=,1/i(i − 1) · 1/ (in−1 − 1) . . . 1/ (i1 − 1)j(j − 1)pim+1 = P 1 (Xn+1 = m + 1Xn = i, Xn−1 = in−1 , . . . , X1 = i1) =§ 1.11. Управляемые и частично наблюдаемые цепи Маркова11Чтобы определить момент остановки, рассмотрим решающее правило(0 продолжать,1 6 j 6 m.d(j) =1 остановиться,т. е. m/k ≈ e и k ≈ m/e.Замечание 1.11.2. Пример 1.11.1 можно рассматривать в более общей постановке, когда принимают во внимание так называемую величину«удовлетворенности», которая достигает своего максимума, когда выбраннаилучший из всех объект, значение этой величины несколько меньше,если выбранный объект — это второй наилучший и т. д. Эта обобщеннаязадача решается аналогично.Не я управлял событиями, но признаю откровенно —события управляли мною.A. Линкольн (1809–1865), Президент Соединенных Штатов АмерикиWho can control his fate? (Othello)Кто царь своей судьбы?В.
Шекспир, Отелло. Пер. М. Л. Лозинского112Глава 1. Цепи Маркова с дискретным временемПример 1.11.3. 1. Пусть J является собственным подмножеством конечного пространства состояний I неприводимой цепи Маркова (X n) с матрицей перехода P, которая разбивается на блоки следующим образом:P=PJJ PJI\JPI\JJ PI\JI\JXn>0(PI\JI\J) n PI\JJ = PJJ + PJI\J (II\J − PI\JI\J) −1 PI\JJ ,где II\J — это единичная матрица со строками и столбцами, индексы которых i, j ∈ I \ J.2.
Член парламента Билл Сайкс, находясь в Лондоне, может проводитьвремя либо в Палате Общин (C), либо в своей квартире (F), либо в баре(B), либо со своей подругой (G). Каждый час он меняет свое местонахождение в соответствии с матрицей перехода P, хотя жена его, котораяне подозревает о существовании подруги, полагает, что его перемещенияконтролируются матрицей перехода P W :CC 1 /3F 0P=B 1 /3G 1 /3FB1 /3 1 /31 /3 1 /30 1 /31 /3 0G01 /3 ,1 /3 1 /3PWCC 1 /3= F 1 /3B 1 /3FB1 /3 1 /31 / 3 1 / 3 .1 /3 1 /3Знакомые видят Билла только тогда, когда он находится в J = {C, F, B};подсчитайте матрицу перехода P̃, которая, согласно их мнению, управляетего передвижениями.Всякий раз, когда знакомые видят, что Билл переходит на новое место,он звонит на мобильный телефон своей жены; выпишите матрицу перехода,которая управляет последовательностью мест, откуда Билл делает звонки,и вычислите ее инвариантное распределение.Жена Билла записывает, откуда поступает каждый его звонок, и унее возникают подозрения — Билл приходит в свою квартиру недостаточно часто.
Уличенный, Билл клянется в верности, решает отказаться отвызывающей неприятности матрицы переходов, выбрав, взамен прежней,113следующую матрицу:CC1 /4F 1 /2P∗ =B 0G 2/10.Если фиксируются только переходы в состояния, принадлежащие множеen) со значениями в J; покажите, что ееству J, то мы наблюдаем ц.м.д.в. (Xматрица перехода имеет видe = PJJ + PJI\JP§ 1.11. Управляемые и частично наблюдаемые цепи МарковаF1 /41 /43 /81/10B1 /21 /41 /81/10G00 ,1 /2 6/10и по-прежнему настаивает, что его передвижения управляются матрицейPW . Сможет ли он таким образом отвести подозрения жены? Обоснуйтесвой ответ.e =Решение.
1. Ср. с примером 1.4.4. Чтобы проверить равенство P−1= A + B(I − D) C, запишемe 1 = j| Xe0 = i) =P (X∞XP (Xn = j, Xr 6∈ J для r = 1, . . . , n − 1|X0 = i) == pij +n=2= pij +∞ XXXn=0 k6∈J l6∈Jpik (Dn) kl plj , i, j ∈ J.2. Воспользовавшись результатом первой части задачи, при J == {C, F, B} находим1 /3 1 /3 1 /31 /6 1 /2 1 /31 /2 1 /6 1 /3e = A + B(I − D) −1 C =P!.Далее, матрица перехода для звонков из C, F и B имеет вид!0 1 /2 1 /21 /3 0 2 /33 /4 1 /4 0=(ее инвариантное распределениеC=13F+34B,F=12CC,+;F,34B)B,и определяется единственным образом как=43 4,.11 11 11,удовлетворят равенствамB=12C+23F114Глава 1.
Цепи Маркова с дискретным временемДалее, матрица для P∗ имеет видf∗ =P§ 1.12. Геометрическая алгебра цепей Маркова, I.Собственные значения и спектральные щели!1 /4 1 /4 1 /21 /2 1 /4 1 /41 /4 1 /2 1 /43 3 3Иными словами, Билл в среднем проводит одинаковое время в каждом из«легальных» состояний C, F и B.Однако его жена может наблюдать следующие расхождения с матрицейPW :а) звонки из B, следующие за звонками из C, происходят в два разачаще, чем звонки из B, следующие за звонками из F,б) среднее число звонков 50/71 > 2/3, в то время как согласно матрице PW в среднем их должно было быть 2/3. Однако это расхождениенезначительно, и этот метод не очень полезен на практике.
Действительно, для инвариантного распределения ∗ = ( ∗C , ∗F , ∗B , ∗G) матрицы P∗выполняется равенство ∗ P∗ = ∗ . Это означает, что141∗F = 41∗B = 21∗G = 2=121∗C+ 41∗C+ 43∗B+ 5∗C+1 ∗,5 G3 ∗∗F + 8 B+1 ∗∗F + 8 B+∗F343т. е.47т. е.82т. е.5т. е.+1 ∗,10 G1 ∗,10 G∗G,121∗F = 41∗B = 21∗G = 2∗C=1 ∗,5 G3 ∗∗C+ 8 B+1 ∗∗C+ 8 F +∗F+∗B.Инвариантное распределение единственно:∗C=28,71∗F=34,71∗B=4,71Теорема 1.9.3 дает оценки скорости сходимости к стационарному распределению. Эта теорема демонстрирует, что скорость сходимости является экспоненциальной (или геометрической) по n, что совсем неплохо.Однако величина (1 − ) 1/m , стоящая в правой части соотношения (1.9.14),может быть довольно близкой к 1, особенно если имеется естественная последовательность ц.м.д.в.
на расширяющихся пространствах состояний I l .Приведем пример ситуации, когда возникает эта проблема. Рассмотрим(l × l)-матрицу A с элементами aij , равными 0 или 1. Перманент матрицыA определяется подобно определителю, следует лишь опустить знаки:и ее инвариантное распределение равномерное1 1 1∗=, ,.∗C§ 1.12. Геометрическая алгебра ц.м.д.в., I. Собственные значения и спектральные щели 115∗G=5.71За длительный период времени среднее число звонков равно283343435650× +× +× +×= .7147147187110711 ∗,10 G1 ∗,10 GXper A =lYai(i) .: перестановка порядка l i=1Перманент per A равен числу «совершенных связей» между точкамиi ∈ {1, .
. . , l}, индексирующими строки, и точками j ∈ {1, . . . , l}, индексирующими столбцы. Популярная интерпретация такова: пусть естьмножество, составленное из l мальчиков и l девочек; равенство a ij = 1означает, что девочка i и мальчик j нравятся друг другу, а равенство a ij == 0 означает, что это не так. Тогда per A подсчитывает число возможных«свадеб», где каждая свадебная пара любит друг друга. Это трудная задачас точки зрения вычислений: наилучший из существующих алгоритмов вычисления per A требует l2l шагов.
Стохастический метод вычисления per Aосновывается на ассоциированной с ним ц.м.д.в., и важно уметь оцениватьскорость сходимости к стационарному распределению при больших l.Пример 1.12.1. Пусть l — натуральное число. Расположим l точек 0,1, . . . , l − 1 на единичной окружности в вершинах правильного l-угольника. Рассмотрим случайное блуждание (Xn) на этих точках, при которомчастица перескакивает в одну из соседних точек с вероятностью 1 /2.Переходная матрица этой ц.м.д.в. — это (l × l)-матрица вида:01 /2 0 .
. . 0 1 /20 1 /2 . . . 00 ,...1/2 00 . . . 1 /2 01 2P= /(1.12.1)содержащая много нулей. Действительно, при четных l множество вершинразбивается на «четное» подмножество Wч = {0, 2, . . . , l − 2} и «нечетное»подмножество Wнеч = {1, 3, . . . , l − 1}. Эти подмножества образуют периодические подклассы: например, если цепь выходит из вершины, входящей116Глава 1. Цепи Маркова с дискретным временем§ 1.12. Геометрическая алгебра ц.м.д.в., I. Собственные значения и спектральные щели 117стационарное распределение=11, ...,ll1= 1T ,l 1где 1 = ...
.(1.12.2)1Кроме того, матрица P обратима с этим стационарным распределением.Рис. 1.34в четное подмножество, то она будет попадать в нечетное подмножество вовсе нечетные моменты времени и будет попадать в четное подмножествов четные моменты времени.
Таким образом, при четных l цепь (X n) являетсяпериодической с двумя подклассами. При нечетных l элементы матрицыPm впервые все станут положительными, когда показатель степени будетравен m = l. Далее, минимальный элемент матрицы P l равен 2/2l = 1/2l−1 ,что равно вероятности P 0 (X1 = 0) = P (Xl = 0|X0 = 0) (поскольку цепьпопадает из 0 в 0 за l шагов, только если пройдем вдоль всего пути в любомнаправлении).Таким образом, при нечетных l правая часть соотношения (1.9.14)принимает следующий вид:1 n/ (l−1)n1 − l−1≈ exp − l−1.(1.12.3)22(l − 1)Это означает, что, желая иметь равномерную сходимость при l, n → ∞,мы должны гарантировать, что n/ (2l l) → ∞, т. е. n должно расти быстрее,чем 2l l.
Является ли эта оценка точной?Чтобы найти ответ, обратимся к алгебре. Матрица (1.12.1) является эрмитовой: PT = P. Следовательно, она имеет l ортонормированныхсобственных векторов, образующих базис в l-мерном действительном евклидовом пространстве Rl (и в l-мерном комплексном евклидовом пространстве Cl), и все ее собственные значения действительны.
Собственныевекторы можно найти, воспользовавшись элегантным аппаратом дискретного преобразования Фурье. А именно, рассмотрим функции 0 , . . . ,l−1 , где1j, j, p = 0, 1, . . . , l − 1.(1.12.4)p (j) = √ exp 2 ipllp=Здесь j = 0, 1, . . . , l − 1 — дискретный аргумент этих функций, p == 0, 1, . . . , l − 1 — дискретный параметр, индексирующий эти функции.Эквивалентным образом, можно представить p как векторы из Cl , записавp (0)...p (l − 1)(компоненты здесь занумерованы числами 0, . . . , l−1 вместо традиционнойнумерации 1, . .
. , l, но это поможет сделать алгебраические выкладкиболее прозрачными). Таким образом,Рис. 1.35Очевидно, что для любого l цепь неприводима и имеет единственное1kTp 1 z }| {1= √ e2 ip·0/l , . . . , √ e2llip(l−1) /l,p = 0, 1, . . . , l − 1.(1.12.5)118Глава 1. Цепи Маркова с дискретным временем√Отметим,√что все наши векторы имеют первой компонентой 1 / l. Нормировка 1/ l выбрана для того, чтобы векторы были ортонормированными:(1, p = p0 ,h p , p0 i = p,p0 =(1.12.6)0, p 6= p0 .§ 1.12. Геометрическая алгебра ц.м.д.в., I.
Собственные значения и спектральные щели 119условие ||0 ||2=h0,0i= 1, значит, должно выполняться равенство0=1= √ 1, а с другой стороны, нам необходимо, чтобы выполнялось условиеlP1TT= 1.j = h , 1i = 1, что требует выполнения равенстваljBack to Fourier8Чтобы проверить равенства (1.12.6), запишем(Из серии «Фильмы, которые не вышли на большой экран».)p0 i=1lp (j)p0 (j)=j=0Когда p = p0 , правая часть равна1lj=0p − p0exp 2 ij .l−11 lP1 = 1. В противном случае, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
