Лекция по цепям Маркова (М.Л. Сердобольская) (1119984), страница 2

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

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

. , 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). Пусть S1 = m=1(am − a).В силу того что 1/n → 0 при n → ∞, найдется номер N1 , для которого 1/n < ε/2S1при всех n > N1 .

Заметим, что N1 зависит только от S1 и ε. Далее, величина S1определяется только номером m0 (и, разумеется, последовательностью {am }n=1,∞ ,но ее мы считаем фиксированной), а номер m0 зависит только от ε. Таким образом,N1 = N1 (ε).Теперь мы должны взять номера n, при которых оба слагаемых в правой части (1.27) малы. Положим N = max(N1 , m0 ).

Поскольку N1 и m0 зависят только отε, мы имеем N = N (ε) Тогда для n > N (ε) S1 a1 + · · · + anS26−a+6 ε.nnnЛемма доказана.10(n)Теорема 1.2. Пусть P (ξm = xj ) → pj при m → ∞, тогда M τj /n → pj .Доказательство. Положим в лемме 2 am = P (ξm = xj ) и a = pj = lim am .m→∞Из (1.26) получаем(n)nτj1 XP (ξm = xj ) = lim P (ξm = xj ) = pj .lim M= limm→∞n→∞n→∞ nnm=1(1.28)Теорема доказана.Можно показать, что если цепь Маркова имеет строго положительные финальные вероятности, то(n)τjP−→ pj ,(1.29)n→∞nв этом соотношении имеется в виду сходимость последовательности случайных ве(n)личин τj , n = 1, 2 . .

. , по вероятности.Рассмотрим физическую интепретацию полученных результатов. Предположим,что мы имеем множество (ансамбль) систем, динамика которых происходит по правилам цепи Маркова и определяется матрицей переходных вероятностей. Будемсчитать, что текущий момент времени достаточно удален от начального, и распределение уже пришло к стационарному: P (ξn = xj ) = pj для каждой из систем.Тогда в частотной интерпретации вероятность pj примерно равна доле систем, находящихся в данный момент времени в состоянии xj .Утверждения (1.28) и (1.29) говорят о том, что доля времени, которое одна фиксированная динамическая система пребывает в состоянии xj в процессе своей динамики, приблизительно равна среднему количеству систем в ансамбле, пребывающих в этом состоянии в один фиксированный момент времени.

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

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