Вероятность - Ширяев А.Н.
Скачать (прямая ссылка):
Рис. 22. К обратному уравнению.
Рис. 23. К прямому уравнению.
уравнения записываются соответственно следующим образом:
p(k+i) = p(k).p> (17)
p(A+l)=p.p(ft). (18)
Аналогично для (безусловных) вероятностей pW получаем, что
р{?+1)=У>р{>% (19)
a
или в матричной форме
§ 12. МАРКОВСКИЕ ЦЕПИ
129
В частности,
(,прямое уравнение) и
]П<*+1) = ]Па! • Р(/г)
(обратное уравнение). Поскольку Р^> = Р, О'-11 = 1П" то из этих уравнений
следует, что
Р*) = Р", п(*'=1Г?-
Тем самым для однородных марковских цепей вероятности перехода за k шагов
р<*> и вероятности р**1 являются -элементами й-х степеней матриц Р и J7,
в связи с чем многие свойства этих цепей можно изучать методами
матричного анализа.
Пример. Рассмотрим однородную марковскую цепь с двумя состояниями 0 и 1 и
матрицей
р _ (Роо Аи \
\Pio PuJ
Нетрудно подсчитать, что
2 - Роо- Рп
I (Роэ + Рп- П" / I -Роо -(I Роо)\
2 - ро0 - рц \ - (1-Рп) 1 Рп )
(в предположении, что | р00 + ри - 1 ! < 1)-
Отсюда видно, что если элементы матрицы Р таковы, что |Poo + Pu - 1 i < 1
(в частности, если все вероятности перехода pi} положительны), то при л-
>-оэ
и, значит,
Таким образом, если |p0o + Pn- 1|<1, то поведение рассматриваемой
марковской цепи подчиняется следующей закономерности: влияние начального
состояния на вероятность нахождения частицы в том или ином состоянии
исчезает с ростом времени (р<?> сходятся к предельным значениям лу, не
зависящим от i и образующим распределение вероятностей л0^г О, л^з^О, Лд
+ л^ 1); если к тому
и (по индукции)
130 ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ
же все элементы ру > 0, то тогда предельные значения я0 >• 0, лх>0.
Следующая теорема описывает широкий класс марковских цепей, обладающих
так называемым свойством эргодичности-, пределы ny = limp!^) не только
существуют, не зависят от i, образуют
п ^
распределение вероятностей /я^^зО, н0 и таковы> 4X0
Uj > 0 при всех / (такие распределения яj называются эргодиче-скими).
Теорема 1 (эргодическая теорема). Пусть Р = \\pij\\ - матрица переходных
вероятностей марковской цепи с конечным множеством состояний Х = {1, 2,
..., N}.
a) Если найдется п0 такое, что
minp</O>0, (21)
то существуют числа я1; ..., nN такие, что
лу > 0, 2п/ = 1 (22)
и для любого i е X
p\f^- П., п^-оо. (23)
b) Обратно, если существуют числа лх, ..., ял,, удовлетворяющие
условиям (22) и (23), то найдется п0 такое, что выполнено
условие (21).
c) Числа (я1; ..., ял) удовлетворяют системе уравнений
п/ = 2 / = 1 > • ¦ •. N- (24)
а
Доказательство, а) Обозначим
т{.'г) = min р\'Р, М{.п) = шах р(.п).
1 ( Ич ' 1 ( нч
Поскольку
рЦ+,'-Ер*р13. <25>
а
ТО
mf+D = min = min V plap<?jmin^] Pia minp<P = т<л),
* * a * a a
откуда и аналогично M)n) 5з УИ/,1+1). Поэтому для
доказательства утверждения (23) достаточно показать, что
о, п^со, )=1 X.
§ 12. МАРКОВСКИЕ ЦЕПИ 131
Пусть е = minp(.'?°' > 0. Тогда t, / 11
Р\Г+п) = = 2 № ]р1аЧ+*2,р?р(а1 =
а а <х
= 21 Рйо> ~гР%)Н1+еРпп)-
а
Но р).Яо) - 0, поэтому
р (я0+я) ^ т(п). ^ |^р(п") _ ер(л>] ер(2д) = т(п) (1 - е) + ер^п\
а
и, значит,
т{па+п) ^ т(я) п _ е) ерВ.я),
Аналогичным образом
Mfa+n) < А^я) (1 - е) + ер)/2я).
Объединяя эти неравенства, получаем
Л4<я"+я> - т)я°+я) < (А4<я) - т1,я)) • (1 - е)
и, следовательно,
д|(*".+ ") _ "(*"•+") ^ (Л1}п> - т<-я)) (1 - е)* I 0, ft -*" сю.
Итак, по некоторой подпоследовательности {цр} М|.я^ - m^-v-0, np-voo. Но
разность М/я) - т}я) монотонна по я, а значит, М^- т)п) -v 0, л оо.
Если обозначить лу = lim т(я), то из полученных оценок слега *
дует, что для л^л0
[р<я> - лу j =ss М<,я) - т<я> < (1 - е)!^"!-1,
т. е. сходимость р(я) к предельным значениям л, происходит с
геометрической скоростью.
Ясно также, что т<.я> 5= т(Яо) е > 0, " ^ п0, и, значит, л^ > 0.
b) Условие (21) непосредственно следует из (23), поскольку
ЧИСЛО СОСТОЯНИЙ КОНеЧНО И Лу>0.
c) Уравнения (24) вытекают из (23) и (25).
Теорема доказана.
4. Система уравнений (24) играет большую роль в теории марковских
цепей. Всякое ее неотрицательное решение (лх, ..., л"), удовлетворяющее
условию ^ла=1, принято называть стацио-
а
парным или инвариантным, распределением вероятностей для марковской цепи
с матрицей переходных вероятностей Цр;у||. Объяснение этого названия
состоит в следующем.
Uc2
ГЛ I ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ
Возьмем распределение (л^.., nN) в качестве начального, Pj = uj. Тогда
РТ = I] napaj = Я/
а
и вообще р^п) ~ л,. Иначе говоря, если в качестве начального
распределения взять (лх лдг), то это распределение не будет
изменяться со временем, т. е. для любого k
Р(Е* = /) = Р(?о = У),
Более того, с таким начальным распределением марковская цепь ? - (?> П.
Р) будет стационарной: совместное распределение вектора ilk, l*+i, не
зависит от k для любого I (предполагается,
что k-\-l^n).
Условие (21) гарантирует как существование пределов я,= = 1 irn р)">, не
зависящих от i, так и существование эргодического
п 11
распределения, т. е. распределения с я/>0. Распределение (ctj, ..., njv)
