Цепи Маркова (1121219), страница 29
Текст из файла (страница 29)
. , ul , чтоhx, i − ln∗ji=1lXui piji=1j=1uju= (uT P) j T j = uj .(uT P) j(u P) jj=10(Если максимальное собственное значение 0 ( ∗) матрицы R большечем 1, получаем противоречие: соответствующие собственные векторыT(0) Tи ϕ (0) имеют строго положительные компоненты, и должно былобы выполняться равенствоuT R n = (lPтак как)) n hu, ϕ (0) i(0) T∗+ O((1 − ) n) .(1.15.37)lXj=1lxj lnX(uT P) juj= hx, i −xj ln T .uj(u P) jКомбинируя равенства (1.15.42) и (1.15.41), приходим к равенству в формуле (1.15.40). Это завершает доказательство соотношения (1.15.32).Пример 1.15.10.
Лемма 1.15.9 дает возможность точно вычислятьΛ∗ (x) в случае неприводимой апериодической цепи Маркова с двумя состояниями. В этом случае матрица вероятностей перехода P имеет вид1−,(1.15.43)P=ul= ( 1,2)имеет вид∈ (0, 1). Стационарное распределение=1+,2=+e.(1.15.44)Легко найти собственные значения матрицы(1 − )e 1e2,R =12(1 − )ej=1где ,Если теперь взять точную верхнюю грань правой части неравенства(1.15.38) по положительным векторам u, то получим неравенство (1.15.34).Остается проверить неравенство, противоположное (1.15.34): u1lXujΛ∗ (x) 6 sup xj ln: u = ... , u1 , . . .
, ul > 0 . (1.15.39)T(u P) j1−uj. (1.15.38)(uT P) jj=1xj lnlX(1.15.42)j=1i=(1.15.41)xj = 1.hx, i +∗),При этом правая часть соотношения (1.15.41) равна∈ Rl ] > hx,0( ) :Λ∗ (x) = sup [hx, i− ln0() = lnПоскольку скалярное произведение hu, ϕ (0) i двух положительных векторовположительно, равенство (1.15.37) несовместимо с (1.15.36). Единственновозможным является равенство 0 ( ∗) = 1, а в этом случае u = (0) .Следовательно, ln 0 ( ∗) = 0, и0(j=1 =lX(uT R ) j=xj lnuj=1∗jxj lnlXui pij e(1.15.36)В самом деле, для любых j = 1, . . . , l выполняется равенствоlX(1.15.40)Но очевидно, что такой вектор u существует: это собственный вектор(0) Tматрицы R , соответствующий максимальному собственному значению 0 ( ). В самом деле, для u = (0) мы имеем uT R = 0 ( )uT , т.
е.т. е. uT Rn = u ∀ n > 1.j=1uj.(uT Pi) juT R = u T ,xj lnи рассмотрим матрицу R(= R ∗ ) с неотрицательными элементами pij e ,i, j = 1, . . . , l. Матрица R неприводимая и апериодическая, следовательно,к ней применима теорема 1.15.7.Можно показать, что uT является собственным вектором матрицы R,соответствующим собственному значению 1:lX0( ) 6(1.15.35)j=1uj,(xT P) jxjlXi=∗(uT P) j, j = 1, . . . , l, где hx, u j= ln∗jПусть задан вектор u ∈ Rl со строго положительными компонентамиu1 , . . ., ul ; положим§ 1.15. Большие уклонения для цепей Маркова с дискретным временемГлава 1. Цепи Маркова с дискретным временем1742.176Глава 1.
Цепи Маркова с дискретным временем§ 1.16. Вопросы по теории цепей Маркова с дискретным временем177Максимальное собственное значение равноq1(1 − )e 1 + (1 − )e 2 + 4( + − 1) + ((1 − )e 1 + (1 − )e 2 ) 2 .0( ) =2(1.15.45) xЧтобы вычислить преобразование Лежандра Λ∗ (x), где x = x1 , при2меним лемму 1.15.9. Можно предположить, что x 1 , x2 > 0 и x1 + x2 = 1.Положим x1 = 1 − c, x2 = c, 0 6 c 6 1. Суммаu1u+ x2 ln T 2(uT P) 1(u P) 2x1 lnРис. 1.45из правой части равенства (1.15.32) принимает видu− (1 − c) ln(1 − + K) − c ln 1 − −, где K = 2 .Ku1(1.15.46)(1.15.48)Немало стрел, летящих наугад,Неведомые цели породятИ снова будет лучник удивлён,Попав туда, куда не метил он.− ln(1 − ),− ln(1 − ),∗Λ (x) =(O! many a shaft, at random sent,Find mark the archer little meant,And many a word, at random spoken,May soothe or wound a heart that’s broken.(1.15.47)c = 1,c = 0.и(1 − 2c)) 2 + 4 c(1 − ) (1 − ) (1 − c)2 (1 − ) (1 − c)(p(1 − 2c) +Λ (x) =−∗Максимизируя по K, для 0 < c < 1 находим§ 1.16.
Вопросы по теории цепей Маркова с дискретнымвременем на экзаменах «Математическиетреножники» в Кембриджском университете(пер. Г. Кружкова)Прямые, хотя и несколько утомительные вычисления показывают, чтоΛ∗ (x) = 0 тогда и только тогда, когда x1 = 1 , x2 = 2 .В частном случае, когда + = 1, ц.м.д.в.
(Xn , n > 1) превращаетсяв последовательность н.о.р.с.в. В этом случаеΛ( ) = e 1 + e 2 ,(1.15.49) xи преобразование Лежандра Λ∗ (x), x = x1 , уже обсуждалось в началеэтого параграфа. См. рис. 1.45.2Вальтер Скотт (1771–1832), шотландский писатель и поэтЗадача 1.16.1. Каким соотношением связаны инвариантное распределение вероятностей и среднее время возвращения для состояний конечнойнеприводимой цепи Маркова?Частица движется по 2n вершинам гиперкуба {0, 1}n следующим образом: на каждом шаге она с равной вероятностью может перейти в каждуюиз n соседних (смежных) вершин, независимо от прошлых переходов.(Две вершины являются смежными, если евклидово расстояние междуними равно 1.) Первоначально частица находится в вершине (0, 0, . .
. , 0).Найдите математическое ожидание числа шагов до того момента, когдачастицаа) впервые вернется в вершину (0, 0, . . . , 0),б) впервые попадает в вершину (0, 0, . . . , 0, 1),в) впервые попадает в вершину (0, 0, . . . , 0, 1, 1).178Глава 1. Цепи Маркова с дискретным временемРешение. В данной задаче используем симметрию. Инвариантными1(x) = n ∀ x ∈ {0, 1}n .
Для конечной неприво2mx =вероятностями являютсядимой цепи Маркова среднее время возвращения m x в состояние x равно1.(x)Таким образом, среднее число шагов до первого возвращения частицыв вершину 0 = (0, 0, . . . , 0) равно 2n .Кроме того,2n = m0 = 1+nX1+E (время достижения вершины 0 | начальная вершина e i) =ni=1= 1 + E (время достижения вершины e n | начальная вершина 0),§ 1.16. Вопросы по теории цепей Маркова с дискретным временемЗадача 1.16.2. Три девочки A, B и C играют в настольный теннис.В каждой игре две девочки играют друг против друга, а третья отдыхает.Победитель любой фиксированной n-й игры снова играет в (n + 1)-й игре.Вероятность того, что девочка x победит девочку y в любой игре, в которойони играют друг против друга, равна sx / (sx + sy) для x, y ∈ {A, B, C}, x 6=6= y, где sA , sB , sC соответствуют игровым навыкам этих трех девочек.1. Представьте этот процесс в виде ц.м.д.в., определив пространствовозможных состояний и переходные вероятности.2.
Найдите вероятность того, что те же две девочки, которые игралидруг против друга в первой игре, будут опять играть друг против другав четвертой игре. Покажите, что эта вероятность не зависит от того, какиеименно две девочки участвовали в первой игре.3. Какова предельная пропорция для числа игр, сыгранных каждой издевочек?Решение для 1 и 2 содержится в примере 1.1.13.3. Инвариантное распределение вероятностей, являющееся решениемуравнения P = , находим из уравнений детального балансагде e i = (0, 0, . . .
, 0, 1, 0, . . . , 0) (1 на i-м месте, остальные нули). Такимобразом,E (время достижения вершины e n | начальная вершина 0) = 2n − 1.Аналогично, рассматривая первые два шага из начального состояния,находим2n = 2 +1[n · 0+n2(x) =1 sA + s B + s C − s x, x = A, B, C.2 sA + s B + s CНапример,(A)pAB =1 sB + s CsC=2 sA + s B + s C sB + s CДалее,Обозначив последнее математическое ожидание через A, получаем уравнение2n = 2 +n−1A,nоткуда следует, чтоA = (2n − 2)n.n−1sA + s B + s CЗадача 1.16.3. Рассмотрим ц.м.д.в. (Xn , n = 0, 1, .
. .) на Z1 с начальным состоянием X0 = 0 и вероятностями переходовP(i, i + 1) = p,E (время достижения вершины 0 | начальная вершина (0, . . . , 0, 1, 1)) == E (время достижения вершины (0, . . . , 0, 1, 1) | начальная вершина 0).(B)pBA .Таким образом, пропорция игр, в которых играет девочка x, равна 1 − (x),т. е.1 sA + s B + s C + s x.2+ n(n − 1) E (время достижения 0 | начальная вершина (0, . . .
, 0, 1, 1))] .179P(i, i − 1) = q(i ∈ Z),где p + q = 1. Пусть Yn = |Xn |. Покажите, что (Yn , n = 0, 1, . . .) являетсяцепью Маркова и найдите ее вероятности перехода.Решение. Из условия задачи Y0 = 0. Ясно, что если Yn = i, то Yn+1 == i ± 1, i > 1, а если Yn = 0, то Yn+1 = 1. Рассмотрим условнуювероятностьP (Yn+1 = i + 1|Yn = i, Yn−1 = yn−1 , . . . , Y0 = y0 = 0)при i > 0.
При i = 0 эта вероятность равна 1 и не зависит от y 1 , . . . , yn−1 .Обозначим событие в условии буквой A:A = {Yn = i, Yn−1 = yn−1 , . . . , Y0 = y0 = 0}.180Глава 1. Цепи Маркова с дискретным временемПусть A+ и A− — пересечения события A с событиями {Xn > 0} и {Xn << 0}:A+ = {Yn = i, Yn−1 = yn−1 , . . . , Y0 = y0 = 0, Xn > 0},A− = {Yn = i, Yn−1 = yn−1 , . .
. , Y0 = y0 = 0, Xn < 0}.Тогда P (Yn+1 = i + 1|A) можно представить в видеP (Xn+1 = i + 1|A+) P (Xn > 0|A) + P (Xn+1 = −i − 1|A−) P (Xn < 0|A) == p P (Xn > 0|A) + q P (Xn < 0|A).Далее, каждая траектория из X0 = 0 в Xn = i имеет зеркальноеотражение — траекторию из X0 = 0 в Xn = −i с теми же Y0 , . . ., Yn . Длякаждой такой пары траекторий можно записатьP X0 (траектория) =pi XP (отражение),qi 0поскольку вероятность «петель», появляющихся вдоль траектории (между первым и последним моментами, когда цепь X попадает в заданноесостояние), одинакова для обеих траекторий и единственное отличие между вероятностями возникает при переходе цепи из некоторого состоянияв соседнее состояние (в соответствующем направлении) между петлями.ПоэтомуqiP (A) = P (траектория) + P (отражение) = P (траектория) 1 + ipиP (Xn > 0|A) =P (траектория)pi= i,P (траектория) + P (отражение)q + piP (Xn < 0|A) =qi.q i + piТогда вероятностиP (Yn+1 = i + 1|A) =pi+1 + qi+1pi+1 + qi+1и P (Yn+1 = i − 1|A) = 1 −pi + q ipi + q iне зависят от y1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
