Цепи Маркова (1121219), страница 25
Текст из файла (страница 25)
соотношение (1.12.29). Следовательно,матрицы P и PT имеют ортонормированный базис из собственных векторовотносительно h · , · i . Далее, P и PT имеют один и тот же действительный спектр, и их собственные значения p , представленные совместносо своими кратностями и в убывающем порядке, удовлетворяют условию(1.13.3). Тогда лапласианы L(P) = I − P и L(P T) = I − PT = L(P) T (укоторых собственные векторы те же, что и у P и P T , соответственно) имеютсобственные значения p = 1 − p ; взятые вместе со своими кратностямии расположенные в возрастающем порядке, эти собственные значенияудовлетворяют соотношениямl−16 2.(1.14.1)Из неравенств (1.14.1) следует, что L(P) и L(P T) определяют эрмитовонеотрицательно определенное преобразование в R l и Cl относительно скалярного произведения h · , · i .
Собственный вектор преобразования L(P),соответствующий наименьшему собственному значению 0, есть ; дляL(PT) это 1T .Запишем неравенство Пуанкаре для 1 в общем виде. Положимrij =i pij ,i, j = 1, . . . , l.(1.14.2)Воспользуемся симметрией вида rij = rji , которая имеет место в силуобратимости. Далее, для любых i, j = 1, . .
. , l зафиксируем путь Γ ij == (i0 → i1 → . . . → im) вдоль диаграммы, выходящий из i и заканчивающийся в j, причем каждая стрелка встречается не более одного раза,т. е. i0 = i, im = j, pis ,is+1 > 0 ∀ s = 0, . . . , m − 1 и каждая стрелка ee== (ei → ej) появляется не более одного раза среди es = (is → is+1). В силунеприводимости такой путь всегда существует (мы называем такой путь13 Ср.с названием фильма Вуди Аллана «Manhattan Murder Mystery»151|Γij | =m−1Xs=01,ris is+1Γij ∈ G .(1.14.3)В этой постановке неравенство Пуанкаре принимает вид1>maxbe= (bi→bj)XΓij ∈G1(Γij 3 be) |Γij |i j−1.(1.14.4)Выражение в правой части неравенства (1.14.4) зависит от выбора путейΓij (как мы отметили в примере 1.12.1, подходящий выбор — это геодезические линии). В общем случае выражение в правой части измеряет «степеньнеприводимости» матрицы P; удачный выбор G оказывает большую по1мощь.
В случае равномерного стационарного распределения=1Tlправая часть неравенства (1.14.4) совпадает с правой частью неравенства(1.13.6).При доказательстве неравенства (1.14.4) нам будет удобно работатьс лапласианом L(P); для краткости обозначим его просто L. (Выгода отработы с L(P) связана с тем фактом, что собственный вектор, соответствующий наименьшему собственному значению L(P) T , есть 1T .) Собственноезначение 1 можно охарактеризовать как наименьшее собственное значение матрицы L при сужении ее действия на ортогональное дополнениек вектору 1. (Здесь и далее термин «ортогональность» и все связанныес ним понятия подразумеваются относительно взвешенного скалярногопроизведения h · , · i .) Мощное средство, применимое в данной ситуации,это так называемая вариационная (или минимаксная) характеризациясобственных значений эрмитовой матрицы, а именно теорема Куранта—Фишера.
На самом деле эта теорема является обобщением болеераннего результата, часто называемого теоремой Рейлиха —Ритца, для наших целей вполне достаточно воспользоваться этой последней теоремой.Суть в том, что согласно теореме Рейлиха—Ритца собственное значение1 является решением задачи минимизации в терминах величин hLx, xi ,||x|| = hx, xi и hx, 1i :1= min[hLx, xi : ||x|| = 1, hx, 1i = 0] =h hLx, xii= min: x 6= 0, hx, 1i = 0 .2||x||(1.14.5)Глава 1. Цепи Маркова с дискретным временемВ нашей ситуации удобно использовать формулуhLx, xi =l1 X2i,j=1 x1(xi − xj) 2 rij ,x = ...
∈ Rl ,(1.14.6)xlкоторая следует из соотношений L = I − P и rij = i pij . Заметим, что правая часть формулы (1.14.6) не изменится, если выполнить преобразованиеx 7→ x + c1, т. е. если прибавить постоянную c к компонентам x 1 , . . . , xl .Но именно такая операция естественным образом позволяет получить изпроизвольного вектора x вектор, ортогональный к 1:hx, 1i.h1, 1i(1.14.7)l1 X(xi − xj) 22V (ϕ) =1= min||ϕ||2i,j=1X ri is s+1e= (is →is+1) ∈Γijris is+1 1/ 2ϕ (e)i2(1.14.12)i jи применим неравенство Коши—Шварца к внутренней сумме:hXe= (is →is+1) ∈Γij ri is s+1ris is+1 1/ 2ϕ (e)i26 |Γij |Xris is+1 (ϕ (e)) 2 .e= (is →is+1) ∈Γij(1.14.8)i,j=1 ϕ1i.. ∈ Rl , ϕ 6∝ 1 =:ϕ=.ϕlh E (ϕ)i= min: ϕ — действительная функция .V (ϕ)(1.14.9)Здесь вектор ϕ определяем как функцию ϕ : i 7→ ϕ (i), где ϕ (i) = ϕ i , i == 1, .
. . , l (ϕ будет играть роль функции «потенциала»). Далее,E (ϕ) =l1 X(ϕ (i) − ϕ (j)) 2 rij ,2V (ϕ) =l1 X(ϕ (i) − ϕ (j)) 22(1.14.10)i,j=1иi,j=1l h1 X2Получаем, чтоi j.Это равенство сохранится, если к компонентам прибавить постоянную.Заключаем, что соотношение (1.14.5) можно переписать в видеh hϕ, Lϕie∈Γijгде для стрелки e = (is → is+1) величина ϕ (e) определяется как разностьϕ (is+1) − ϕ (is). Затем перепишем равенство (1.14.11) в видеС другой стороны, для такого действительного вектора x, что hx, 1i == 0, выполняется равенство||x||2 =153При помощи уравнения (1.14.9) можно легко доказать неравенство(1.14.4). А именно, для любых i, j = 1, .
. . , l запишем сумму вдоль траектории Γij :L−1XXϕ (i) − ϕ (j) =(ϕ (ir+1) − ϕ (ir)) =ϕ (e),r=1Thx + c1, 1i = 0 тогда и только тогда, когда c = −§ 1.14. Геометрическая алгебра цепей Маркова, III. Границы Пуанкаре и Чигераi j.(1.14.11)V (ϕ) 6=l1 X2i,j=11 X2be= (bi→bj)i j |Γij |rbi,bj (ϕ (be)) 2Xris is+1 ϕ (e) 2 =e= (is →is+1) ∈ΓijX|Γij |eΓij : Γij 3bi j6 E (ϕ)maxbeXeΓij : Γij 3b|Γij |i j.(1.14.13)e и воспользоваться соотношениемЕсли взять теперь максимум по b(1.14.5), получим неравенство (1.14.4).Доказательство оценки (1.13.12).
Как и выше, докажем более общее неравенство. Пусть P — неприводимая и апериодическая матрица.Мы знаем, что −1 не является собственным значением матрицы P (ипостараемся отделить собственные значения от −1). В сущности, величина −1 = 1 − | l−1 | измеряет, насколько «далека» наша ц.м.д.в. отпериодической цепи с периодом два (когда −1 является собственным значением).
Периодическая ц.м.д.в. должна иметь двухдольную диаграмму,где пространство состояний распадается на два такие подмножества, чтовсе стрелки направлены из одного подмножества в другое. Это означает,что каждая петля в периодическом случае должна состоять из четногочисла стрелок.Поэтому для апериодической матрицы P выберем для любого состояния i = 1, . .
. , l простую петлю Σi = (i0 → i1 → . . . → im−1 → im)152154Глава 1. Цепи Маркова с дискретным временемс нечетным числом ребер, проходящую через i = i0 = im . Пусть, каки ранее, S обозначает множество выбранных петель. Аналогично формуле(1.14.3) определим вес петли как§ 1.14. Геометрическая алгебра цепей Маркова, III. Границы Пуанкаре и ЧигераА именно, получаемE ϕ2 =l1X4i=1|Σi |Q =m−1Xs=0В этих обозначениях оценка для1ris is+1−1,Σi ∈ S .(1.14.14)6l1Xi |Σi |4i=1iXe= (is →is+1) ∈ΣiX1=4приобретает вид−1>2maxbe= (bi→bj)hXΣi ∈S1(Σi 3 be) |Σi |i(−1) sX(1.14.15)ris is+1[ϕ (is) + ϕ (is+1)]ris is+126be= (bi→bj)(в силу неравенства Коши—Шварца) =X[ϕ (bi) + ϕ (bj)] 2 rbi bj|Σi | i == (E ϕ + hϕ, Pϕi )i−1rris is+1 [ϕ (is) + ϕ (is+1)] 2e= (is →is+1) ∈Σi2155X|Σi |ieΣi : Σi 3b(в силу соотношения (1.14.16).Σi : Σi 3be(1.14.17)В правой части можно взять максимум:и зависит от выбора множества S .Чтобы доказать неравенство (1.14.15), начнем со следующего очевидного тождества:E ϕ2 6 X1(E ϕ2 + hϕ, Pϕi ) max|Σi |Q2beΣi : Σi 3bei:Σi ∈ S.(1.14.18)Далее, деление на E ϕ2 = ||ϕ||2 приводит к неравенствуllX1 X(ϕ (i) + ϕ (j)) 2 rij =(ϕ (i)) 22i,j=1i=1i+lXi,j=12ϕ (i) ϕ (j)rij = E ϕ + hϕ, Pϕi ,(1.14.16)где E обозначает математическое ожидание относительно стационарного ϕ1распределения , а функция ϕ : i 7→ ϕ (i) определена как вектор ϕ = ...
,ϕlгде ϕi = ϕ (i) (прием, использованный ранее). Тогда если Σ i — это петляс началом и концом в i, то запишемϕ (i) =1(ϕ (i0) + ϕ (i1)) 2 − (ϕ (i1) + ϕ (i2)) 2 + . . . + (ϕ (im−1) + ϕ (im)) 2 ;2здесь пригодилась нечетность m. Как и при доказательстве неравенстваПуанкаре, в игру вступает неравенство Коши—Шварца. Xhϕ, Pϕi> −1 + 2 max|Σi |Q2||ϕ||beΣi : Σi 3bei:Σi ∈ S−1,и минимаксная характеризация Рейлиха—Ритца (1.13.3) приводит к оценке(1.14.15).Если хотите доказать свою правоту, интегрируйте по частям.Если это не помогает, используйте неравенство Коши—Шварца.(Из серии «Так говорил суперлектор».)Доказательство неравенства Чигера.
Вновь полезно доказать неравенство более общего вида, чем (1.13.18), предполагая, что матрица P == (pij) неприводима и обратима относительно произвольного положительного инвариантного распределения = ( i), и рассматривая симметричныйвес (1.14.3). Для множества состояний S ⊂ {1, . . .
, l} определим потокQ(S, Sc) формулойXQ(S, Sc) =rij ,(1.14.19)(i,j); i∈S,j∈Sc156Глава 1. Цепи Маркова с дискретным временем(S) =XQ(S, Sc) ,(1.14.20)i.(1.14.21)i∈SВ этой более общей постановке неравенство Чигера утверждает, чтоh26216 2h.(1.14.22)Верхняя граница в соотношении (1.14.22) получается немедленно.А именно,Pдля заданного множества состояний S ⊂ {1, . . . , l}, где 0 66 (S) = i∈S i 6 1/2, положим((Sc),i ∈ S,(1.14.23)S (i) =− (S), i ∈ Sc .||+ 2(=(i) , i = 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
