Цепи Маркова (1121219), страница 33
Текст из файла (страница 33)
выходит из (i, j), равно 1 / (i,j) = N2 (см. теорему1.7.8);2) благодаря симметрии и строго марковскому свойству,2= 2/3,(n)= 1/3,Получим3p11 =2=0и12 −1√+333nn.6→ 1 , и = (1/3, 1/3, 1/3) является (единПри этом = 1/3, так какственным) стационарным распределением. Постоянные и вычисляютсяиз уравнений для n = 0 и n = 1: √311= 0.+ + = 1,−√+§ 1.16. Вопросы по теории цепей Маркова с дискретным временемcosЗадача 1.16.19.
В упрощенной компьютерной игре фигурка движетсяслучайно по решетке размера N × N (N > 2) по следующим правилам.Пусть (Xn , Yn) — положение фигурки после n шагов, где Xn и Yn могутпринимать значения 0, 1, . . . N − 1. На (n + 1) -м шаге вероятность каждойиз следующих четырех возможностей равна 1/4:а)б)в)г)Xn+1Xn+1Xn+1Xn+1= Xn + 1= Xn − 1= Xn ,= Xn ,(mod) N,(mod) N,Yn+1 = Yn + 1,Yn+1 = Yn − 1,=ТогдаE (0,1) (время до попадания в (1, 1)) = N 2 − 1.Задача 1.16.20. В лабиринте, приведенном на рис.
1.47, пять пронумерованных клеток для крыс соединены туннелями. Линии означают туннели,по которым крыса может двигаться в любом направлении, а стрелки обозначают туннели, в которых есть «турникеты», препятствующие движениюв противоположном направлении.Yn+1 = Yn ;Yn+1 = Yn ;(mod) N;(mod) N.Вычислите1) среднее число шагов до возвращения в состояние (1, 1), если ц.м.д.в.выходит из состояния (1, 1),2) среднее число шагов для достижения (1, 1), если ц.м.д.в.
выходит изсостояния (0, 1).Решение. В данном случае ц.м.д.в. является случайным блужданиемна плоском графе с N 2 вершинами, которые расположены в узлах целочисленной решетки (i, j), i, j = 0, 1, 2, . . . , N − 1, и ребрами, которыесоединяют каждую такую точку с четырьмя соседними (при условии, чтоточка (i, 0) соединяется с точкой (i, N − 1), а точка (0, j) — с (N − 1, j);периодические граничные условия). В силу уравнений детального балансаравномерное распределение вида(i,j)m (i,j) = 1 + E (i−1,j) (время до попадания в (i, j)).1N2инвариантно.
Так как граф связный, ц.м.д.в. неприводима. Поэтому онаположительно возвратна и является единственным стационарным распределением. ТогдаРис. 1.47Крыса бегает по лабиринту следующим образом: в каждой клетке онаслучайным образом выбирает выход, и на каждом перекрестке, обозначенном •, она случайным образом выбирает направление (включая туннель,из которого она только что вышла, если только обратный путь не перекрыттурникетом). Пусть Xn — число посещений n-й клетки.
Найдите матрицупереходных вероятностей для цепи X = (Xn).Классифицируйте каждое состояние цепи в а), используя, где следует,термины «поглощающее», «невозвратное», «возвратное», «апериодическое», «нулевой возвратности», «положительно возвратное».Вычислите среднее время возвращения в каждое состояние.Найдите вероятность того, что крыса попадет в клетку 1, при условии,что она вышла из клетки 3.100004 / 9 1 / 9 1 / 9 1 / 6 1 / 6 P = 1 / 6 1 / 6 1 / 6 1 / 4 1 / 4 . 0 0 0 1 /2 1 /2 0001 /2 1 /2Из рис. 1.47 и вида матрицы P заключаем, чтосостояние 1 поглощающее;состояния 2 и 3 невозвратны и апериодичны;состояния 4 и 5 положительно возвратны, апериодичны.E 0 sTn = E 0 (s 1 E (em4 = m5 = 2.Наконец, для hk = P k (попасть в 1) имеем соотношенияи111+ h2 + h36662.
Для ϕ (s) = ϕ1 (s), взяв условные вероятности по первому скачку,получимϕ (s) = ps + (1 − p)sϕ3 (s) = ps + (1 − p)s(ϕ (s)) 3 .Корни этого уравнения имеют видΦ = 1,Счетное количество и одна ночь(Из серии «Фильмы, которые не вышли на большой экран».)Задача 1.16.21.
1. Блоха совершает случайное блуждание на целыхчислах {. . . , −1, 0, 1, . . .}. При каждом прыжке она продвигается на одиншаг вправо с вероятностью p или на два шага влево. Пусть n > 0 и T n —время первого достижения положения n, есливыходит из нуля.
ПоPблохаsk P (Tn = k) удовлетворяеткажите, что производящая функция ϕn (s) =kуравнению ϕn (s) = {ϕ (s) }n , где ϕ (s) = ϕ1 (s) и −1 < s 6 1.2. Покажите, что блоха (с вероятностью 1) допрыгает до состояния 1,если p > 2/3.При этом условии найдите среднее число шагов, которые необходимыблохе, чтобы оказаться в состоянии 1.Решение. 1.
Можно записатьk=1= ϕ1 (s) E 0 sTn−1 = (ϕ1 (s)) n ∀ s, −1 < s 6 1.(1 − p) Φ3 − Φ + p = (Φ − 1) ((1 − p) Φ2 + (1 − p) Φ − p) = 0.откуда следует, что h2 = 7/13, h3 = 4/13.Tn =1))Значит, величина Φ удовлетворяет уравнению411h2 = + h2 + h3 ,999nX|Φ := ϕ1 (s) | |s→1− = P 0 (T1 < ∞) < 1.m 2 = m 3 = ∞,h3 =2 +...+ nЭти вычисления справедливы независимо от того, равна ли вероятностьP 0 (T1 = ∞) нулю или положительна. Единственное отличие заключаетсяв том, что во втором случаеСредние времена возвращения равныm1 = 1,201где k — интервал времени между первым попаданием в состояние k − 1и первым попаданием в состояние k.
Благодаря строго марковскому свойству k ∼ T1 , где T1 — момент попадания в состояние 1 при выходе изсостояния 0. Используя пространственную однородность переходов, получим, чтоРешение. Переходная 5 × 5-матрица имеет вид:§ 1.16. Вопросы по теории цепей Маркова с дискретным временемГлава 1. Цепи Маркова с дискретным временем200k,− (1 − p) ±p(1 − p) 2 + 4p(1 − p).2(1 − p)При p > 2/3 два последних корня по модулю больше 1, поэтому Φ = 1и T1 < ∞ с вероятностью 1.Наконец, положимM := ϕ01 (s) s→1− = ET1 .Тогда(1 − p) Φ3 + 3(1 − p) Φ2 M − M + p = 0.При p > 2/3 подстановка Φ = 1 приводит к равенствуM=1.3p − 2В частности, это доказывает, что M = ∞ при p = 2/3.Задача 1.16.22.
Из лаборатории поступили 2 независимые последовательности наблюдений Y1 , Y2 , . . . и Z1 , Z2 , . . . Они представляют собой202Глава 1. Цепи Маркова с дискретным временем§ 1.16. Вопросы по теории цепей Маркова с дискретным временемн.о.р. испытания Бернулли, т. е. каждая случайная величина принимаетзначения 1 или 0 с неизвестными вероятностями успехаоткуда следует, чтоp = P (Yi = 1) = 1 − P (Yi = 0) и q = P (Zi = 1) = 1 − P (Zi = 0),Тогдаi > 1,где 0 < p < 1, 0 < q < 1.
Для того чтобы решить, какая из вероятностей pи q больше, мы применяем следующий тест: выбираем натуральное числоM и прекращаем наблюдения в первый такой момент времени n, что илиY1 + . . . + Yn − (Z1 + . . . + Zn) = M,u −M = −h0 = 1 −1 − 1/1 − 1/1 − 1/.1 − 1/ 2MM2M203M=2M−11=−11+M.Задача 1.16.23. В вершинах приведенного ниже графа (см. рис.
1.48)расположены лампочки. В каждый момент времени может светиться только одна лампочка.илиY1 + . . . + Yn − (Z1 + . . . + Zn) = −M;в первом случае мы принимаем решение, что p > q, а во втором — чтоp < q. Покажите, что если p > q, то вероятность ошибки (т. е. вероятностьрешить, что p < q) равна (1 + M) −1 , где = p(1 − q)q−1 (1 − p) −1 .Решение. Определим ц.м.д.в. Xn = (Y1 − Z1) + . . .
+ (Yn − Zn) на{−M, . . . , M} с переходными вероятностямиpii+1 = p(1 − q),pii = pq + (1 − p) (1 − q),i = −M + 1, . . . , M − 1,pii−1 = q(1 − p),где −M и M — поглощающие состояния. Мы хотим вычислить h0 , где hi == P i (попасть в −M до попадания в M). Получим уравненияh−M = 1,hi = q(1 − p)hi−1 + (pq + (1 − p) (1 − q))hi + p(1 − q)hi+1 ,− M + 1 6 i 6 M − 1,hM = 0.При ui = hi+1 − hi получимui =где1u i− 1 = . . . == p(1 − q) q(1 − p). Тогдаhi+1 − 1 = u−MiX+MПри i = M − 1 получаемj=01j 1 i+M=u −M ,1 − 1/ i+M+1u −M .1 − 1/Рис.
1.48Пусть Xn обозначает номер лампочки, которая горит в момент времениn > 0. Процесс эволюционирует следующим образом. Если X n = i, толампочку, которая загорится в момент времени n + 1, выбирают (с равнойвероятностью) среди вершин, которые соединены ребром с i.
Например,если лампочка C горела в момент времени n, то одна из лампочек R 1 , R4 ,L1 , L4 загорится с вероятностью 1/4 в момент времени n + 1. Покажите,что P (Xn = L1) сходится к пределу при n → ∞, и найдите этот предел.При X0 = C найдите среднее количество раз, когда лампочка R 1 загорится, прежде чем впервые вновь загорится лампочка C.Предположим теперь, что длина интервала времени, в течение котороголампочка горит, не равна 1, как ранее, а является экспоненциальной случайной величиной со средним 2/7 и последовательные моменты включениялампочек независимы. Пусть в момент t = 0 включается лампочка C.Найдите среднее время, в течение которого будут гореть лампы справаот C, прежде, чем снова загорится лампочка C.Решение.
Рассматриваемая ц.м.д.в. — это случайное блуждание наконечном графе. Она обратима по отношению к стационарному распределению = ( i), где.Xvj .i = vijи vi — кратность вершины i. В данном примере−1 =1 − 1/ 2Mu −M ,1 − 1/C18= ,L=R=1,16Lk=Rk=3,321 6 k 6 4.204Глава 1. Цепи Маркова с дискретным временем+CR3+CR4+CR2+CR1(CR)·E0T =∞X0=∞Xk (1l=0следовательно,=− ak),0 bnиi0=i− 1 a i− 1 ,X=bnчто дает тот же ответ 1 для цепи с непрерывным временем.Задача 1.16.24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
