Цепи Маркова (1121219), страница 37

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 37)

Стрелочная диаграмма ц.м.н.в. из условия задачи полностьюсимметрична. На рис. 2.14 показаны только стрелки, выходящие из состояния 0. В силу симметрииqi := −qii = ;иQ=qij =N,−/N/N −.../N/N1 6 i, j 6 N + 1, i 6= j,.../N.../N ....... −1при t → ∞ (это равномерное дискретное распределение).N+1Пример 2.2.6. Блоха скачет по часовой стрелке от вершины к вершинетреугольника ABC; времена пребывания — независимые показательно распределенные с параметром единица случайные величины.

Найдите собственные значения соответствующей Q-матрицы и выразите вероятностиперехода pxy (t), t > 0, x, y = A, B, C, через эти корни характеристическогоуравнения. Выразите суммыS0 (t) =∞Xt3nn=0(3n)!,S1 (t) =∞Xn=0t3n+1,(3n + 1)!S2 (t) =√√через функции et , e−t/2 , cos( 3t/2) и sin( 3t/2).Найдите пределыlim e−t Sj (t),t→∞j = 0, 1, 2.∞Xn=0t3n+2,(3n + 2)!228Глава 2. Цепи Маркова с непрерывным временемКакова связь между разложениями et = S0 (t) + S1 (t) + S2 (t) и et == ch t + sh t?Решение. Выпишем характеристический полином Q-матрицы!det−1 − κ100−1 − κ1−1 − κ10= (−κ − 1) 3 + 1 = −κ (κ 2 + 3κ + 3).§ 2.2.

Марковские цепи с непрерывным временем...Наконец, вероятности pAC (t) = pBA (t) = pCB (t) равны∞ √3 √3 Xt3n+2111e −t= − e−3t/2 cost − √ e−3t/2 sint ,32√3.2и S2 (t) =где2132a = pxx (∞) =(так как = (1/3, 1/3, 1/3)),3a+√ b = pxx (0) = 1, следовательно, b = 2/3,3c = ṗxx (0) = qxx = −1,2− b+следовательно, c = 0.Заметим, что Q-матрица имеет вид Q = A − I, где все элементы матрицыA за исключением a12 , a23 и a21 , являются нулевыми. Следовательно,etQ = e−tI etA . Далее, заметим, что Q3 = I и все диагональные элементыматрицы Qk равны 0, если k не делится на 3. Отсюда следует, чтоpxx (t) =∞Xe −tn=0Таким образом,S0 (t) =3nt,(3n)!x = A, B, C.∞Xt3nn=012= et + e−t/2 cos(3n)!33 √3 t .32∞P3n+132tравно(3n+ 1)!n=0 √3 √3 1 t11e − e−t/2 cost + √ e−t/2 sint .33223следовательно, S1 (t) =3t3n+2равноn=0 (3n + 2)!∞P1 t1e − e−t/2 cos33223 √3 √3 1 −t / 2√t −esint .22313lim e−t Sj (t) = , j = 0, 1, 2,t→∞задают стационарное распределение = (1/3, 1/3, 1/3).Разложение et = ch t + sh t появляется, если рассмотреть ц.м.н.в.с Q-матрицей−1 1,1−1т.

е. «приведенный» вариант предыдущей цепи.Пример 2.2.7. Рассмотрим Q-матрицу размера N × N вида−−1 1 0 . . . 0 00 ... 0 0. . . 0 00 − 0 0 − . . . 0 0. . . . . . . . . . . . . . . . . . . . . .  =000000... −... 00 0 −1 1 . . . 0 0  0 0 −1 . . . 0 0. . . . . . . . . . . . . . . .

. . . . . .  .000000(2.2.11). . . −1 1... 0 0См. рис. 2.15. Здесь состояние N является поглощающим: q Ni ≡ 0, или,Рис. 2.152Аналогично вероятности pAB (t) = pBC (t) = pCA (t) равны √3 √3 111− e−3t/2 cost + √ e−3t/2 sint ,33ПределыПоэтому диагональные переходные вероятности равны √3 √3 −3t/2pxx (t) = a + eb cost + c sint , x = A, B, C,2(3n + 2)!n=0Корни (собственные числа) равныκ = 0, − ± i229что то же самое, qNN = −qN = 0.

При этом все матрицы Qk являютсяверхними треугольными (так как отсутствует стрелка j − 1 ← j). Значит,таковой будет и матрица etQ . Прямое уравнение имеет вид Ṗ(t) = P(t)Q,начальное условие P(0) = I, поэтомуṗii = − pii ,ṗij = − pij + pij−1 ,ṗiN = piN−1 ,ṗNN = 0,pii (0) = 1,pij (0) = 0,piN (0) = 0,pNN (0) = 1,1 6 i < N,1 6 i < j < N,1 6 i < N,230Глава 2. Цепи Маркова с непрерывным временеми, поскольку, очевидно, pij (t) = 0 для всех i > j, это уравнение допускаетрекуррентное решение видаиз уравнения ṗii = − pii следует, что pii (t) = e− t , для 1 6 i < N,из уравнения ṗii+1 = − pii+1 + e− t следует, что pii+1 (t) = te− t , для1 6 i < N,а из уравнения ṗii+2 = − pii+2 +для 0 6 i < N − 1 и т.

д.2te−получаем pii+2 (t) =t( t) 2 − te ,2§ 2.2. Марковские цепи с непрерывным временем...231Полезное наблюдение состоит в том, что если qi = 0, то состояниеi поглощающее, т. е. pii (t) ≡ 1 ∀ t > 0 (и обратное утверждение такжеверно).Типичные траектории ( (0) , Q) ц.м.н.в. представлены на рис. 2.16. Онивсе прыгают вверх на одну единицу и согласно выше приведенному описанию со временем достигают состояния N, где и остаются навсегда.Общая формулаpij (t) =( t) j−i − te ,(j − i)!1 6 i < j < N − 1,иpiN (t) = 1 −наконец,N−iX( t) ll=0l!e− t , 0 6 i < N;Рис. 2.16pNN ≡ 1.В матричной формеP(t) = etQe−t −e1t= 0e−...0...0tt( t) 2 −e2!t −te1...0tP ( t) l − tel>N l!P ( t) l − t ...e .l>N−1 l!......01...(2.2.12)Пример 2.2.8.

Если взять Q-матрицу вида−−1 1 00 ... 00... 00 0 − 0 −1 1 0 0 − ... 0 0  0 0 −1. . . . . . . . . . . . . . . . . .  = . . . . . . . . .00000... −... 001−то она образует цикл, см. рис. 2.17.0000... 0 0... 0 0 ... 0 0 ,. .

. . . . . . .. . . −1 1. . . 0 −1(2.2.13)Видим, что при t → ∞ выполняется условиеpij (t) → 0 ∀ 0 6 i < j < Nи piN (t) → 1 ∀ 0 6 i < N.Таким образом,lim pij (t) =t→∞jN00т. е. P(t) → . . .000...000...0............∼ N11∼ N.. . . ..1 ∼ N.Здесь N — вероятностное распределение, сосредоточенное в состоянииN (цепь с течением времени заканчивает движение в состоянии N).Рис. 2.17Матрица P(t) = etQ здесь будет иметь периодическую структуру:pij (t) = pi+l,j+l (сложение по mod N) ∀ i, j, l,232Глава 2. Цепи Маркова с непрерывным временемДействительно, суммируя переходные вероятности по всем состояниям,которые «проектируются» в состояние j, когда при движении вдоль действительной временной оси образуется цикл, получим ответpij (t) = p1,j+1−i (t) =и∞X( t) j−i+lNl=0(j − i + lN)!pij (t) = p1,N+j−i+1 (t),1 6 j < i 6 N.Пример 2.2.9. Многие свойства, которые обсуждались ранее, можнобез большого труда перенести на бесконечные матрицы.

Например, рассмотрим бесконечную Q-матрицу вида−1 1 0 0 . . .−0 0 ......(см. рис. 2.18).... 0 −1 1 0 . . .  0 0 −1 1 . . .  ,..............Чтобы найти элементы pii+l (t), можно использовать прямое или обратноеуравнения(2.2.16)Ṗ(t) = P(t)Q или Ṗ(t) = QP(t)ṗii = − pii (t),i=1. 0 . .=.. ... .. .....233с начальным условием P(0) = I. Для l = 0 (т.

е. для диагональных элементов) уравнения принимают видe− t , 1 6 i 6 j 6 N,При t → ∞ распределение pij (t) стремится к равномерному дискретномураспределению i = 1/N ∀ i. Это единственное решение уравнения Q =NP= 0, удовлетворяющее условиям i > 0,i = 1.0 −Q=0 0 −§ 2.2. Марковские цепи с непрерывным временем...pii (0) = 1,откуда следует, чтоpii (t) = e−t∀ i = 0, 1, .

. . и t > 0.(2.2.17)Для l = 1 (один шаг вправо от главной диагонали) получимṗii+1 = − pii+1 (t) + pii (t) (прямое уравнение),ṗii+1 = − pii+1 (t) + pi+1i+1 (t) (обратное уравнение),откуда следует, чтоpii+1 (t) = te−(2.2.14)t∀ i = 0, 1, . . . , и t > 0.(2.2.18)В общем случае, для любых l = 0, 1, . . . имеем.ṗii+l = − pii+l (t) + pii+l−1 (t) (прямое уравнение),ṗii+l = − pii+l (t) + pi+1i+l (t) (обратное уравнение),что приводит к формуламpii+l (t) =Рис. 2.18В этом примере матрица Qk вновь является верхней треугольной привсех k = 0, 1, . .

., значит, таковой является и матричная экспонентаP(t) = etQ=∞ k kXt Qk=0k!, t > 0.Элементы pii+l (t) при l > 0 требуется вычислить, ноточно тождественно равны нулюp00 (t) p01 (t) p02 (t) . . . 0p11 (t) p12 (t) . . .P(t) =  00p22 (t) . . ....0(2.2.15)элементы pii−l (t) уж.( t) l −el!t∀ i = 0, 1, . . . , и t > 0.(2.2.19)Наконец, поскольку переходы i → j для j < i невозможны,pii−l (t) = 0 ∀ i = 0, 1, . . . , l = 1, 2, . .

. и t > 0.В матричной формеe− 0P(t) =  0...tt −e1e− t0...t( t) 2 −e2!t −te1e−..t.t...(2.2.20)закон Пуассона с t0 закон Пуассона с t =0 0 закон Пуассона с t ... .............................. .(2.2.21)234Глава 2. Цепи Маркова с непрерывным временемЭквивалентным образом, можно получить тот же результат, перейдяк пределу(N)P(t) = etQ = lim etQ , t > 0,(2.2.22)где Q (N) и p (N) (t) = etQ — это матрицы вида (2.2.11) и (2.2.12) соответственно.Матрицы P(t), t > 0, определенные формулой (2.2.21), имеют свойства, перечисленные в теореме 2.1.4.

Очевидно, каждая матрица P(t)стохастическая, задающая набор переходных вероятностей на Z + . Можноповторить определение 2.2.1 для I = Z+ = {0, 1, . . .} и (бесконечной)матрицы переходных вероятностей P(t), определенных формулой (2.2.21).Типичные траектории ( (0) , Qt)-ц.м.н.в. (выходящей из 0) изображены нарис. 2.16. Все скачки ц.м.н.в. равны 1.Суммируем вышесказанное.Теорема 2.2.10.

Пусть матрица Q имеет вид (2.2.14). Семействоматриц P(t) из соотношения (2.2.21) удовлетворяет равенствам(2.2.15) и (2.2.22) и имеет следующие свойства:а) полугрупповое свойствоP(t + s) = P(s)P(t),s, t > 0;(2.2.23)б) P(t) — единственное решение уравненийt > 0,прямое уравнение,t > 0,обратное уравнение,причем P(0) = I;dkP(t)= Qk ∀ k = 1, 2, . . ..в)kdt(2.2.24)t=0Прямые и обратные уравнения часто называют уравнениями Колмогорова, по имениАндрея Николаевича Колмогорова (1903–1987), великого русского математика, внесшеговажный вклад во многие области теоретической и прикладной математики.

Колмогоров известен как создатель строгого обоснования всей теории вероятностей, и более 50 лет онбыл признанным лидером советского математического сообщества. В отличие от некоторыхдругих советских математиков и физиков того периода, он никогда не занимал особо высоких административных постов и не участвовал непосредственно в ядерной или космическойпрограммах. Однако он имел непререкаемый авторитет как в математике, так и в вопросах,выходящих за ее пределы, и служил образцом для подражания в российском и международном интеллектуальном сообществе.Другое имя, связанное с этими уравнениями, — Уильям Феллер (1906–1970), известныйамериканский математик, родившийся в Загребе (Хорватия).

Он существенно прояснил рольпрямых и обратных уравнений в теории вероятностей и ее многочисленных приложениях. Он235также написал классический учебник в двух томах [F], по-видимому никем не превзойденныйдо настоящего времени.N→∞(N)dP(t) = P(t)Q,dtdP(t) = QP(t),dt§ 2.3. Процесс Пуассона§ 2.3. Процесс ПуассонаПриключение Пуассона4(Из серии «Фильмы, которые не вышли на большой экран».)Процесс Пуассона был введен в примере 2.2.9 в предыдущем параграфе. Ввиду его важности введем специальные обозначения.Определение 2.3.1.

Характеристики

Список файлов лекций