Цепи Маркова (1121219), страница 7
Текст из файла (страница 7)
Времена и вероятности достиженияjn 6∈AПоскольку gi > 0, опустив последнюю сумму, мы уменьшим правую часть.Первые же n слагаемых дают в сумме P i (HA 6 n). Следовательно,23hA = hB .Далее,hB =11+ hD ,33откуда получаем23hE = hD .Тогда132937hD = hB + hD ,gi > lim P i (HA 6 n) = P i (HA < ∞) = hAi .n→∞В общем случае эти уравнения предоставляют мощное средство длявычисления вероятностей достижения даже в самых запутанных ситуациях,особенно, когда можно воспользоваться симметрией ц.м.д.в.
См. следующие примеры.Пример 1.3.2. Постройте граф, имеющий семь вершин, следующимобразом: возьмите правильный шестиугольник и соедините противоположные вершины прямыми линиями; пусть вершинами графа будут вершинышестиугольника и его центр симметрии; а ребрами графа будут сторонышестиугольника и отрезки, соединяющие вершины с центром. В дискретные моменты времени частица переходит от одной вершины графак какой-то из соседних вершин случайным образом и независимо от прошлых переходов. Предположим, что частица начинает движение в вершинеA шестиугольника. Найдите вероятность того, что частица вернется в A,так и не побывав в центральной вершине C.13и вновь в силу симметрииAgi > P i (H 6 n) ∀ n > 0,13h D = hB + hE ,Наконец,hB =11+ hB ,37т. е. hD = hB .т. е.
hB =7.18Следовательно, hA = 7/27.Пример 1.3.3. Процессы рождения и гибели; см. пример 1.1.7 б). Дляпроцесса рождения и гибели положим hi = P i (достичь 0), тогда hi являетсяминимальным неотрицательным решением системыh0 = 1, hi = phi+1 + (1 − p)hi−1 , i > 1.При p 6= 1/2 это решение имеет видhi = A + B 1 − p ip.Если p < 1/2, из условия минимальности и неотрицательности следует,что B = 0 и A = 1, откуда получаем hi ≡ 1. Если p > 1/2, заключаем, чтоA = 0 и B = 1, и тогда 1 − p ihi =.pПри p = 1/2 решение имеет видhi = A + BiРис. 1.12Решение.
См. рис. 1.12. Положимhi = P i (достичь A раньше, чем достичь C).и вновь из условия минимальности и неотрицательности следует, что B = 0и A = 1, значит, hi ≡ 1.Отметим, что найденные значения не зависят от выбора вероятностей p0j . Заметим также, что hi — это вероятность вымирания, а 1 − hi —В каждую секунду один человек умирает, а 11человека рождается.16Ч. Бэббидж (1792–1871), английский математикЕсли мы перейдем к примеру 1.1.7 в), то уравнения становятся зависимыми от состояния:h0 = 1,hi = pi hi+1 + (1 − pi)hi−1 , i > 1.Для отыскания решения перейдем к рассмотрению разностейui = hi−1 − hi , где pi ui+1 = (1 − pi)uiиПоложимui+1 =i1 − pi1 − pi 1 − pi−11 − p1ui =...u1 .pipipi−1p11 − pi−11 − p1=..., тогда, посколькуpi−1p1+ ...
+j=ij=0i−1).∞Xj=ijj=0X∞j=0j , еслиj∞Xj6∈AТаким образом, для любого решения gi > 0 системы (1.3.5) выполняется неравенство gi > kAi , i ∈ I.Д о к а з а т е л ь с т в о. Как и при отыскании hAi , математическое ожидание времени достижения kAi вычисляется при X0 = i. Если i ∈ A, тоHA = 0, следовательно, и kAi = 0. Если i 6∈ A, то HA > 1 иE i (HA | X1 = j) = 1 + E j HAXE i (HA 1(X1 = j)) =j=0Xj=1+P i (X1 = j) E i (HA | X1 = j) =XP i (X1 = j) E j HA = 1 +j6∈Apij kAj .j6∈APj6∈Ak6∈Apij как P (HA > 2), находимj6∈A< ∞.XПусть теперь gi — это любое неотрицательное решение.
Тогда gi == kAi = 0 для i ∈ A. Если i 6∈ A, тоXX Xgi = 1 +pij gj = 1 +pij 1 +pjk gk .Представив 1 как P i (HA > 1), аj= ∞.Для средних времен достижения kAi справедлива следующая теорема.Теорема 1.3.4. При заданном A ⊂ I величины kAi представляютсобой минимальные неотрицательные решения следующей линейнойсистемы:kAi ≡ 0,i ∈ A,X(1.3.5)AApij kj , i 6∈ A.ki = 1 +j6∈A= ∞,hi =еслииhi ≡ 1,jj=0i=0∞X∞Xеслиj∈IЗдесь 0 = 1 и A = u1 .
Постоянная A определяется из того условия, чтоinfi hi > 0: −1X∞A=.iТаким образом,j=00,kAi = E i (HA) =мы получаем0В частности, во втором случае, hi+1 6 hi и limi→∞ hi = 0. Вероятностивыживания теперь равныX∞∞∞XX1−,еслиjjj < ∞,в силу марковского свойства. Таким образом,u1 + .
. . + u i = h 0 − h i ,hi = 1 − A(43вероятность выживания (условные вероятности при условии X 0 = i). Следовательно, вероятности выживания равны1 − 1 − p i , i > 0, для p ∈ (1 2, 1] ,/p0для p ∈ [0, 1/2] .§ 1.3. Времена и вероятности достиженияГлава 1. Цепи Маркова с дискретным временем42gi = P i (HA > 1) + P i (HA > 2) +Xj6∈ApijXk6∈Apjk gk .Глава 1. Цепи Маркова с дискретным временемПовторяя подстановки, для любого n находимX...j1 6∈AXpij1 pj1 j2 . . . pjn−1 jn gjn >jn 6∈A> P i (HA > 1) + . . .
+ P i (HA > n),Предположим, что та же лягушка начинает прыжки, находясь на расстоянии N ступеней от вершины на бесконечной лестнице. Чему теперьбудет равно ожидаемое число прыжков, которые совершит лягушка, прежде чем достигнет вершины лестницы?Решение. Система уравнений для конечной лестницы [0, N] имеет видkN = 0,так как gi > 0. Тогда при n → ∞ получаемПример 1.3.6. Пролет лестницы состоит из N ступенек. Лягушка,начиная движение от подножия лестницы, пытается добраться до верхней ступени, совершая серию независимых прыжков следующим образом.Если лягушка находится на i-й ступеньке (0 < i < N), то ей удаетсяперепрыгнуть на (i + 1)-ю ступеньку с вероятностью (0 < < 1/2), нос такой же вероятностью она может упасть вниз на (i − 1) -ю ступеньку и с дополнительной вероятностью 1 − 2 она вновь приземляется наi-ю ступеньку.
Когда лягушка находится у подножия лестницы (нулеваяступенька), ей удается подпрыгнуть вверх так, чтобы попасть на первуюступеньку с вероятностью (0 < < 1), а с вероятностью 1 − она остается на прежнем месте. Чему равно ожидаемое число прыжков, которыесовершит лягушка, прежде чем достигнет вершины лестницы?а из граничных условий в точках i = 0 и N следует, чтоN 2 − i2N−iN−i−+22k0 =N(N − 1)N+ .2ki =1В случае бесконечной лестницы выражение A + Bi −i2 невозможно2сделать неотрицательным для всех i.
Следовательно, k i ≡ ∞.Пример 1.3.7. Рассмотрим ц.м.д.в. с пространством состояний{1, 2, 3, 4, 5, 6} и матрицей переходаОбщее решение имеет вид ki = A + Bi; постоянные A и B задаютсяравенствами A = 0, B = 1/ (1 − 2p). Однако при p > 1/2 конечногонеотрицательного решения не существует. Следовательно, для i > 1 имеем 1 i при 0 6 p < 1/2,ki = 1 − 2p∞при 1/2 6 p 6 1.1 2i ,2ki = A + Bi −иki = 1 + pki+1 + (1 − p)ki−1 , i > 1.Общее решение имеет видОтметим, что единственным неотрицательным решением системы(1.3.5) может оказаться kAi ≡ ∞, i 6∈ A. Как и в случае с величинами hAi ,уравнения (1.3.5) можно эффективно использовать, особенно в случаях,когда система обладает свойствами симметрии.Пример 1.3.5.
Для процесса рождения и гибели из примера 1.1.7 б)положим ki = E i (H{0}); это среднее время достижения состояния 0. Тогдаki является минимальным неотрицательным решением системыk0 = 0,k0 = 1 + (1 − )k0 + k1 .n=1P i (H > n) = E i H =kAi .Aki = 1 + ki−1 + (1 − 2 )ki + ki+1 , 1 6 i 6 N − 1,Agi >∞X45gi = 1 + P i (HA > 1) + . . . + P i (HA > n) +§ 1.3. Времена и вероятности достижения44 0 01 / 5 1 / 51 / 3 01 / 6 1 / 601 /4001 /2 001 /5 1 /5 1 /51 /3 001 /6 1 /6 1 /60011 /2 001 /20 1 /3 .1 /601 /4Найдите сообщающиеся классы для этой цепи и для каждого классаукажите, является он открытым или замкнутым.Предположим, что цепь выходит из состояния 2; найдите вероятностьтого, что когда-либо будет достигнуто состояние 6.Предположим, что цепь выходит из состояния 3; найдите вероятностьтого, что цепь попадет в состояние 6 ровно за n переходов (шагов), n > 1.Решение.
Структура цепи представлена на рис. 1.13.46Глава 1. Цепи Маркова с дискретным временем§ 1.4. Строго марковское свойство47Отсюда следует, что 1 n 1 n(n)p36 = A + B −+C −,4n = 0, 1, . . .6При n = 0, 1, 2 получаем равенства14A + B + C = 0,откуда следует, чтоA=значит,(n)p36 =Рис. 1.13Состояния 1, 3, 6 образуют замкнутый класс, состояния 2, 4 — открытый класс, а состояние 5 является поглощающим (и образует замкнутыйкласс).
Если hi = P i (достигнуто состояние 6) то h1 = h3 = 1,112555111h4 = h4 + h2 + ,662откуда получаем h2 = 13/19, h4 = 14/19. Следовательно, ответ на второйвопрос таков:P 2 (достигнуто состояние 6) =13.19Далее, для класса {1, 3, 6} матрица перехода имеет вид!.Для того чтобы найти ее собственные значения, решаем уравнение!−1 /21 /41 /2det 1/3 1/3 −т. е.3и находим−7122−1 /21 /31 /4 −91−= ( − 1)24241= 1,214=− ,= 0,22+1312,35124+35545B= ,−14nA+1113B+ C= ,16363687C=− ,−87−16n.§ 1.4.
Строго марковское свойствоRestore my Strong Markov property!3(Из серии «Кое-что из политики».)h2 = h 2 + h 4 + ,0 1 /2 1 /21 /3 1 /3 1 /31 /4 1 /2 1 /416A− B− C= ,15+122416=− .= 0,Строго марковское свойство состоит в том, что процесс начинаетсязаново не только после любого заданного момента времени n, но такжеи после случайно выбранного момента времени. Примером такого моментавремени может служить H i — момент первого достижения цепью заданногосостояния i ∈ I.
Сформулируем это свойство в общем случае.Определение 1.4.1. Случайная величина T, зависящая от X 0 , X1 , . . .и принимающая значения 0, 1, 2, . . . , ∞, называется моментом остановки,если событие {T = n} описывается только в терминах случайных величинX1 , . . . , Xn без привлечения величин Xn+1 , Xn+2 , . . .Образно говоря, наблюдая за цепью, вы знаете, когда вам следуетостановиться, и предвидеть будущие состояния вам для этого не нужно.Время первого достижения H A является примером момента остановки,поскольку {HA = 0} = {X0 ∈ A}, а при n > 1 выполняются соотношения{HA = n} = {X0 6∈ A, . .
. , Xn−1 6∈ A, Xn ∈ A}.Когда A состоит лишь из одного состояния i, время достижения частоназывают временем первого входа:Hj = inf [n > 0 : Xn = j}.3 Игра слов, основанная на том, что слово property означает«свойство», а также «собственность» или «имущество».48Глава 1. Цепи Маркова с дискретным временемStop Man, Hit Woman4(Из серии «Фильмы, которые не вышли на большой экран».)С другой стороны, последний момент пребыванияLA = sup [n : Xn ∈ A] ,вообще говоря, не является моментом остановки, так как для события{LA = n} требуется информация об Xn+1 , Xn+2 , .
. .Теорема 1.4.2. Пусть (Xn , n > 0) — это цепь Маркова ( , P),и предположим, что T — это момент остановки. Тогда, при условии T < ∞ и XT = i последовательность (XT +n , n > 0) образует( i , P)-цепь Маркова. В частности, при условии T < ∞ и XT = iслучайные величины XT +1 , XT +2 , . . . не зависят от X0 , . . . , XT −1 .Д о к а з а т е л ь с т в о. Пусть A — это событие, которое определяетсясостояниями цепи до момента времени T, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
