Лекция по цепям Маркова (1134070), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

е. j=1 πij = 1 для любого i = 1, . . . , s. Рассмотрим две строки матрицы π с фиксированными номерами α и β . ПоложимXS + (α, β) =(παk − πβk ).(1.15)k : παk −πβk >0Имеют место следующие утверждения:1) S + (α, β) = S + (β, α);2) если найдется номер столбца j ∈ {1, 2, .

. . , s} такой, что πij > δ > 0 для всехi = 1, 2, . . . , s, тоS + (α, β) 6 1 − δ.(1.16)5Доказательство. Заметим, чтоXS + (β, α) =(πβk − παk ) = −k : πβk −παk >0X(παk − πβk ).k : παk −πβk 60Понятно, что из суммы можно исключить слагаемые, равные нулю, т. е.XS + (β, α) = −(παk − πβk ).(1.17)k : παk −πβk <0Разобьем множество {1, . .

. , s} на два подмножестваK+ = k : παk − πβk > 0 , K− = k : παk − πβk < 0(вариант разбиения, конечно, зависит от α и β). В этих обозначениях (1.15) и (1.17)запишутся какXXS + (α, β) =(παk − πβk ),S + (β, α) = −(παk − πβk ).k∈K+k∈K−Отсюда++S (α, β) − S (β, α) = Xk∈K+sXX (παk − πβk ) = 1 − 1 = 0+(παk − πβk ) =k=1k∈K−в силу стохастичности матрицы π, таким образом, равенство S + (α, β) = S + (β, α)доказано.Далее,1=sXk=1παk =Xπαk +k∈K+следовательно,S + (α, β) =Xπαk ,παk = 1 −Xπαk −k∈K+k∈K−XX(παk − πβk ) = 1 −k∈K+k∈K−Xπαk ,k∈K−Xπβk .(1.18)k∈K+Пусть номер столбца j взят из второго утверждения леммы.

Очевидно, что, каковбы ни был этот номер j ∈ {1, . . . , s}, либо j ∈ K+ , либо j ∈ K− . Если j ∈ K+ , тов силу неотрицательности всех элементов матрицы π имеемXXπβk > πβj > δ,παk > 0.k∈K+Если j ∈ K− , то наоборотXk∈K−παk > παj > δ,Xπβk > 0.k∈K+k∈K−В любом случае в (1.18)Xk∈K−παk +Xπβk > δ.k∈K+Подставляя эту оценку в (1.18), получаем неравенство (1.16).6Перейдем к теореме Маркова.Теорема 1.1. Пусть найдется натуральное число n0 такое, что матрица перехода π (n0 ) за n0 шагов цепи Маркова имеет хотя бы один столбец, не содержащий нулевых элементов.

Тогда:(n)1) для любого j = 1, . . . , s существуют финальные вероятности pj = limn→∞ πij ,которые не зависят от номера i начального состояния;Ps2) вероятности pj > 0, j = 1, 2, . . . , s, образуют распределение, т. е. j=1 pj = 1;3) для любого j = 1, 2, . . . , s и для любого m = 1, 2, . . . имеет место равенствоpj =sX(m)(1.19)pk πkj ;k=14) финальные вероятности также являются предельными значениями для распределения на n-м шаге,pj = lim P (ξn = xj ),(1.20)j = 1, .

. . , s.n→∞Доказательство. Для j = 1, . . . , s ведем обозначения(n)Mj(n)(n)= max πij ,(n)mj16i6s= min πij ,16i6sтогда для любых i = 1, 2, . . . , s(n)0 6 mj(n)(n)6 πij 6 Mj(1.21)6 1.Применим к матрице π (n+1) уравнение (1.13), получим(n+1)Mj= max16i6s(n+1)πij= max16i6ssX(n)πik πkj6(n)Mjk=1max16i6ssX(n)πik = Mjk=1(n)max 1 = Mj16i6sв силу стохастичности матрицы перехода за один шаг. Таким образом, для каж(n)дого фиксированного j = 1, .

. . , s последовательность {Mj }n=1,∞ не возрастает(n)и ограничена снизу, следовательно, существует предел Mj∗ = lim Mj . Аналоn→∞(n)гичные рассуждения доказывают, что последовательность {mj }n=1,∞ не убывает(n)и существует m∗j = lim mj . Очевидно, Mj∗ > m∗j .n→∞Если мы покажем, что два указанных предела совпадают, m∗j = Mk∗ = pj , то(n)в силу (1.21) этого будет достаточно для того, чтобы pj = limn→∞ πij .Рассмотрим матрицу π (n+n0 ) , где n0 задано в условии теоремы.

Имеем(n+n0 )Mj(n+n0 )− mj(n+n0 )= max πij16i6s(n+n0 )− min πij16i6s(n+n0 )= παj(n+n0 )− πβj,(1.22)где мы обозначили через α номер строки, на которой достигается максимум, и черезβ — номер строки, на которой достигается минимум (разумеется, номера α, β разныедля разных n и j, но до некоторого момента мы считаем n и j фиксированными).Вновь применим уравнение (1.13): XnXX (n )(n0 )(n0 )(n)(n )(n)(n+n0 )(n+n0 )(παk −πβk )πkj =+(παk0 −πβk0 )πkj , (1.23)παk−πβk=k∈K+k=17k∈K−где мы воспользовались обозначениями леммы 1, заменив в ней матрицу π на такжестохастическую матрицу π (n0 ) , другими словами, в нашем случае(n )(n )(n )(n )K+ = k : παk0 − πβk0 > 0 ,K− = k : παk0 − πβk0 < 0 .Оценим сверху каждую из двух сумм в правой части (1.23).

Для k ∈ K+ мы(n )(n )(n)(n)имеем оценку παk0 − πβk0 > 0, тогда в силу πkj 6 MjX(n )(n )(n)(n)X(παk0 − πβk0 )πkj 6 Mj(n )(n )(παk0 − πβk0 ).k∈K+k∈K+(n )(n )Для k ∈ K− множитель παk0 − πβk0 отрицателен, поэтому для оценки величины(n )(n )(n)(n)(n)(n)(παk0 − πβk0 )πkj сверху нам придется оценить множитель πkj снизу: πkj > mj .ТогдаX (n )X (n )(n )(n)(n)(n )(παk0 − πβk0 )πkj 6 mj(παk0 − πβk0 ).k∈K−k∈K−Подставим полученные оценки в (1.23) и затем учтем равенство (1.22), в итоге получимX (n )X (n )(n )(n)(n )(n+n0 )(n+n0 )(n)(παk0 − πβk0 ).(παk0 − πβk0 ) + mjMj− mj6 Mjk∈K+k∈K−В обозначениях леммы 1 первая сумма в правой части последнего неравенства естьS + (α, β).

Преобразуем вторую сумму аналогично тому, как мы поступали при доказательстве леммы 1:XX (n )(n )(n )(n )(παk0 − πβk0 ) =(παk0 − πβk0 ) =(n )k∈K−(n )k : παk0 −πβk0 60X=−(n )(n )(n )(πβk0 − παk0 ) = −S + (β, α) = −S + (α, β),(n )k : πβk0 −παk0 >0где в последнем равенстве мы учли первое утверждение леммы 1. Таким образом,(n+n0 )(n+n0 )(n)(n)(n)(n) Mj− mj6 Mj S + (α, β) − mj S + (β, α) = Mj − mj S + (α, β).По условию теоремы в матрице π (n0 ) найдется столбец, в котором нет нулевыхэлементов, т. е. при некотором j0(n)(1.24)δ = min πij0 > 0.16i6s(n)Используем оценку (1.16) S + (β, α) 6 (1 − δ) и учтем, что Mj(n+n0 )Mj(n+n0 )− mj(n)6 Mj(n) − mj(1 − δ).(n)− mj> 0, получим(1.25)Заметим, что в последнем неравенстве уже нет номеров α, β, зависящих от n и j,и мы можем утверждать, что это неравенство верно при всех n = 1, 2, . .

. и j =81, . . . , s. Перейдем в обеих частях неравенства к пределу при n → ∞ и фиксированном j:Mj∗ − m∗j 6 (Mj∗ − m∗j )(1 − δ).Если Mj∗ − m∗j > 0, то, сокращая на Mj∗ − m∗j , получаем 1 − δ > 1, т. е. δ 6 0, чтоневозможно вследствие (1.24). Поэтому Mj∗ − m∗j = 0. Пункт 1 теоремы доказан:существует(n)pj = lim πij ,j = 1, . .

. , s.n→∞Пункты 2, 3 теоремы получаются путём перехода к пределу при n → ∞ в равенствахssXX(n)(n+m)(n) (m)πij ,πij=πik πkj1=j=1k=1соответственно. Пункт 4 также вытекает из предельных соотношенийlim P (ξn+1 = xj ) = limn→∞n→∞sX(n)πij P (ξ1= xi ) =sXpj ai = pj ,j = 1, . . . , s.i=1i=1Здесь мы учли условие нормировки начального распределения:ма доказана.Psi=1ai = 1.

Теоре-Замечание 1.3. Если дополнительно потребовать, чтобы вся матрица π (n0 ) не(n )содержала нулевых элементов, т. е. πij 0 > 0 для всех i, k = 1, . . . , s, то(n )(n )πij 0 > δ = min πij 0 > 0,16i,j6s(n0 )поэтому mj(n)> δ, следовательно, mj> δ для всех n > n0 в силу неубывания(n){mj }n=1,∞ .(n)последовательностиТаким образом, pj = limn→∞ mj > δ > 0 длявсех j = 1, . . .

, s. Другими словами, все финальные вероятности отличны от нуля.Замечание 1.4. Равенство (1.19) можно интерпретировать следующим образом:если начальное распределение совпадает с финальным, aj = pj , j = 1, 2, . . . , s, тоэто распределение сохраняется на любом шаге цепи Маркова, P (ξn = xj ) = pjдля любого n = 1, 2, . . . .

Такое распределение называется стационарным, и мыполучили, что финальное распределение (если оно существует) с необходимостьюявляется стационарным.Пусть динамика некоторой физической системы происходит по законам цепиМаркова, т. е. в каждый из моментов времени t = 1, 2, . . . система может находитьсяв одном из состояний xj , j = 1, .

. . , s, а переходы от одного состояния к другомупроисходят случайным образом с вероятностями, заданными матрицей π. Зафикси(n)руем некоторое состояние xj и введем случайную величину τj , равную количествумоментов времени из t = 1, 2, . . . , n, в которые система пребывала в состоянии xj .(n)Тогда τj /n — это доля времени, которое цепь Маркова провела в состоянии xj .(n)Представим τjв виде(n)τj=nX(m)χj,(m)χjm=19(1, если ξm = xj ,=0, если ξm 6= xj ,(n)другими словами, τjесть количество тех шагов, на которых произошло событие(n)ξm = xj . Тогда математическое ожидание случайной величины τj /n равно(n)nnτj1 X1 X(m)M χj =P (ξm = xj ).=Mnn m=1n m=1(1.26)(n)Покажем, что если P (ξm = xj ) → pj при m → ∞, то M τj /n → pj .

Для этоговоспользуемся следующим простым утверждением математического анализа.Лемма 1.2. Пусть последовательность действительных чисел {am }n=1,∞ сходится к a при m → ∞. Тогдаa1 + · · · + an→ a,nn → ∞.Доказательство. Выберем произвольное натуральное m0 < n и запишем цепочку соотношений n 1 X a1 + · · · + an(am − a) 6− a = nn m=1 m0n S1 1 X1 XS26 (am − a) =(am − a) + +.(1.27)n m=1n m=m +1nn0Оценим величины S2 и S1 , пользуясь сходимостями am → a и 1/n → 0 соответственно.Возьмем произвольное ε > 0 и зафиксируем его.

В силу сходимости am → aнайдется номер m0 = m0 (ε) такой, что |am − a| < ε/2 для всех m > m0 . Тогда длялюбого n > m0 величина S2 оценивается какmmX Xεε|am − a| 6 (n − m0 ) < n ,(am − a) 6S2 = 22m=m +1m=m +100поэтому S2 /n < ε/2 при n > m0 .P m0Рассмотрим первое слагаемое в правой части (1.27).

Характеристики

Список файлов лекций