Цепи Маркова (1121219), страница 13
Текст из файла (страница 13)
Цепи Маркова с дискретным временемПример 1.8.6. Однородный процесс рождения и гибели. Этот процесс является случайным блужданием на Z+ , таким что§ 1.8. Положительная и нулевая возвратность. IIиmk = E k (время возвращения в k) =pii+1 = p, pii−1 = 1 − p, i > 1, p01 = q, p00 = 1 − q,= p i−1 + (1 − p) i+1 , i > 1,= q 0 + (1 − p) 2 ,0 = (1 − q) 0 + (1 − p) 1 ,1=iкак и выше, имеют решение i = A + B(p/ (1 − p)) , i > 0.При p < 1/2 имеет смысл свести число параметров к одному, т. е.положить A = 0. Для i = 0, 1 мы получаем одно и то же уравнениеi1−p(1 − p)откуда следует, что B =01ii > 1;11+ i+1 ,2 i− 12i > 1,= A + Bi, i > 1.
При i = 1, 0 эти уравнения имеютi=q0+122,0= (1 − q)0+121,откуда следует, что B = 0 иp/ (1 − p)1 − p/ (1 − p)q(1 − 2p). Таким образом,p(1 + q − 2p)1 − 2p=,1 + q − 2pимеют общее решениевид= pB.q1−p,pсм. § 1.5. Следовательно, при p > 1/2 цепь невозвратна.Остается рассмотреть случай p = 1/2. В этом случае fi = 1 и цепьвозвратна. Уравнения инвариантностиiq, k ∈ Z+ .P 0 (T0 < ∞) = 1 − q + q P 1 (достичь 0),P i (достичь состояния i − 1) =независимо от значения q.Действительно, уравнения инвариантностиЧтобы нормировать, запишемpppp2++.
. . = B +1=B +2kмы видим, что если P 1 (попасть в 0) < 1, то цепь невозвратна. Однакоp < 1/2 : положительная возвратность,p = 1/2 : нулевая возвратность,p > 1/2 : невозвратность01При p > 1/2 мы должны рассмотреть fi = P i (Ti < ∞). Записавгде 0 6 p, q 6 1. Рассмотрим случай 0 < q 6 1 и 0 < p < 1, когда цепьнеприводима. Тогда классификация такова:q8180qp=p 1−pi0,=Bp(1 − 2p + q),q(1 − 2p)i > 1,≡ A, i > 1,0=1A,2qи неотрицательныеP инвариантные меры соответствуют значениям A > 0.Мы видим, чтоi < ∞ только при A = 0.
Таким образом, цепьiне имеет стационарного распределения и, следовательно, имеет нулевуювозвратность.Значит, при p = 1/2 справедливо следующее: а) все неотрицательныеинвариантные меры = ( i) взаимно пропорциональны, и каждая такаямера, не равная 0 тождественно, имеет компоненты i = A > 0 при i > 1и 0 = A/ (2q) > 0. Кроме того, б) все векторы k , k > 0, должны бытьинвариантными и, следовательно, взаимно пропорциональными. При такойнормировке, что kk = 1, единственно возможными являются случаи а)kk0i ≡ 1 и 0 = 1/ (2q) ∀ k, i > 1 и б) i = 2q ∀ i > 1.
(Это выглядит ещеболее удивительным, так как можно было ожидать, что при k > 1 должновыполняться неравенство< ... <kk−2<kk−1<1<kk+1<k00 = i < k < ∞,pq0 = k < i < ∞,0 < i, k < ∞, i 6= k,цепь вернется в k) == E k (числа посещений состояния i, прежде чемi−kp, 1 − p iqp= i =,p1−pkp 1−p k,kiи цепь является положительно возвратной, что и утверждалось.Далее, при p < 1/2 выполняются соотношенияikk+2< ...,82Глава 1. Цепи Маркова с дискретным временемki= P k (числа посещений состояния i, прежде чем цепь вернется в k, равно n) = 1 2 n−11=1−∀ i > k > 1,2(i − k)2(i − k)как и в случае симметричного случайного блуждания на Z.Cherchez la Gamme: a Musical On Vectorial ReturnИщите Гамму: мюзикл о векторных временах возвращенияПример 1.8.7.
Пусть X = (Xn : n > 0) — случайное блуждание намножестве целых чисел, причем шаги влево либо вправо совершаютсяс вероятностью 1/2 в любой момент времени. Покажите, чтоP (X2n = 0|X0 = 0) = Cn2n 1 2n2,и докажите, что м.ц.д.в. X возвратна.Пусть X0 = 0, m — натуральное число, а N — случайное число попаданий в точку m, прежде чем цепь вернется в 0.Найдите P (N > 1) и докажите, что 1 2 2m1−1 n−12m, n > 1.(2n)n=1(возвращение за нечетное число шагов√невозможно), и ее можно оценитьприформулы Стирлинга: n! ≈ 2 nn+1/2 e−n . Это приводит к рядуP помощи√1/ n, который расходится. Таким образом, в силу теоремы о том,n5 Играслов, ср.
«Cherchez La Femme» («Ищите женщину»).Pn(n)pii = ∞,заключаем, что состояние 0 возвратно. Эти же аргументы можно использовать и для любого состояния i. Следовательно, цепь возвратна. (Это жеутверждение следует из другой общей теоремы о том, что возвратностьявляется свойством класса.)Символ P будет означать здесь P 0 , т. е. распределение цепи ( 0 , P).Тогда P (N > 1) = P 0 (побывать в m перед возвращением в 0). Взяв условную вероятность по первому шагу, запишемP (N > 1) =1P (побывать в m перед возвращением в 0),2 1где P i обозначает распределение цепи ( i , P).
Положимhi = P i (побывать в m перед возвращением в 0),тогда1212hi = hi−1 + hi+1 , 1 6 i < m.Общее решение имеет вид hi = A + Bi. Из условий h0 = 0, hm = 1 находим,что A = 0, B = 1/m. Следовательно, h1 = 1/m и P (N > 1) = 1/ (2m).Очевидно,1−1= P (N = 0) = P 0 (вновь попасть в 0, прежде чем попасть в m).2mВ силу симметрииP m (вновь попасть в m, прежде чем попасть в 0) = 1 −Решение. Изучим вероятность P (X2n = 0|X0 = 0) = p00 того, чтотраектория длины 2n, которая начинается в точке 0, возвращается в точку0 через 2n шагов.
Каждая такая траектория должна состоять из n шаговвправо и n влево. Общее число таких траекторий равно C n2n , и вероятностькаждой из них равна (1/2) 2n . Эти рассуждения и приводят к формуле дляP (X2n = 0|X0 = 0).∞∞PPP (Xn = 0|X0 = 0) совпадает сP (X2n = 0|X0 = 0)Суммаn=1что состояние возвратно тогда и только тогда, когдаTimes5(Из серии «Фильмы, которые не вышли на большой экран».)P (N = n) =83и в силу асимметрии модели нет никаких видимых оснований предположить, что возможно равенство kk−1 = kk+1 .)Наконец, нетрудно проверить, что§ 1.8. Положительная и нулевая возвратность. II1.2mДля того чтобы траектория, начинающаяся в точке 0, попала в событие{N = n} при n > 1, она должна пройти через m, прежде чем вернуться в 0,n − 1 раз вернуться в m, не попадая ни разу в 0, и лишь затем устремитьсяв 0, уже не возвращаясь в m.
В силу строго марковского свойстваP (N = n) =111−2m2mn−1 12m,где последний множитель равен P m (попасть в 0, прежде чем вернуться в m)и получен опять в силу симметрии. Отсюда и следует требуемый результат.Пример 1.8.8. Рассмотрим цепь Маркова с пространством состоянийS = {0, 1, 2, .
. .} ∪ {10 , 20 , 30 , . . .} и вероятностями перехода, показаннымина рис. 1.24, где 0 < q < 1 и p = 1 − q.84Глава 1. Цепи Маркова с дискретным временем§ 1.8. Положительная и нулевая возвратность. II85Чтобы определить, имеет ли место нулевая или положительная возвратность, рассмотрим уравнение инвариантности = P, эквивалентноесистеме уравнений010Рис.
1.24q,1 − pa2=1q2−1и аналогичноb = q + pba,i+1 q+ i0 q,p + i−1 p,(i−1) 0i > 1,i0 > 2.==1 1 − q2q q=1 1 − q2qq1q0,0,102020,i−10,==1 1 − q2qqpqa2.1 − pap(1 + q)a2 − (pq + 1)a + q = 0,01= (1 − q) 1 +0q= 1 − q 2 2= 1 − q2 i−130i0qq=1 − q2q0,0.0,∞ 1 − q2 i−1 −1 q2 + q − 1X1= 1++1= 2.i=1и решениями являютсяq.1 − q2qq + 2qqВ счетном пространстве состояний много точек. Больше, чем звездна небе, и намного больше, чем песчинок в песках Сахары.(Из серии «Так говорил суперлектор».)Нас интересует минимальное решениеq< 1, что достигается тогда и только тогда, когда q <1 − q20,и стационарное распределение существует тогда и только тогда, когда оба2ряда, составленныеиз√ i и i0 , сходятся, что выполняется при (1 − q ) /q << 1, т.
е. q > ( 5 − 1) 2. Следовательно, цепь имеет нулевую возвратность,√√когда q = ( 5 − 1) 2, и положительно возвратна, когда q > ( 5 − 1) 2.В последнем случаеТаким образом,a=1 и a===По индукции находим общие формулыiи a=q+03откуда следует, чтоb=i01b = P i0 (достичь i)(эти вероятности не зависят от значения i в силу однородности рассматриваемой цепи).
Вычисляя условные вероятности относительно первогоскачка и используя строго марковское свойство, находимa = q + pba2 ,iЭти уравнения допускают рекуррентное решение:Для каждого значения q определите, является ли цепь невозвратной,положительно возвратной или имеет нулевую возвратность.В случае, когда цепь положительно возвратна, вычислите инвариантноераспределение.Решение.
При i > 1 положимa = P i (достичь i − 1),= 1 q,= 0,√5−1.2√Следовательно, цепь возвратна тогда и только тогда, когда q > ( 5 − 1) 2,√и невозвратна тогда и только тогда, когда q < ( 5 − 1) 2.Пример 1.8.9. Пусть (Wn) — это процесс рождения и гибели на Z+ == {0, 1, 2, . . .} со следующими вероятностями перехода:1pi,i+1 = pi,i−1 = ,2p01 = 1.i > 1,86Глава 1. Цепи Маркова с дискретным временем87Действительно,P 0 (N > 1) = 1(так как p01 = 1),Сопоставляя (Wn) с симметричным простым случайным блужданием (Yn)на Z или иным способом, докажите, что (Wn) — это возвратная ц.м.д.в.Докажите, что (Wn) имеет нулевую возвратность.Вычислите векторы k = ( ki , i ∈ Z+) для цепи (Wn), k ∈ Z+ .Наконец, пусть W0 = 0, а N — число посещений состояния 1, преждечем цепь вернется в 0. Покажите, что P 0 (N = n) = (1/2) n , n > 1.Решение. Заметим, что (Wn) является неприводимой ц.м.д.в.
Крометого, Wn = |Yn |, где (Yn) — симметричное случайное блуждание «по ближайшим соседям» на Z. Следовательно,§ 1.9. Сходимость к положению равновесия. Предельные пропорцииP 1 (возвращение в 1 без прохождения цепи через 0) = 1 − p 10 =(так как цепь достигает 0 из 1 с вероятностью 1/2 и возвратна),и12P 1 (достичь 0 без возвращений в 1) = p10 = .P |i| ((Wn) возвращается в i) > P i ((Yn) возвращается в i) ∀ i ∈ Z,но правая часть равна 1, так как цепь (Yn) возвратна. Следовательно,вероятность в левой части также равна 1, и цепь (W n) также возвратна.Чтобы проверить нулевую возвратность, достаточно доказать, что цепь(Wn) не имеет стационарного распределения.