Цепи Маркова (1121219), страница 4
Текст из файла (страница 4)
Используязапись± iϕ= | ± | (cos ϕ ± i sin ϕ),± = | ± |eсоответствует характеристическое уравнение5 251− 3++− = − ( − 1)вектор — это строка 1 = (1, . . . , 1) из единиц. Формально 1P T = 1, или,что эквивалентно, P1T = 1T для столбца 1T . Чтобы проверить последнееравенство, заметим, что каждый элемент столбца P1 T равен 1:X(P1T) i =pij = 1,§ 1.1. Марковское свойство и немедленные следствия из негоГлава 1. Цепи Маркова с дискретным временем22(n)pij = A + Bи12+C −1 − √17 n12,√√−1 + 17−1 + 17A + B + C = ij , A + B+= pij1212 −1 + √17 2 −1 − √17 2+C= pij(2) .A+B1212(n)Например, окончательное выражение для p21 имеет видможно работать только с действительными слагаемыми вида cos(nϕ)и sin(nϕ).(n)В-третьих, коэффициент A перед единицей в уравнении для p ij , какгде −1 + √17 n −1 + √17 n1226√ +1−1917 −1 − √17 n12.правило, определяет предел lim pij(n) .
Это следует из того, что | | 6 1 для426√ −1+191917n→∞всех собственных чисел матрицы P и, «как правило» (хотя и не всегда),любое собственное число 6= 1 по модулю меньше 1, | | < 1. Это болеетонкий факт, к нему мы еще вернемся в последующих параграфах. Поэтомув разложенииX(n)Bs nspij = A +P=1 /3 1 /3 1 /30 1 /2 1 /21 /3 2 /3 0!/ (N − 1) .
. .1−/ (N − 1)/ (N − 1)/ (N − 1) . . .1−. . . / (N − 1) (N − 1) 1 −P= /. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .n→∞так как Pn осциллирует между I для четных n и P для нечетных n.)Необходимо отметить, что многие (даже очень простые) примеры могутпривести к достаточно громоздким формулам для p ij(n) . Например, матриценеверно: собственные числа равны 1, и −1 и предел lim pij(n) не существует,этоПример 1.1.11. Полезным свойством является наличие симметриив матрице P: оно может сократить число состояний исходной цепи Маркова.
Например, матрица N × N вида0 11 0все члены, кроме A, исчезают при n → ∞. (В случае P =Рис. 1.3собственныечисла s 6=1описывает модель мутации вируса, в которой вирус либо сохраняет свойтип, либо меняет его на любой другой тип с одинаковыми в этом случаевероятностями (типы — это 1, . . . N).24Глава 1. Цепи Маркова с дискретным временем(n)/ (N − 1) 1 − / (N − 1)1−Кроме того, в силу симметрии(n)pij =−n=N−11N−1N n= +1−.NNN−1(n)1 − p11∀ i 6= j.N−1Теперь пора установить знаменитое марковское свойство для ц.м.д.в.Оно состоит в том, что цепь Маркова стартует заново после любого заданного момента времени n.Теорема 1.1.12. Пусть (Xn) — цепь Маркова с параметрами ( , P).Тогда, ∀ m > 1 и i ∈ I при условии, что Xm = i, процесс (Xm+n , n > 0) —цепь Маркова с параметрами ( i , P). В частности, при условии, чтоXm = i, случайные величины Xm+1 , Xm+2 , .
. . не зависят от величинX 0 , . . . , X m− 1 .Иными словами, в ц.м.д.в. прошлое (X0 , . . . , Xm−1) и будущее(Xm+1 , Xm+2 , . . .) условно независимы при фиксированном настоящем(Xm = i).Д о к а з а т е л ь с т в о. Напомним, что стохастический вектор i состоит из элементов ij , j ∈ I.
Нужно проверить, что для любого событияA, определяемого величинами X0 , . . . , Xm−1 , и события B, определяемоговеличинами Xm+1 , . . . , Xm+1+n , для некоторого n, имеют место следующиеутверждения: а) условная вероятность P (A ∩ B | Xm = i) представляетсяв виде произведенияP (A ∩ B | Xm = i) = P (A | Xm = i) P (B | Xm = i),(1.1.10)и б) условная вероятность P (B | Xm = i) вычисляется, как в ( i , P)-ц.м.д.в.:Xpij1 .
. . pjn−1 jn .(1.1.11)P (B | Xm = i) =(j1 ,...,jn) ∈B25Пусть вначале A и B имеют видA = {X0 = i0 , . . . , Xm−1 = im−1 },B = {Xm+1 = j1 , . . . , Xm+n+1 = jn }для некоторой последовательности состояний i 0 , . . . , im−1 , j1 , . . . , jn ∈ I.Произвольные события A и B являются объединениями таких непересекающихся «элементарных» событий.Для событий A и B указанного вида выполняются соотношения= / (N − 1)):+ / (N − 1)/ (N − 1)++ / (N − 1)=(n)p11Теперь можно применить формулы из примера 1.1.7 (сЧтобы вычислить p11 , сведем число состояний к двум (к примеру 1 и 0),рассматривая переходы из состояния 1 в него же или в другое состояниеи обратно, без дальнейшей детализации (поскольку для полной постановкизадачи все остальные состояния неразличимы). Приведенная цепь с двумясостояниями имеет матрицу перехода 2 × 21−.§ 1.1.
Марковское свойство и немедленные следствия из негоP (A ∩ B ∩ {Xm = i}) == P (X0 = i0 , . . . , Xm−1 = im−1 , Xm = i, Xm+1 = j1 , . . . , Xm+n+1 = jn) == i0 pi0 i1 . . . pim−1 i pij1 . . . pjn−1 jn .Для произвольного B нужно взять сумму по всем (j1 , . .
. , jn) ∈ B:Xpij1 . . . pjn−1 jn .i0 pi0 i1 . . . pim−1 iСуммаP(j1 ,...,jn) ∈B(j1 ,...,jn) ∈Bдает условную вероятность P (B | Xm = i), значит, этавероятность действительно вычисляется так же, как в ( i , P)-ц.м.д.в.Далее, для произвольного события A просуммируем по (i 0 , . .
. , im−1) ∈ A:P (A ∩ B ∩ {Xm = i}) =X(i0 ,...,im−1) ∈Ai 0 pi 0 i 1. . . pim−1 i P (B|Xm = i) == P (A ∩ {Xm = i}) P (B | Xm = i).Наконец, для вычисления условной вероятности P (A ∩ B | X m = i) разделимна P (Xm = i):P (A ∩ B ∩ {Xm = i})=P (Xm = i)P (A ∩ {Xm = i})=P (B | Xm = i) = P (A | Xm = i) P (B | Xm = i),P (Xm = i)P (A ∩ B | Xm = i) =что и требовалось доказать.В дальнейшем будем обозначать через Pi условные вероятностиP ( · | X0 = i), взятые при условии, что состояние системы в момент времени0 есть i.Пример 1.1.13.
Три девочки A, B и C играют в настольный теннис.В каждой игре две девочки играют друг против друга, а третья отдыхает.Победитель любой фиксированной n-й игры снова играет в (n + 1)-й игре.26Глава 1. Цепи Маркова с дискретным временемВероятность того, что девочка x победит девочку y в любой игре, в которойони играют друг против друга, равна sx / (sx + sy) для x, y ∈ {A, B, C}, x 6=6= y, где sA , sB , sC соответствуют игровым навыкам этих трех девочек.a) Представьте этот процесс в виде ц.м.д.в., определив пространствовозможных состояний и переходные вероятности.б) Найдите вероятность того, что те же две девочки, которые игралидруг против друга в первой игре, будут опять играть друг против другав четвертой игре. Покажите, что эта вероятность не зависит от того, какиеименно две девочки участвовали в первой игре.Решение. a) Промаркируем состояния буквами A, B, C, определяющими, какая из девочек не участвует в заданной игре.
Тогда матрицапереходных вероятностей для {A, B, C} × {A, B, C} имеет видsCsB 0s+ssBCB + sC sCsA.0 sA + s CsA + s C sBsA0sA + s B sA + s BЭтот процесс является цепью Маркова, потому что результаты последовательных игр независимы.б) Сейчас мы ищем вероятность того, что за три шага цепь вернетсяв заданное начальное состояние. См.
рис. 1.4.§ 1.1. Марковское свойство и немедленные следствия из него27место, указанное в его билете. Если это место свободно, он занимает его,и концерт начинается. Однако если это место занято, зритель настаивает,чтобы место было освобождено. В этом случае зритель, освободившийместо, решает поступать точно также: если свободное место соответствуетего билету, он его занимает; в противном случае он настаивает, чтобы егоместо освободили. Ту же политику применяет и следующий неудачливыйзритель и т.
д. Каждое перемещение занимает 45 секунд. Какова ожидаемаязадержка начала концерта, вызванная этими перемещениями.Решение (набросок). Здесь важно иметь в виду, что первоначально N − 1 зритель распределен так, что а) вероятность того, что место jсвободно, равна 1/N, j = 1, . . . , N; б) при условии, что место j свободно,вероятность того, что первый зритель, вошедший в зал, займет место i 1 ,второй займет место i2 , . . ., (N − 1)-й займет место iN−1 , равна 1/ (N − 1)!,для любой последовательности i1 , . . ., iN−1 из множества {1, .
. . , N} \ {j}.Рассмотрим ц.м.д.в. с состояниями N, N − 1, . . ., 0. Здесь состояние 0обозначает, что зритель, пришедший последним, увидит свое место свободным, состояние n, 1 6 n 6 N − 1, означает, что (N − n) -е передвижениебыло «неудачным», и N — начальное состояние системы. Тогда вероятность перехода из состояния n в 0 равна 1/n и вероятность перехода из nв n − 1 равна (n − 1) /n; вероятность перехода из 0 в 0 равна 1.
Пусть E(n)обозначает ожидаемое число переходов (перемещений) до того момента,как ц.м.д.в. попадет в состояние 0 из состояния n; нас интересует E(N).Полезное замечание: E(n) равно ожидаемому числу перемещений в залес n местами.Ключевым в решении задачи является рекуррентное соотношение:E(n) =n−11n−1· [1 + E(n − 1)] + · 0 =[1 + E(n − 1)] ,nnnn = 1, 2, . . .
,гдеE(1) = 0.Рис. 1.4(3)pAA = pAB pBC pCA + pAC pCB pBA =2sA sB sC.(sA + sB) (sB + sC) (sC + sA)Пример 1.1.14. Рок-концерт, проводящийся в холле с N нумерованными местами, привлёк огромную толпу зрителей. Свет потушен, N − 1место уже занято и последний зритель заходит в зал. Первым N − 1 зрителям распорядитель довольно легкомысленно посоветовал занять местаслучайным образом, но последний зритель настаивает на том, чтобы занятьОтсюда следует, чтоE(n) =1n−1(n − 1 + n − 2 + .
. . + 1) =.n2Если N = 121 (размер небольшого зала), то ожидаемое время задержки120= 45 мин.45 ·2Пример 1.1.15. Мораль следующей задачи составляет то, что частополезно ввести вероятности даже там, где изначальноo Предn их не было.1положим, что окружность единичной длины C 1 = z : |z| =разбита2на два непересекающихся измеримых множества, одно из них, называемоеВ силу симметрии эта вероятность одинакова для любого начальногосостояния и равна28Глава 1. Цепи Маркова с дискретным временемкрасным, имеет общую длину 2/3, а другое, голубое, длину 1/3.
Докажите,что всегда можно вписать в окружность квадрат так, что по меньшей меретри из его четырех вершин будут красными.Решение. При заданном разбиении рассмотрим квадрат, вписанныйслучайным образом, причем одна из вершин распределена на C 1 равномерно; это единственным образом определяет квадрат. Пронумеруем вершины1, 2, 3, 4, например, по часовой стрелке, начиная с той первой, котораяраспределена равномерно. ПоложимXi = 1(вершина i попала в красное множество),i = 1, 2, 3, 4.ТогдаE (числа красных вершин) = EX1 + EX2 + EX3 + EX4 = 4 EX1 = 8/3 > 2.Таким образом, сумма X1 + X2 + X3 + X4 принимает значения 3 или 4с положительной вероятностью, значит, всегда можно вписать квадрат так,как указано в задаче.На самом деле можно оценить вероятность P того, что по меньшеймере три из четырех вершин будут красными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
