А.Н. Ширяев - Вероятность-1 (1115330), страница 24
Текст из файла (страница 24)
далее с теоремой !). 3. Следующая теорема описывает широкий класс марковских цепей, обладающих так называемым свойством эргодичности: пределы я! = (пп р,," не только существуют, не зависят от ), образуют распределение вероятностей (я! > О, 2 я! = 1), но и таковы, что ау > 0 при всех ! ! (такие распределения называются зргодическими; подробнее см. $3 в гл. Ч111). Теорема 1 (эргодическая теорема). Пусть Р= )!Р))!! — матрица "ереходных вероятностей марковской цепи с конечным множеством состояний Х = (1, 2, ..., )Ч). а) Если для некоторого лэ и)!и р!"') >О, )! (21) (в предположении, что !Реэ+ ри — 1( <! ). Отсюда видно, что если элементы матрицы )р таковы, что (рее + р)!— — 1( < 1 (в частности, если все вероятности перехода рн положительны), то прил- со ГЛ.
). ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ и! Л~~ кл Рл ! Доказательство. а) Обозначим т( ) =поп р("), ); ()' (24) М(л) = гпах р(".). ! =,. (! . Поскольку (л+ () ~ (л) Рц лл~ Р' Р; а (25) то откуда т(л) < гп(л+(), и аналогично М(.") > М(."+ ). Поэтому дяя доказательства утверм(денйя (23) достаточно показать, что М(.") — т(л)- О, и- оо, у=1, ...
Ф. ! ! Пусть е = п)1п(! Р(,".') > О. Тогда (лЕ) ~р(о) () ~] (о) . ()] () ! ~Ч,'Р()р() а а л Ч~;~ ] ,(лл) ,(л)] (л) + . (~) л Но р("') — ер(л) > О, поэтому (лл+л) (л) ~ ~ ( (лл) (л)] (2л) (л)( 1 ) + (2л! Рц ' ! л л га )а г! ! Л а и, значит, т(л'+л) >ты)(1-е)+е то найдутся числа к), ..., кн со свойством к! > О, ~ !г! = 1 (22) ! такие, что для каждого 1' ЕХ и любого ! ЕХ (23) Ь) Обратно, если существуют числа л(, ..., кн, удовлетворяющие условиям (22) и (23), то найдется пе такое, что выполнено условие (2!). с) Числа (к(, ..., кл) из а) удовлетворяют системе уравнений ф )2.
МАРКОВСКИЕ ((ЕЛИ. ЭРГОЛИЧЕСКАЯ ТЕОРЕМА !47 Аналогичным образом М(ло+л) (Моиг! е1+г (эл) ! - ! ( '! 'Р(! Объединяя эти неравенства, получаем М(ла+л) (лл+л) (М(л) (л))(1 ! ! ' ! ! и, следовательно, М(ела+а) (ела+а) ( ( (л) ( ) ! ! (а) ( ( М(л) О!) ( (1 )(л/ла)-! — я! ° — - — е т.е, сходимость р, к предельным значениям я;, происходит с геометри(л) ческой скоростью. Ясно также, что т(л) >т(л') >е>0, п>по и, значит, я)>0.
! Ь) Условие (21) нейосредственно следует из (23), поскольку число состояний конечно и гО > О. с) Уравнения (24) вытекают из (23) и (25). П 4. Система уравнений (ср. с (24)) х;=~~! х р;, 7=1, ...,А! а (24*) играет большую роль в теории марковских цепей. Всякое ее неотрицательное Решение (((=(Ч(, ..., Чн), УдовлетвоРЯющее Условию 2 Ч =1, л принято называть стационарным или инвариантным распределением вероятностей для марковской цепи с матрицей переходных вероятностей 11Р()(1 Объяснение этого названия состоит в следующем. Возьмем РаспРеделение (',)=(Ч(, ..., Чн) в качестве начального, т.
е. пусть р)=Ч;, 7=1, ..., А(. Тогда Р! д ЧаРа! =Ч! (() % ~ а и вообще р,. ) =Ч;. Иначе говоря, если в качестве начального распреде(л) пения взять (г = (Ч), ..., Чн), то это распределение не будет изменяться Итак, по некоторой подпоследовательности (пв) М л — т л — 0 при ! ! и,)- оо. Но разность М вЂ” т монотонна по п, а значит, М( — т( -+0 (л) (л) (л) (л) ! ! при и- оо. Если обозначить )г! = (пп т("', то из полученных оценок вытекает, что л ! для п>по ГЛ. 1. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ 148 со временем, т.
е. для любого й РК.=))=РК.=)), )=),...,А. (л) я) х караг = ° ° ° =~ яар л)' а а и поскольку р(7 -+я;, то к) —— ~~',(паву) = я). л Отметим, что стационарное распределение вероятностей (и к тому же единственное) может существовать и для неэргоди ческих цепей. Действительно, если 1 0 01 ' 10 то и, следовательно, пределы!йп рц не существуют. В то же самое время (л) л система д;=~~г, о р;, г'=1,2, л превращается в систему ()) =(гэ.
(ГЭ =(!1 единственное решение (()1, г)э) которой, удовлетворяющее условию ()1+ +г)э=1, есть (1/2, 1/2). Более того, марковская цепь С =(С, © )р) с таким начальным распределением (е=(д), ..., гглг) будет стационарной: совместное распределение вектора (бы Се+1, ..., Сь+() не зависит от е для любого ! (предполагается, что й+! (и). Условие (21) гарантирует как существование пределов гО = !пп р(,".), не зависящих от г, так и существование эргодического распределения, т.
е. распределения (гг), ..., клг) с к > О. При этом распределение (к(, ..., к)г) оказывается также и стационарным распределением. Покажем сейчас, что этот набоР (кн ..., к)т) ЯвлЯетсЯ единслгвенным стационаРным Распределением, В самом деле, пусть (й(,..., й)г) — еще одно стационарное распределение.
Тогда 4 Ш. МДРКОВСКИН ЦЕПИ. ЭРГОДИЧКСКЛЯ тКОПКМА !49 Отметим также, что для рассмотренного выше примера в п. 2 система (24ь) с х; = Ч; имеет вид Чо = Чо Рш + Ч ! Р1о Ч! =Чоро1 + Ч1 Рн откуда, учитывая условие Чо+Ч! = 1, находим, что единственное стационарное распределение (Чо, Ч!) совпадает с уже найденным: ! — Р! ! ! — Рго 2 — рсо — р|1' ! 2 — рш — р!~ ' Рассмотрим теперь некоторые следствия, вытекающие из зргодической теоремы. Пусть А — некоторая группа состояний, А С Х, и /А(х) = (О, хфА.
Введем величину и („) !А(со)+ "+!А(4 ) и+1 — долю времена, проводимого частицей в множестве А. Поскольку Е[!А(бь) [Ео =!] = Р(бь бА [Со =!) = ~~ р! ! (= Р[~!(А)), /ел то Е [ил(п) [Ео = !] = — ~~~ р~~~(А) о=о и, в частности, ь Е[и1;!(и) [Ео=!] = — ~', р1;!. о=о Из анализа известно (см. также лемму ! в $ 3 гл. !У), что если послеао+" +ал (ь! довательностьа„- а,то о "' — а,п- со. Позтомуесли р!.1- я, и+! Ч !' й — ~со, то Е имя(п) -+ 4г;, Еил(п) — ~ ял, где ял = ~~~ 4гр /ЕА йпя эргодических цепей на самом деле можно доказать большее, а именно, что для величин!А(бо), ..., /А(6,), ...
справедлив Закон больших чисел. Если Ео, Е!, „, — конечная эргодическая марковская цепь, то для всякого е) О, любого множества А сХ и ГЛ. Ь ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ произвольного начального распределения РЦил(п) — ял/ >е) О, и- оо. (26) Прежде чем переходить к доказательству, заметим, что непосредственное применение результатов $ 5 к бернуллиевским величинам !л(Со), ... ..., (л(С„), ... невозможно, поскольку они, вообще говоря, являются зависимыми.
Однако доказательство можно провести по тому же пути, что и в случае независимых величин, если снова воспользоваться неравенством Чебышева и тем обстоятельством, что для эргодических цепей с конечным числом состояний найдется такое О < р <!, что [р; г — яю)<Ср". (27) Рассмотрим состояния ю и у (которые могуг и совпадать) и покажем, что для е>О Р(~ юй(п) — яю~> ~~ =ю) (28) В силу неравенства Чебышева Р(!ю Гй(п) — яю! >с~(о=ю) < ЕЦиЮюТ(п) — кю!э !бо=ю) е Поэтому надо лишь показать, что Е[[РЮюз(п) — яю1з)(о=ю)- О, и оо. Простой подсчет показывает, что ЕЦРЮюТ(п) — кю[~ / 4о = ю) = Е~ ~~ (!Юют((ь) — яю)~ !4о=ю') = — ~~, ~ и,'~", э=о э=о ю=о где пю(ю' = Е([)юй(6)Уюют(сю)1 Ыо = ю) — яю Е [Уюл(сь)!~о = ю]- з=пйюп(й, у) и Ю=/й — ([. В силу (27) р,," =яюю Рею,".', [ею,".ю!<Ср".
Поэтому ~пю,'.,'гюг[ < С, [р'+ р'+ р'+ р'), $!2. МАРКОВСКИЕ !!ЕПИ. ЭРГОДИЧЕСКАЯ ТЕОРЕМА 151 где С~ — некоторая постоянная. Следовательно, л и л л , Х ~~ Л),ге< С', ~, ~ !р'+р'+р»+р') < »=о !=о ( ) »=о !=о 4С! 2(л+1) 8С! (л+ !)з 1- р (л+!)(1- р) откуда и следует справедливость соотношения (28), из которого очевидным образом вытекает требуемое соотношение (26). Б. В $9 длЯ слУчайного блУжданиЯ 5о, 5п ..., поРожденного схемой Бернулли, были выведены рекуррентные уравнения для вероятностей и математических ожиданий времени выхода на ту или иную границу.
Аналогичные уравнения сейчас будут выведены и для марковских цепей. Пусть с = (со, сп ... ) — марковская цепь с матрицсй переходных вероятностей !1р!!!) и фазовым пространством Х=(О, Ы, ..., ~А!). Пусть А и  — два целых числа, -М < А < О < В < М, и х е Х. Обозначим через Я»4 ! множество тех траекторий (хо, хп ..., х»), х; е Х, которые впервые выходят из интервала (А, В) через верхнюю границу, т. е.
покидают множество (А, В), попадая в множество (В, В+ 1, ..., Л1). Положим для А<х<В В»(х) =Р(((о, ". 6) ЕЯ»+! ~4> =х). С целью отыскания этих вероятностей (первого выхода марковской цепи из множества (А, В) через верхнюю границу) воспользуемся методом, примененным при выводе обратных уравнений. Имеем В»(х) = Р(((о, , ~») Е Я»» !)4о = х) = Ртр((4о, "., (») ЕЯ»+!!(о=х, 6 =У), У где, как нетрудно убедиться, опираясь на марковское свойство и однород- ность цепи, Р((Со, ", С») Е Я»+! ~ Со = х, ~6 = у) = = Р((х, у, Ст, ..., С») Е Я»„.1 ) Со = х, С! =У) = = Р((у, сз, ..., с») Е Я»)с! = У) = =Р((у, сь ..., с» !)еЯ»!со=у) =В»-)(у). Поэтому для А < х < В и 1 < й < л Д(х) =~ р,„Д 1(у). 152 ГЛ.
1. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ Прн этом ясно, что Д(х) = 1, х = В, В + 1, ..., М, рв(х)=0, х= — АГ, ..., А. тв(х) =! + ~~~ тв ~ (у) руу у (здесь 1<А<а, А <х<В). При этом тв(х)=0, хк(А, В). Понятно, что если матрица переходных вероятностей задается формулой (!!), то уравнения для ов(х), Д(х) и тв(х) превращаются в соответствующие уравнения из $9, где они получены, по существу, тем же самым методом, что и здесь. Наиболее интересны применения выведенных уравнений в предельном случае, когда блуждание осуществляется неограниченно во времени.
Так же, как и в $9, соответствующие уравнения можно получить формальным предельным переходом из выведенных выше уравнений, полагая й- со. Для примера рассмотрим марковскую цепь с состояниями (О, 1, ..., В) и переходными вероятностями Рга = 1, Рва = 1 и для ! <!< — ! =( р~>0, )=1+1, г;, 1=1, д;>О, г=( — 1, где р;+О+в;=1. Этой цепи соответствует граф lв-1 ! О Аналогичным образом выводятся и уравнения для ов(х) — вероятностей первого выхода из интервала (А, В) через нижнюю границу Пусть ге=пни(0<1<А: 4~ й(А, В)), причем ту =й, если множество ()=а. Тогда тот же самый метод, примененный к тв(х)=Е(гв!со=х), приводит к следующим рекуррентным уравнениям: ф!2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
