Цепи Маркова (1121219), страница 32
Текст из файла (страница 32)
Экзаменатор переходит от первой стратегии ко второй,когда наблюдает n последовательных правильных ответов, и переходит0.00. . . . . . . . . . . . . .0p0.......... . . 0 1 − q(1 − p)Уравнения инвариантности P = имеют видXj + q(1 − p) n ,0 = (1 − p)n−1=средняя длина вспышки.средняя длина блока06j6n−1+ (1 − q(1 − p))n,1 6 i 6 n − 1,q(1 − p)pn1, p, . .
. , pn−1 ,.nnq(1 − p ) + pq(1 − p)ca=pba+ (1 − p) (а предельная пропорция неправильно оцененных ответов равнаn (1− q) (1 − p) =pn (1 − q) (1 − p).pn (1 − q) + qk0=1(pk−10+ 1) =11+ 2(pp=Naturam expellas... tamen usque recurret.Гоните природу в дверь, она войдет в окно.Гораций (65 г. до н. э.–8 г. н. э.), римский поэт+ca=ca)1(p+1=baba+ (1 − p)ca+ 1,+ 1).Далее, рассмотрим а). Пусть состояние цепи Маркова — это числобросков монеты после последнего появления решки.
Тогдаii=0q+ nq = n,p (1 − q) + qn−1Xbaоткуда следует, чтоСледовательно, предельная пропорция адекватно оцененных ответов равна(При k = 1 это отношение равно p.)Решение. В силу строго марковского свойства имеемоткуда получаемi− 1 ,=pn=pi... 0... 0q(1 − p) 0 0 00.........00Пусть ji обозначает среднее число шагов до первого попадания в состояние j при условии, что ц.м.д.в. выходит из состояния i.
Выразите acв терминах величин ba .Последовательно подбрасывают монету, для которой вероятность выпадения герба равна p. Вычислите:а) среднее число бросков до появления серии из k последовательныхгербов;б) Определим блок порядка k как часть последовательности гербови решек между последовательными появлениями не менее, чем k идущихдруг за другом гербов. По соглашению, блок заканчивается этой сериейгербов, за которой следует решка, а после решки начинается начинаетсяновый блок порядка k.
Серию по меньшей мере k последовательных гербоввнутри блока будем называть вспышкой. Найдите отношениеp 0 0Задача 1.16.15. Неприводимая цепь Маркова имеет состояния 0, 1,. . . , n и матрицу перехода P = (p(i, j)). Стартуя из a, эта цепь не можетпопасть в состояние c, не пройдя вначале через b. Кроме того, известно,чтоp(b, c) = p,p(b, a) = 1 − p,для j 6= a, c.p(b, j) = 01−p. 1 − p 0 p ..1−p 0 0 pP=. . . . . . . .
. . . . . . . . 1−p 0 0 0193от второй стратегии к первой, когда обнаруживает неправильный ответ.Представьте этот процесс в виде ц.м.д.в. Найдите предельные пропорцииответов, которые экзаменатор проверил адекватно, и предельные пропорции неправильных ответов, которые получили полный балл.Решение. Состояниями являются 0, 1, . . . , n. В состоянии i < n экзаменатор заметил, что имеются i последовательных правильных ответов,и он использует стратегию 1.
В состоянии n он замечает, что имеютсяn правильных ответов, и переходит на стратегию 2, и ни одного неправильного ответа при этом еще не появилось. Эти рассуждения приводятк матрице§ 1.16. Вопросы по теории цепей Маркова с дискретным временемГлава 1. Цепи Маркова с дискретным временем192k−20+ 1) =1111111 − pk+ 2 + ... + 0 = + 2 + ... + k = k.ppppppp (1 − p)Теперь для б) рассмотрим последовательные независимые «блоки» испытаний, в результате которых после k или более гербов подряд следует194Глава 1. Цепи Маркова с дискретным временемрешка.
Для каждого блока среднее число гербов равноk + (pq) + 2p2 q + 3p3 q + . . . = k +p.1−pОжидаемая длина блока равнаk0+1+kp1−pp=1+ k+.1−pp (1 − p)1−p195Далее, в случае а) последовательность Zn = Mn не является цепьюМаркова, так как, напримерP (M4 = 2|M3 = 1, M2 = 0, M1 = 0, M0 = 0) = p >> P (M4 = 2|M3 = 1, M2 = 2, M1 = 1, M0 = 0) = p2 .А в случае б) последовательность Zn = Yn является цепью Маркова,посколькуДействительно, величина k0 — это среднее число бросков до появленияk последовательных гербов, p/ (1 − p) — это среднее число гербов, в дополнение к k имеющимся гербам, до появления первой решки, а 1 — этовклад, внесенный этой первой решкой.
Тогда благодаря усиленному з.б.ч.предельная пропорция гербов, появляющихся внутри блока, равна§ 1.16. Вопросы по теории цепей Маркова с дискретным временемk + p/ (1 − p)= (k(1 − p) + p)pk .1 + (1 − pk) / (pk (1 − p)) + p/ (1 − p)Задача 1.16.16. Рассмотрим ц.м.д.в. (Xn) n>0 с начальным состояниемX0 = 0 и вероятностями переходовP(i, i + 1) = p,P(i, i − 1) = q(i ∈ Z),где p + q = 1. ПустьMn = max {Xn } и Yn = Mn − Xn .06r6nДля каждого из следующих случаев определите, является ли (Z n) n>0ц.м.д.в., и в случае положительного ответа найдите ее вероятности перехода:а) Zn = Mn ; б) Zn = Yn .Решение. Пусть Zn принимает значения из множества I.
Формальноеопределение таково:P (X0 = i0 , X1 = i1 , . . . , Xn = in) =i 0 pi 0 i 1. . . pin−1 in ∀ n > 1 и i0 , i1 , . . . , in ∈ I.Здесь ( i , i ∈ I) — это вероятностное распределение, а (pij , i, j ∈ I) —стохастическая матрица (матрица перехода) на I. Отсюда следует, чтоусловные вероятностиP (Xn+1 = j | Xn = i, Xn−1 = in−1 , . . . , X0 = i0) = pijне зависят от того, какие значения in−1 , . . . , i0 принимают величины Xn−1 ,. . . , X0 .P (Yn = yn |Yn−1 = yn−1 , .
. . , Y1 = y1 , Y0 = 0) =q, если yn = yn−1 + 1,= p, если yn = yn−1 − 1 и yn−1 > 0,p, если yn = yn−1 = 0,т. е. эта вероятность не зависит от y1 , . . . , yn−2 .Задача 1.16.17. 1. Случайная последовательность неотрицательныхцелых чисел (Fn) n>0 образована следующим образом: F0 = 0, F1 = 1,а далее если известны F0 , . . . , Fn , то Fn+1 полагают равным либо сумме,либо разности величин Fn и Fn−1 с вероятностью 1/2.
Является ли (Fn) n>0ц.м.д.в.?Рассмотрев ц.м.д.в. Xn = (Fn−1 , Fn), найдите вероятность того, что(Fn) n>0 достигнет значения 3, прежде чем вновь попадет в 0.2. Постройте диаграмму для (Xn) n>0 , достаточную, чтобы установитьобщую закономерность поведения цепи. На основании этого, используястрого марковское свойство, покажите, что вероятность √достижения состояния (1, 1), если ц.м.д.в.
выходит из (1, 2), равна (3 − 5) /2.Not wrung from speculation and subtleties,but from common sense and observation.Не исходи из изворотливых рассуждений,а полагайся на наблюдения и здравый смысл.Т. Браун (1605–1682), английский врач и литераторРешение. См.
рис. 1.46.Последовательность (Fn) не является цепью Маркова, так как Fn+1зависит от Fn и Fn−1 , однако пара (Fn−1 , Fn) является ц.м.д.в. Первая частьрис. 1.48 a показывает, что уровня Fn = 3 можно достичь из состояния(F0 , F1) = (0, 1), попадая либо в точку (2, 3), либо в (1, 3).
Попасть наэтот уровень, прежде чем на уровень Fn = 0 (т. е. в состояние (1, 0)),можно по двум прямым траекториям, дополненным нескольким смежными196Глава 1. Цепи Маркова с дискретным временем§ 1.16. Вопросы по теории цепей Маркова с дискретным временем197√3± 5. Нас интересует ми2√3− 5. Следовательно,нимальный неотрицательный корень, т. e.
p =22√ .p0 =1+ 5Корни этого уравнения равны p = 1 иРис. 1.46треугольными циклами. Первая из этих возможностей имеет вероятность 21 1111· ·1 + + 2 + ... = ,22887а вторая — вероятность1·1 1 111· · 1 + + 2 + ...2 2 28817= ,что в сумме равно 3/7.Рассмотрим треугольный участок на рис. 1.48, обладающий очевиднойсимметрией. В частности,P (1,2) (попасть в (1, 1)) = P (2,3) (попасть в (1, 2)) = P (1,3) (попасть в (2, 1)) := pиP (2,1) (попасть в (1, 1)) = P (3,2) (попасть в (2, 1)) := p0 .Очевидно, 0 < p, p0 < 1.
Взяв условную вероятность по первому скачку,мы можем записать (благодаря строго марковскому свойству)12p = p0 +111P(попасть в (1, 1)) = p0 + p22 (2,3)22Задача 1.16.18. Блоха прыгает случайным образом по вершинам треугольника; каждый прыжок она совершает из занятой вершины на однуиз двух других с вероятностью 1/2. Найдите вероятность того, что блохавернется на место старта через n прыжков.Вторая блоха также прыгает по вершинам треугольника, но для неевероятность прыгнуть по часовой стрелке в 2 раза больше, чем вероятностьпрыгнуть против часовой стрелки.
Чему равна вероятность того, что втораяблоха возвратится на место старта через n прыжков?Решение. Для первой блохи матрица переходных вероятностей такова:!P=0 1 /2 1 /21 /2 0 1 /21 /2 1 /2 0(n)Благодаря симметрии все элементы на диагонали p ii одинаковы, равно(n)как и все элементы pij вне диагонали. Поэтому рассмотрим приведеннуюцепь с двумя состояниями 1 и 0 (не одинаковыми) и переходной матрицей01eP=.1 /2 1 /2(n)(n)e равны 1 и −1/2, иe11Тогда p11 = p.
Собственные числа матрицы P −1 n(n)=A+B,p112причем A + B = 1, A − B/2 = 0. Отсюда получаем A = 1/3, B = 2/3 и 12 −1 n(n).pii = +332Для второй блохииp0 =1 11 11+ P(попасть в (1, 1)) = + pp0 , следовательно, p0 =.2 2 (1,3)2 22−pПолучимp=11+ p2 ,2(2 − p)2т. e. p3 − 4p2 + 4p − 1 = (p − 1) (p2 − 3p + 1) = 0..P=0 1 /3 2 /32 /3 0 1 /31 /3 2 /3 0!,а собственные числа равны1,√−13−1±i= √ e ±i263/6.Глава 1. Цепи Маркова с дискретным временем+ √3nsin.6ncos+6= −1 n (n)p11Тогда198(n)p111991) среднее число шагов m (i,j) , необходимых для возвращения в (i, j),при условии, что ц.м.д.в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
