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

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

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

Тогда(Xn) n>0 — марковская цепь рождения и гибели с переходными вероятностямиСтандартными рассуждениями находим соотношение для вероятности h i == P i (попасть в 0):i u1 ,h0 = 1, hi = pi hi+1 + qi hi−1 , i > 1,pi ui+1 = qi ui , ui = hi−1 − hi ,iq . . . q1= i,pi . . . p 10+ ··· +u1 + · · · + u i = h 0 − h i , h i = 1 − u 1 (иi−1).hj = (hji , i ∈ I) и hjj = 1.При этом hji ≡ 1 всегда является решением:X1PT = 1, так как (1PT) i =pil = 1 ∀ i ∈ I.lqi = pi = 1/2 при i 6= 2m ,qi = 1/3, pi = 2/3 при i = 2m .qiui+1 = ui =pi105в среднем путешественник вновь вернется в i, если он вылетает из i.

Прирешении этой задачи следует быть внимательным и предусмотреть случай,когда не существует рейсов между некоторыми заданными аэропортами.б) Рассмотрите бесконечное дерево T с корнем R, где для всех m > 0все вершины, находящиеся на расстоянии 2m от R, имеют степень 3,а все остальные вершины (исключая R) имеют степень 2. Покажите, чтослучайное блуждание на T возвратно.Решение. а) Пусть X0 = i — начальный аэропорт, Xn — аэропорт n-гоназначения, а I обозначает множество аэропортов, достижимых из i.

Тогда(Xn) — неприводимая цепь Маркова на I, следовательно, среднее время§ 1.10. Детальный баланс и обратимостьГлава 1. Цепи Маркова с дискретным временем104I.2. Уравнения для kji = E i (время достижения состояния j) таковы:Xkjj = 0, kji = 1 +pil kjl = 1 + (kj PT) i , i 6= j,l∈I, l6=jгдеkj = (kji , i ∈ I) и kjj = 0.Если условиться считать, что 0 · ∞ = 0, то kji = (1 − ij) ∞ всегда являетсярешением, если цепь неприводима.Эти уравнения получают, рассматривая условное распределение относительно первого скачка. Векторы hj и kj имеют верхний индекс,обозначающий конечное состояние, в то время как нижние индексы их106Глава 1. Цепи Маркова с дискретным временемjjki= E k (время пребывания в i, прежде чем цепь вернется в k)kk= 1,таковы:ki=Xкомпонент hi и ki обозначают начальные состояния.

Решение, которое мыищем, определяется как минимальное неотрицательное решение, удовлетворяющее условиям нормировки hjj = 1 и kji = 0.II.1. Уравнения дляkl pli ,lk=илиkЭти уравнения получают, рассматривая условное распределение относительно последнего скачка, и векторы k имеют в качестве верхнегоиндекса начальные состояния.

Решение определяется из условий ki > 0и kk = 1.II.2. Аналогично для стационарного распределения (или, в общем случае, инвариантной меры) выполняется равенство= P.i>0иPi= 1.iII.3. Решение уравнений детального балансаi pij=j pjiвсегда является инвариантной мерой. Если при этом107Далее, если блок Oi расположен над апериодическим замкнутым классом Ci , то он имеет предел при n → ∞. Предельный блок — это такаясубстохастической матрица, что сумма элементов вдоль каждой строкилежит между 0 и 1, но не обязательно равна 1. (Может быть и так, чтосумма вдоль строки равна 0, что означает, что целая строка превращаетсяв пределе в нулевую строку.) Предельный блок не равен нулю, если исходP (n)pjk ,ный блок ненулевой. (Точнее, для любого состояния j ∈ I суммаk∈Cii 6= k,P, если k возвратно.Решение определяется из условий§ 1.10.

Детальный баланс и обратимостьPii= 1, то мы полу-чаем стационарное распределение. Как правило, найти решение уравненийдетального баланса нетрудно (конечно, если решение вообще существует),поэтому эти уравнения являются мощным средством для отыскания стационарного распределения, и ими рекомендуется пользоваться во всех такихслучаях.Мы закончим этот параграф обсуждением общей картины асимптотического поведения итераций P n конечной переходной матрицы P с несколькими сообщающимися классами; см.

рис. 1.8–1.10. Как мы уже говорилив § 1.2, блок O0 стремится к 0. Предыдущие результаты показывают, чтоесли блок Ci соответствует апериодическому замкнутому сообщающемусяклассу, то в процессе итераций при n → ∞ этот блок будет сходиться(i)к блоку Πi , образованному повторением строки (i) = ( j , j ∈ Ci), представляющей собой единственное стационарное распределение класса C i .которая задает вероятность перехода из j в замкнутый класс C i за n шагов,не убывает с ростом n.) Более того, даже если блок O i был изначальнонулевым, он может превратиться в ненулевой при достаточно большом nи возрастать к своему предельному значению при n → ∞.С другой стороны, если класс Ci периодичен с некоторым конечнымпериодом vi > 1 и содержит периодические подклассы Wi1 , .

. . , Wivi , тоудобно рассуждать в терминах степени P vi . Предположим для удобства,что матрица P неприводима, так что у нас есть всего один сообщающийсякласс C, состоящий из всего пространства состояний I; этот класс замкнути распадается на периодические подклассы W 1 , . . . , Wv ; см. рис.

1.10. Мызаметили ранее, что W1 , . . ., Wv представляют собой непересекающиесянаборы сообщающихся классов матрицы P vi ; каждый такой набор можнорассматривать как самостоятельную переходную матрицу. Таким образом,весь анализ следует начать заново... Мы видим, что может появитьсянечто вроде «фрактальной структуры», т. е. структура разбиения блокаповторяется на каждом последующем шаге. Так как множество I конечно,мы можем достичь нижнего уровня, на котором все классы замкнуты.К счастью, возможные «хитрые» примеры, как правило, не появляютсяна практике, и, наверное, не стоит о них и думать...Итак, предположим для удобства, что каждый из этих периодическихподклассов Wl , l = 1, .

. . , v, образует замкнутый сообщающийся классдля Pv . Следовательно, каждый из них является носителем единственногоинвариантного распределения (l) переходной матрицы Pv . Таким образом,в матрице Pnv соответствующие блоки расположены на главной диагонали,и при n → ∞ стремятся к предельным стохастическим матрицам Π l , образованным повторением строк (l) , l = 1, .

. . , vi . Как и ранее, обозначимчерез Π матрицу, образованную предельными блоками Π 1 , . . . , Πv . Тогдапоследовательность матриц P n распадается на v подпоследовательностей(Pnv+k), k = 0, . . . , v − 1. В каждой подпоследовательности матрица P nv+kсходится при n → ∞ к матрице ΠP k = Pk Π.Сходимость подобного рода появляется, когда P обладает такой структурой, как показано на на рис. 1.9: если блок C определяет периодическийкласс с периодом v, то он ведет себя так, как описано в предыдущем108Глава 1. Цепи Маркова с дискретным временем§ 1.11. Управляемые и частично наблюдаемые цепи Марковапараграфе.

Тогда блок O ведет себя точно так же: мы имеем сходимостьматриц Pnv+k для каждого фиксированного k = 0, . . . , v.Теперь читатель готов представить себе, что происходит в общем случаепри итерации Pn конечной переходной матрицы P. Мы ответим (хотя бычастично) на вопрос, зачем это нам вообще нужно, в § 1.12 –1.15.109Типичная траектория (Xn) имеет вид:§ 1.11.

Управляемые и частично наблюдаемыецепи МарковаThe Crying Control Theory7(Из серии «Фильмы, которые не вышли на большой экран».)Начнем этот параграф популярным примером управляемой цепи Маркова.Пример 1.11.1. Пусть проверяются m >> 1 различных объектов, приэтом объекты выбирают в случайном порядке, без возвращения, по одному в каждый момент времени. Необходимо выбрать наилучший объект,но к ранее отвергнутым возвращаться нельзя.

Рассмотрев подходящуюц.м.д.в., обоснуйте утверждение, что оптимальная стратегия состоит в том,чтобы отвергнуть первые k объектов, а затем взять тот, который первымокажется лучше, чем все предыдущие. Определите k = k(m). Проверьте,что m/k ≈ e для больших m.Решение. Положим X0 = 1 и(m + 1, если первый объект наилучший,X1 =i,если i-й объект лучше, чем все предыдущие,m + 1, если первый или X1 -й объект является наилучшим,X2 = j,если j-й объект — первый после момента времени X1 ,лучший, чем все предыдущие.В общем случае при r > 2m + 1, если Xr−1 = m + 1 или Xr−1 -й объект является наилучшим,Xr = j,если j-й объект — первый после момента времени Xr−1 ,лучший, чем все предыдущие.Тогда X1 , X2 , .

. . , Xm принимают значения 2, 3, . . . , m + 1 (и Xn = m + 1при n > m). Кроме того, Xn+1 > Xn > n , если Xn 6 m, 1 6 n 6 m.7 Ср.с названием фильма «Crying Freeman».Рис. 1.33Для того чтобы траектория (Xn) задавалась ц.м.д.в., необходимо отсутствие памяти в условных вероятностяхP (Xn+1 = j|Xn = i, Xn−1 = in−1 , . . . , X1 = i1 , X0 = 1) = pij .На помощь приходит комбинаторика:P (i-й объект наилучший среди {1, . . .

, i}) =(i − 1)!1= ,i!iиP (j наилучший, а i — 2-й наилучший после j среди {1, . . . , j}) ==(j − 2)!1=.j!j(j − 1)Тогда при 1 6 j 6 m получаемp1j = P 1 (X1 = j) == P (j наилучший, 1 — 2-й наилучший после j среди {1, . . . , j}) =иp1m+1 = P 1 (X1 = m + 1) = P (1 — наилучший из всех) =1.m1,j(j − 1)110Глава 1. Цепи Маркова с дискретным временемДалее,P 1 (X2 = j|X1 = i) =P 1 (X2 = j, X1 = i)=P 1 (X1 = i)= P (j наилучший, i — 2-й наилучший после j среди {1, . .

. , j};1 — 2-й наилучший среди {1, . . . , i}) / P (i наилучший,1 — 2-й наилучшийсреди {1, . . . , i}) =и1/j(j − 1) · 1/ (i − 1)i=,1/i(i − 1)j(j − 1)1 6 i < j 6 m,P 1 (X2 = m + 1, X1 = i)=P 1 (X1 = i)P (1 — 2-й наилучший среди {1, . . . , i}; i наилучший из всех)==P (i наилучший, 1 — 2-й наилучший среди {1, . . . , i})1/m · 1/ (i − 1)i== , 1 < i 6 m.1/i(i − 1)mP 1 (X2 = m + 1|X1 = i) =В общем случае, для 1 6 i < j 6 m получаемpij = P 1 (Xn+1 = jXn = i, Xn−1 = in−1 , . . . , X1 = i1) ==а для j = m + 1 имеем=1/m · 1/ (i − 1) · 1/ (in−1 − 1) .

. . 1/ (i1 − 1)i= ,1/i(i − 1) · 1/ (in−1 − 1) . . . 1/ (i1 − 1)m0 1/1 · 2 1/1 · 3 . . . 1/ (m − 1)m000000......00Имеем d(m) = 1, что тривиально. Чтобы задать d(m − 1), напомним,что состояние m − 1 означает, что (m − 1)-й объект является наилучшим среди объектов {1, . . . , m − 1}. Вероятность того, что он являетсянаилучшим среди всех, равна pm−1,m+1 = (m − 1) /m, что больше, чем(m − 1) /m(m − 1) = 1/m = pm−1,m pm,m+1 , а это есть вероятность того, чтоm-й объект — наилучший из всех. Следовательно, d(m − 1) = 1.Аналогично для определения d(m−2) сравниваем p m−2,m+1 = (m−2) /mи pm−2,m pm,m+1 + pm−2,m−1 pm−1,m+1 , что равноm−2m−2m−1m−21+·=+ .m(m − 1)(m − 1) (m − 2)mm(m − 1)mИли, что эквивалентно, мы сравниваем1 ии т.

д. Очевидно,11+,m−1m−2d(m) = d(m − 1) = . . . = d(k + 1) = 1,d(k) = . . . = d(1) = 0,11+ ... +> 1.km−1При больших m ищем такое k, чтоZm1ydy = lnm= 1,kk1 6 i 6 m,и, конечно, pm+1m+1 = 1. Матрица перехода размера (m + 1) × (m + 1)имеет вид1 /m02/2 · 3 . . . 2/ (m − 1)m2 /m 003 /m 00. . . 3/ (m − 1)m. . . . .

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

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