Цепи Маркова (1121219), страница 36
Текст из файла (страница 36)
Цепи Маркова с непрерывным временемнулевая, причем мы использовали это свойство в доказательстве теоремы2.1.6 (см. соотношение (2.1.9)). Вообще-то, структуру матрицы Qn можновосстановить по диаграмме из стрелок, представляющей исходную Q-мат(2)рицу Q. Скажем, чтобы вычислить элементы qij , рассмотрим все путиi → k → j длины 2, перемножим qik и qkj вдоль каждого из этих путейи просуммируем полученные произведения.
Далее, для Q 3 возьмем все путидлины 3 и т. д.С другой стороны, для любого a > 0, произведение Q-матрицы и числа a является Q-матрицей. Аналогично сумма Q-матриц Q1 + Q2 являетсяQ-матрицей (значит, и любая линейная комбинация a 1 Q1 + a2 Q2 или, болееnPобщим образом,aj Qj с неотрицательными коэффициентами aj являетсяj=1Q-матрицей).Замечание 2.1.12.
При заданной Q-матрице и любом t > 0 матрицаP(t) = etQ стохастическая по теореме 2.1.6. Поэтому существует ц.м.д.в.,для которой P(t) — это матрица переходных вероятностей.Однако неверно, что любую матрицу вероятностей перехода P можнозаписать в виде etQ для некоторой Q-матрицы и t > 0. Здесь можетпомочь упомянутое ранее свойство в) det etQ = et(tr Q) . Например, матрицыперехода!1 0 0011 0 0,1 /2 1 /20 1 0нельзя записать в виде etQ , так как их определители нулевые или отрицательные, в то время как et(tr Q) > 0.Теперь, используя полугрупповое свойство, докажем, что det e tQ == et(tr Q) .
В самом деле,det e(t+s)QsQ tQsQtQ= det(e e ) = (det e ) (det e ).§ 2.1. Матрицы перехода и Q-матрицыВ других случаях необходим более глубокий анализ. Например, рассмотрим матрицу перехода!P=ddq=det etQ =det(I + tQ) .dtdtt=0t=0Это означает, что q — коэффициент при t в многочлене det(I + tQ), а онв точности равен tr Q. Заметим, что det etQ → 0 при t → ∞ за исключениемслучая, когда Q = 0.0 1 00 0 11 0 0.Предположим, что ее можно записать в виде etQ .
В таком случае рассмотрим матрицу перехода P0 = etQ/m ; очевидно, (P0) m = P. Нетруднопроверить, что для матрицы перехода!P0 =0 0 11 0 00 1 0ее квадрат равен (P0) 2 = P. Но для m = 3 это невозможно (в матрице Pслишком много нулей). Действительно, матрица P описывает детерминированные передвижения.
Отсюда следует, что и матрица P 0 должна бытьдетерминированной. Но ни одна из шести возможных перестановок дляматрицы с тремя состояниями не удовлетворяет желаемому уравнению.Итак, матрицу P нельзя представить в виде etQ .Замечание 2.1.13. Общее мультипликативное свойство матричнойэкспоненты имеет видeQ1 +Q2 = eQ1 eQ2 = eQ2 eQ1 ,(2.1.13)если и только если матрицы Q1 и Q2 коммутируют, т. е. если Q1 Q2 = Q2 Q1 .Отсюда следует полугрупповое свойство e (s+t)Q = esQ+tQ = esQ etQ , поскольку матрицы (sQ) и (tQ) коммутируют.Проверить равенство (2.1.13) можно прямыми вычислениями. ЕслиQ1 Q2 = Q2 Q1 , то(Q1 + Q2) n =nXk=0Далее, определитель det etQ непрерывен (и даже дифференцируем) по t,причем det e0·Q = det I = 1.
Значит, det etQ = etq для некоторого (действительного) q. Наконец, чтобы найти q, заметим, что219nXn!n!Qk1 Qn2 −k =Qk Qn−k .k!(n − k)!k!(n − k)! 2 1(2.1.14)k=0Как и в скалярном случае, произведение матричных рядов∞∞X(tQ1) k X (tQ2) lk=0k!l=0l!можно удачно переупорядочить и получить ряд∞ (t(Q + Q )) nP12n=0n!, равныйet(Q1 +Q2) . Однако без предположении о коммутации Q1 Q2 = Q2 Q1 в разложении (2.1.14) возникнут перемежающиеся произведения матриц Q 1 и Q2и мы не получим формулы (2.1.14).220Глава 2. Цепи Маркова с непрерывным временем§ 2.2. Марковские цепи с непрерывным временем...221§ 2.2. Марковские цепи с непрерывным временем:определения и основные конструкции.Марковское и строго марковское свойстваThe Markov Chain Saw Massacre1(Из серии «Фильмы, которые не вышли на большой экран».)Определение 2.2.1.
Цепь Маркова с непрерывным временем, (конечной) Q-матрицей Q и начальным распределением — это семейство такихслучайных величин (Xt , t > 0) со значениями в I, чтоa) P (X0 = i) = i ,б) для любых 0 < t1 < t2 < . . . < tn и любых состояний i0 , , . . . , in ∈ Iвыполняется равенствоP (X0 = i0 , Xt1 = i1 , . . . , Xtn = in) == i0 pi0 i1 (t1)pi1 i2 (t2 − t1) . .
. pin−1 in (tn − tn−1),(2.2.1)где pij (t) — элемент матрицы P(t) = etQ .Типичная траектория (путь) ц.м.н.в. (Xt) показана на рис. 2.5.Рис. 2.6i0 , i1 , . . . , in в моменты времени t0 = 0, t1 , . . ., tn ; их поведение междуэтими моментами времени произвольно.Матрицу Q часто называют генератором цепи Маркова (Xt) с непрерывным временем. Саму цепь называют ( , Q)-цепью Маркова с непрерывным временем (ц.м.н.в.) и генератором Q. Как и в случае цепей Маркова с дискретным временем (ц.м.д.в.), мы часто будем работать с цепями,выходящими из фиксированного состояния i, т.
е.= i . Такая цепьназывается ( i , Q)-ц.м.н.в.Из определения 2.2.1 вытекают следующие свойства.I. Матрица P(t) = (pij (t)) называется матрицей перехода в моментвремени t. Она задает условные вероятностиpij (t) = P (Xt = j | X0 = i) = P (Xt+s = j | Xs = i).(2.2.2)В терминах траекторий pij (t) задает полную вероятность всех путей из iв j за время t.Рис.
2.5Далее мы увидим, что произвольная траектория а) проводит случайноевремя, распределенное как ∼ Exp(qi), в состоянии i, а затем б) прыгаетв состояние j 6= i с вероятностью qij /qi ; см. (2.2.10).Стандартное соглашение состоит в том, что траектории непрерывнысправа. Это означает, что с вероятностью 1 при всех t > 0lim Xt+h = Xt .h&0В случаях, когда это соглашение не слишком существенно, будем изображать траектории в виде непрерывных линий.Важно понять, что событие {X0 = i0 , Xt1 = i1 , . . . , Xtn = in } в соотношении (2.2.1) включает все траектории, проходящие через состояния1 Ср.c названием фильма «Texas Chainsaw Massacre» («Техасская резня бензопилой»).Рис.
2.7II. Отсутствие памяти у условных вероятностей. Оно состоит в том, чтоP (Xtn = j | Xtn−1 = i, Xtn−2 = in−2 , . . . , X0 = i0) == P (Xtn = j | Xtn−1 = i) = pij (tn − tn−1),(2.2.3)т. е. условная вероятность P (Xtn = j | Xtn−1 = i, Xtn−2 = in−2 , . . . , X0 = i0)не зависит от t1 , .
. . , tn−1 и i0 , i1 , . . . , in−2 .222Глава 2. Цепи Маркова с непрерывным временем§ 2.2. Марковские цепи с непрерывным временем...223Чтобы доказать равенство (2.2.3), нужно использовать определениеусловной вероятностиP (Xtn = j | Xtn−1 = i, Xtn−2 = in−2 , .
. . , X0 = i0) ==P (X0 = i0 , . . . , Xtn−1 = i, Xtn = j)P (X0 = i0 , . . . , Xtn−1 = i)и подставить выражение из формулы (2.2.1).III. Безусловная вероятностьXP (Xt = j) =i pij (t) = ( P(t) )jРис. 2.9(2.2.4)iзадает полную вероятность множества траекторий, находящихся в состоянии j в момент времени t.VI. На самом деле любая (конечная) Q-матрица имеет стационарное распределение, т. е. собственная вектор-строка= ( i) с нулевымсобственнымзначениеминеотрицательнымикомпонентами,для которыхPi = 1. В частности, 0 является собственным значением любой Q-матiрицы.VII.
Как и в случае дискретного времени, если(1)(2)P(t) → Π = . . .dP(t) = P(t)Q,dt0 = P(t)Q|t=0 = Q.(2.2.5)Иными словами, — собственный вектор-строка матрицы Q с нулевымсобственным числом.--,--является стационарным распределением:→∞ (i)=→∞+,+См. теорему 2.8.1 из § 2.8.Например, если в примере 2.1.8 выполняется условие= (i)=+> 0, тоlim P( + t)(i).(2.2.6)lim P( )P(t)P(t) = (ΠP(t)) (i) =(2.2.7)является (единственным) стационарным распределением. Но при = == 0 мы имеем P(t) ≡ I и любой вектор будет инвариантным.VIII. Как и в случае дискретного времени, можно определить строгомарковское свойство. Назовем случайную величину T со значениямив [0, ∞] моментом остановки, если для любого t > 0 событие {T << t} определяется набором (X : 0 6 < t).
Иными словами, индикатор1(T < t) является функцией только от (X : 0 6 < t).dP(t) =0=dt(i)-IV. Как и в случае дискретного времени, имеет место марковское свойство, которое обеспечивает условную независимость прошлого и будущегопри фиксированном настоящем.Теорема 2.2.2. Пусть (Xt) — это ( , Q)-ц.м.н.в.
Тогда для любогозаданного t > 0 и любого состояния i при условии, что {Xt = i},прошлое (Xs , 0 6 s < t) и будущее (Xt+s , t > 0) независимы и (Xt+s)является ( i , Q)-ц.м.н.в.V. Говорят, что = является стационарным распределением, еслии только если P (Xt = j) = j для любых t, j, т. е. P(t) ≡ . При этомвектор-строка обращается в нуль под действием матрицы Q:(i)то каждая строкаРис. 2.8(m)224Глава 2.
Цепи Маркова с непрерывным временем§ 2.2. Марковские цепи с непрерывным временем...225событие {T < ∞, XT = i}, прошлое (Xt , 0 6 t 6 T) и будущее(Xt+T , t > 0) независимы и (Xt+T , t > 0) — это ( i , Q)-ц.м.н.в.Рис. 2.12 иллюстрирует случай, когда T = Hi , где Hi — время переходав состояние i.Рис.
2.10Рис. 2.12A Passage Time to India3(Из серии «Фильмы, которые не вышли на большой экран».)Once Upon a Stopping Time2IX. Ц.м.н.в. (Xt) с генератором Q обладает следующими свойствами:при условии, что Xt = i, qi = −qii > 0, остаточное время пребыванияRi в состоянии i имеет экспоненциальное распределение с параметром qi = −qii :P (Ri > |Xt = i) = P (Xt+s = i ∀ 0 6 s <(Из серии «Фильмы, которые не вышли на большой экран».)Примером момента остановки вновь является момент достижения подмножества состояний A ⊂ I:HA = inf [s > 0 : Xs ∈ A] ,(2.2.8)поскольку1(HA 6 t) = 1(∃ s ∈ [0, t] : Xs ∈ A)зависит только от (X , 0 6 6 t).Мы будем особо интересоваться моментами достижения заданного состояния i (также называемыми моментами перехода в i, как и дляц.м.д.в.).Hi = inf [s > 0 : Xs = i] .(2.2.9)Теорема 2.2.3.
Пусть (Xt) — ( , Q)-ц.м.н.в. и T — момент остановки. Тогда для любого состояния i при условии, что произошло2 Ср.с названием фильма «Once Upon a Time».| Xt = i) = e−qi .Рис. 2.11Далее, в момент t + Ri цепь совершает прыжок в состояние j с веbij = qij /qi :роятностью pP (Xt+Ri = j | Xt = i) =qij.qi(2.2.10)Это свойство будет проверено позже.Если для состояния i выполняется условие qi = 0, то qij = 0 ∀ j;такое состояние называется поглощающим. Соответствующая диаграммаиз стрелок не содержит стрелок, выходящих из состояния i.Замечание 2.2.4. Определение 2.2.1 выделяет так называемую однородную цепь Маркова. Здесь вероятности pij (t) зависят только отвремени t, за которое совершается переход из состояния i в j.
В болееобщем случае неоднородных цепей нужно рассматривать вероятностьpij (s, t + s), t, s > 0, того, что состояние в момент t + s есть j, при условии,что состояние в момент s есть i. Примеры таких цепей появятся в § 2.4.3 Ср.с названием фильма «A Passage to India»226Глава 2. Цепи Маркова с непрерывным временем§ 2.2. Марковские цепи с непрерывным временем...227Нам нужно вычислить pii (t) = (etQ) ii . Очевидно, pii (t) = p11 (t) ∀ i, t, опятьже в силу симметрии.Рассмотрим приведенную Q-матрицу размера 2 × 2 с состояниями 0и 1:−e=Q/N − /N(N + 1)с собственными числами 0 и = −. Эту матрицу можно привеNсти к диагональному виду. Собственные вектор-строки имеют вид (1, 1)и (N, −1). ПоэтомуРис.
2.13Пример 2.2.5. Некий вирус может находиться в N +1 штамме 0, . . . , N.Он сидит в своем штамме случайное время, распределенное как ∼ Exp ( ),а затем с равными вероятностями мутирует в один из остальных штаммов.Найдите вероятность того, что в момент времени t он будет сидеть в томже штамме, что и в начальный момент,p11 (t) = (etQ̃) 11 = A + Be−(N+1)tN.Как и в примере 2.1.8, если искать решение в виде A + Be t , то получимтакие значения:1N, B=A=N+1иp11 (t) =P (в момент t штамм тот же, что и в момент 0).N+11N+e−N+1N+1(N+1)tN= pii (t).В силу симметрииpij (t) =111(1 − pii (t)) =−e−NN+1N+1(N+1)tN,i 6= j.Остается заключить, чтоpij (t) −→Рис. 2.14Решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
