А.Н. Ширяев - Вероятность-1 (1115330), страница 23
Текст из файла (страница 23)
Свойство независимости «будущего» и «прошлого», или, что то же, независимость «будущего» от «прошлого» при фиксированном «настоящем», принято называть марковским свойством, а соответствующую последовательность случайных величин Ео, ..., с„— марковской цепью. Таким образом, если «веса» р(ш) элементарных событий задаются формулой (3), то последовательность с = Ко, ..., с„) с с;(ш) = хи будет образовывать марковскую цепь. В этой связи понятно следующее Определение.
Пусть (П, лг, Р) — некоторое (конечное) вероятностное пРостРанство и Е= Ко,..., Е„) — последовательность слУчайных величин со значениями в (конечном) множестве Х. Если выполнено условие (7), то последовательность 4= Ко,..., 4„) называется (конечной)марковской цепью. Множество Х называется фазовым пространством или пространством состояний цепи. Набор вероятностей (ро(х)), хеХ, с ро(х) = =РКо=х) называют начальным распределением, а матрицу 11р»(х, у)11, х уеХ, с р»(х, у)=Р((»=у)б» |=х) — матрицей переходных вероятностей (из состояний х в состояния у) в момент й = 1, ..., л. В том случае, когда переходные вероятности р»(х, у) не зависят от й, р»(х, у) = р(х, у), последовательность С = (Со, ..., Е„) называется однородной марковской цепью с матрицей переходных вероятностей 11 р(х, уИ1. ГЛ. !.
ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ !40 Заметим, что матрица ((р(х, уЦ является сп!охастической: ее элементы неотрицательны н сумма элементов любой ее строки равна единице, ,о(х, у) = 1, х е Х. Будем считать, что фазовое пространство Х состоит нз конечного множества целочисленных точек (Х =(О, 1, ..., А!), Х =(О, ~1, ..., ~Ф~ и т д), н обозначать, согласно традиции, р; = ро(!) н рс, = р(ю, /).
Понятно, что свойства однородных марковских цепей полностью определяются начальными распределениями р; н переходными вероятностямн рьь В конкретных случаях лля описания эволюции цепи вместо явного выписывания матрицы !! р!! 11 используют (ориентированный) граф, вершинами которого являются состояния нз Х, а стрелка РП ;г ъ; идущая нз состояния ! в состояние / н с числом р! над ней, показывает, что нз точки ! возможен переход в точку / с вероятностью р;;.
В том случае, когда рц = О, соответствующая стрелка не проводится. Пример 1. Пусть Х =(О, 1, 2) н 1 О О 1! рс; 11 = !/2 О 1/2 2/3 О 1/3 Этой матрице соответствует следующий граф: !/2 !/2 ! !/3 2/3 Отметим, что здесь состояние О является «поглощающим»с если частица в него попала, то она в нем и остается, поскольку рао =1. Из состояния ! частица с равными вероятностями переходит в соседние состояния О и 2; состояние 2 таково, что частица остается в нем с вероятностью 1/3 н переходит в состояние О с вероятностью 2/3. Пример 2.
Пусть Х=(0, Ы, ..., ~М), ро=1, р,щ=р м я =1 н для !с( < А! р, /=!+1, ру= д, /=! — 1, О в остальных случаях. $!2. МАРКОВСКИЕ ЦЕПИ. ЭРГОЛИЧЕСКАЯ ТЕОРЕМА 14! Переходы, соответствующие такой цепи, можно графически нзобразнть следующим образом (М = 3): -З -2 р-~ р О Эта цепь отвечает исследованной выше игре двух игроков, когда капитал каждого равен М н на каждом шаге первый игрок с вероятностью р выигрывает у второго +! н проигрывает — ! с вероятностью д. Если трактовать состояние 1 как величину выигрыша первого игрока у второго, то достижение состояний М н -М означает разорение второго н первого игроков соответственно, В самом деле, если г1П пз, ..., г)„ — независимые бернуллневскне случайные величины с Р(гд =+1) = р, Р(п; = -1) = д н 5А = гл +...
+ г)ь— величина выигрыша первого игрока у второго, то последовательность 5а, 5И ..., 5„с 5о=О будет образовывать марковскую цепь с ро=1 н матрнцей переходных вероятностей (11), поскольку Р(5а~ы = у~5ь =1ы 5А ~ =(ь и ..., 5~ =И) = =Р(5ь +ПА+) = /(5а =1ы 5ь ~ =!А и ..., 5) =Й) = = Р(5А +ЧА+ь = У!5А = 4) = Р(гд+ч = 1 — (ь). Марковская цепь 5о, 5П ..., 5„ имеет весьма простую структуру: 5а». ~ = 5» + па+ и О < й < а — 1, где пь г)2, ..., и„— последовательность независимых случайных величин. Те же РассУжДениЯ показывают, что если Са, г)п ..., г1, — независимые случайные величины, то последовательность Со, 5, ..., С„с с+ =ба,ъ„), О<А<я-), (12) также образует марковскую цепь.
В этой связи полезно отметить, что так построенную марковскую цепь естественно рассматривать как вероятностный аналог (детерминированной) последовательности х = (ко, ..., х„), управляемой рекуррентнымн соотношениями кь+1 = )а(хз).
Приведем еще один пример марковской цепи типа (12), возникающей в задачах теории «очередей». Пример 3. Пусть на стоянку такси в единичные моменты времени прибывают (по одной в каждый момент) машины. Если на стоянке нет ГЛ. ). ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ )42 ожидающих, то машина немедленно уезжает. Обозначим через ц» число ожидающих, приходящих в момент й на стоянку, и будем предполагать, что ))(, ..., г)„— независимые случайные величины.
Пусть с» — длина очереди в момент К се =О. Тогда, если с» =(, то в следующий момент у+1 длина очереди ~»+( станет равной ))»+ ( если ('=О, 1= ( — 1+ и»+(, если 1> 1. Иначе говоря, с»+( = (с» — 1)+ +))»+), 0 < й < и — 1, где а+ = шах(а, О), и, значит, последовательность с = (со, ..., („) образует цепь Маркова. Пример 4. Этот пример относится к теории ветвящихся процессов. Под ветвящимся процессом с дискретным временем будем понимать последовательность случайных величин Со, С(, ..., С„, где С» интерпретируется как число частиц„существующих в момент времени й, а процесс гибели-размножения частиц происходит следующим образом: каждая частица независимо от других частиц и от «предыстории> превращается в / частиц с вероятностями р;, / =О, 1, ..., М.
Будем считать, что в начальный момент времени имеется всего лишь одна частица, Со=!. Если в момент Ф было С» частиц (с номерами 1, 2, ..., С»), то, согласно описанию, С»+( представляется в виде случайного числа случайных величин: С»+(=))( +" +г)4,, (м (») где ц,. — число частиц, произведенных частицей с номером Е Разумеется, (Ц если С» =О, то и С»4( =О. Считая, что все случайные величины г)», й > О, (») ( > 1, независимы между собой, находим Р(~»~( = 1»+( ~ С» = 1», С» ) = (»,, ...
) = (») (») = Р(~»~) =(»+( (С» =(») = Р(п)~ +... +)),.„" =(»+(). Отсюда видно, что последовательность Со, С(, ..., С„образует марковскую цепь. Особый интерес представляет случай, когда каждая частица или погибает с вероятностью (), или превращается в две с вероятностью р, р + д = 1. Для этого случая легко подсчитать, что Р;) = Р (~»4.( = ) ) ~» = () $ >2. МАРКОВСКИЕ >(ЕПИ. ЭРГОЛИЧЕСКАЯ ТЕОРЕМА >43 задается формулой ~С>>Узр>Узд> УУз, у=О, ..., 21, РЧ = (о в остальных случаях. р;; = Р(с> = у>бо = 1) = ... = Р(~„= у ) 4„> = (). Обозначим рч =Р((а =у (ба=1) (а«Р(ь«ь+> =Я! =(), ! = 1, 2, ...) 4> — вероятность перехода за и шагов из состояния > в состояние у и р!"=РК,=у) — вероятность нахождения частицы в момент времени й в точке у.
Пусть также "'=~М"В ">=~)р,',">)) Покажем, что переходные вероятности РЧ удовлетворяют «уравне- (~> нию Колмогорова †Чепме» р(ь+» С р(ь> р(» Ч =~ Р>ар«, а (13) или, в матричной форме, >р(4+я р(ь>, р(» (14) Доказательство соотношения (13) весьма просто н основано на формуле полной вероятности и марковском свойстве: = Р(6+ = у Ъ = 1) = ~~~, Р(4 44 = у, бл = 1й = 1) = (а+> а =,Ч; РЯ»+(=у'(Си=о)Р(С«=ойо=у)=~ ра>,РМ>. а а Особо важны следуюшие два частных случая уравнений (13): обратное уравнение Р>> =~ Р>ар«у (15) а 2. Будем обозначать через б = (~ю Щ Р) однородную марковскую цепь с вектором (строкой) начальных вероятностей 1П= 1>р> 1> и матрицей переходных вероятностей Р= 1>р>1>1 Ясно, что ГЛ.
1. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ВЕРОЯТНОСТЕЙ 144 и прямое уравнение ()6) а (см. рис. 22 и 23). В матричной форме прямые и обратные уравнения О 1 (+! Рис. 22. К обратному уравнению О и а+1 Рис. 23. К прямому уравнению записываются соответственно следующим образом: Р(а+!! Р(а! Р (!7) ((8) Р(а+(! Р, Р(а! Аналогично для (безусловных) вероятностей р( ' получаем, что ,(ае О '~ ,(а! ,(О Р/ ~~ а а!' и ((9) или, в матричной форме, П(аео П(а! Р(О В частности, П(~+~! =П(~! Р (прямое уравнение) н П(а+(! =П(!! Р(а! (обратное уравнение). Поскольку Р('! =Р, П(о! =П, то Р(а(=Р", П(а! =П Р'. Тем самым для однородных марковских цепей вероятности перехода за й шагов ру являются элементами й-х степеней матриц Р, в связи с чем (а! многие свойства этих цепей можно изучать методами матричного анализа.
Пример. Рассмотрим однородную марковскую цепь с двумя состояниями О и ! и матрицей Рго Ро! Рьо Р!! й )2. МАРКОВСКИЕ ПЕПИ. ЭРГОЛИЧЕСКАЯ ТЕОРЕМА !45 Нетрудно подсчитать, что ( Рсо+ Рю! Р)о Ро)(рее+ Р)!)') ~Р)э(роо+Р)!) Р))+Ре)Р)э / и (по индукции) 1 — Ро) '! 1 — ро),! + + (Р)ю+Ри — !)" ( 1 — Реэ -(1 — Ро))"! 2- Рео — Рп ~ — (1 — Ри) 1 — Ри,) ! (1 — Р 2 — рее — р)! ~! — Р)! р" — > (1 Рп 1 — реэ'1 2 — Рео — р)! ') ) — Р)! 1 — ро)/ (20) н, значит, 2 — Реэ — Р)! ' ь " 2 — сзх)— Таким образом, если !Реэ+ ри — 1(< 1, то поведение рассматриваемой марковской цепи подчиняется следующей закономерности: влияние начального состояния на вероятность нахождения частицы в том или ином состоянии исчезает с ростом времени (рц сходятся к предельным зна!л) ченням я;, не зависящим от ! и образующим распределение вероятностей: яо > О, я! > О, ло+ я! =!); если к тому же все элементы р;; > О, то тогда предельные значения яэ > О, я! > 0 (ср.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
