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

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

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

Часть a) уже рассматривалась в примере 1.3.2 (см. такжерис. 1.12).б) применим следующую теорему: Для неприводимой ц.м.д.в. с инвариантным распределением , среднее время возвращения в состояние i равно 1/ i .Здесь A = 3/ (18 + 6) = 1/8, и, следовательно, ответ 8.в) применим следующую теорему: Для неприводимой ц.м.д.в. с инвариантным распределением среднее число посещений состояния jдо возвращения в состояние i равно j / i .Здесь C = 1/4, и ответ 2.(В гл.

2 мы дадим строгое определение процесса Пуассона. Однако,если это определение уже известно, то следующую задачу можно легкорешить сейчас.)Глава 1. Цепи Маркова с дискретным временемЗадача 1.16.9. Предположим, что (Xt) t>0 и (Yt) t>0 — независимыепуассоновские процессы, оба с интенсивностью . Рассмотрим разностьWt = Xt − Yt . Пусть J1 обозначает момент первого скачка процесса Wt .Найдите совместное распределение J1 и WJ1 .Пусть M и N — натуральные числа.

Найдите вероятность того, что(Wt) t>0 достигнет уровня N раньше, чем уровня −M.Покажите, что среднее время достижения процессом (W t) t>0 множества {−M, N} равноMN.2Указание. (j + 1) 2 − 2j2 + (j − 1) 2 = 2.Решение. Из построения следует, что J1 — показательная с.в., WJ1принимает значения ±1 с вероятностью 1/2 и с.в. J1 и WJ1 независимы.Кроме того, (Wt) является цепью Маркова с непрерывным временем нацелочисленной решетке Z с интенсивностью 2 , а соответствующая цепьскачков является простым симметричным случайным блужданием.Следовательно, если hi = P i (достичь N прежде, чем −M), то1212hi = hi−1 + hi+1 , h−M = 0,111+ ki−1 + ki+1 ,222hk = (1 − p)qhk−1 + (pq + (1 − p) (1 − q))hk + p(1 − q)hk+1 ,илиhk =(1 − p)qp(1 − q)h+h ,p + q − 2pq k−1p + q − 2pq k+1k ∈ Z,и h0 = 1.

Конечно, нас интересует минимальное неотрицательное решение.Рассмотрим сначала k > 0. Рекурсия0 − (1 − p)q/ (p(1 − q))(hk , hk+1) = (hk−1 , hk)1 (p + q − 2pq) / (p(1 − q))имеет собственные значения 1 и q(1 − p) / (p(1 − q)), и, следовательно,допускает общее решениеhk = A + BM187Следовательно, P x,y (Xn = Yn) = P x−y (Wn попадает в 0) = 0 при нечетном|x − y|. При x − y = 2k обозначим эту вероятность символом h k . Имеютместо уравнения:hN = 1.В общем виде hi = A + Bi, откуда следует, что h0 =.M+NАналогично если ki = E i (достичь N или −M), тоki =§ 1.16. Вопросы по теории цепей Маркова с дискретным временеми q(1 − p) kp(1 − q), если p 6= qhk = A + Bk, если p = q.k−M = kN = 0.hk = q(1 − p) k. p(1 − q) k.p(1 − q)Для k 6 0 ответ симметричен: если q 6 p, то hk ≡ 1, а если q > p, тоhk =В общем виде ki = A + Bi + Ci2 , откуда следует, что ki = NM/ (2 ) +MN.+ (N − M)i/ (2 ) − i2 / (2 ) и k0 =2Задача 1.16.10.

Пусть (Xn) n>0 и (Yn) n>0 — независимые простые случайные блуждания на Z, выходящие из x и y соответственно. На каждомшаге (Xn) n>0 совершает скачок вправо с вероятностью p и влево — с вероятностью 1 − p. Для (Yn) n>0 соответствующие вероятности равны q и 1 − q.Для всех целых чисел x, y и p, q из (0, 1) найдите вероятность (x, y, p, q)того, что Xn = Yn при некотором n > 0.Решение. Поскольку Xn = Yn тогда и только тогда, когда Xn − Yn = 0,удобно рассмотреть разность Wn = Xn − Yn , которая является случайнымблужданием на Z с вероятностями переходапри j − i = 2,p(1 − q)pij = pq + (1 − p) (1 − q) при j − i = 0,при j − i = −2.(1 − p)qЕсли p 6 q, то q(1 − p) / (p(1 − q)) > 1. Тогда минимальное неотрицательное решение получается при A = 1, B = 0: hk ≡ 1.

Если p > q,то q(1 − p) / (p(1 − q)) < 1. Тогда минимальное неотрицательное решениеполучается при A = 0, B = 1:q(1 − p)Ответ для (x, y, p, q) получается с помощью соответствующей подстановки значений x, y, p и q.Задача 1.16.11. Пусть (Xn) n>0 , (Yn) n>0 и (Zn) n>0 — простые симметричные случайные блуждания на Z. Тогда Vn = (Xn , Yn , Zn) являетсяц.м.д.в. Чему равны вероятности перехода для этой цепи?Покажите, что с вероятностью 1 цепь (Vn) n>0 попадает в состояние(0, 0, 0) только конечное число раз.186Глава 1.

Цепи Маркова с дискретным временемРешение. Вероятности перехода для (Vn) равны(1/8, если |i − l| = |j − m| = |l − n| = 1,p (i,j,k) (l,m,n) =0в противном случае.Наша цель — показать, что< ∞.2 /3 001/4 5/16 0 .1 /6 1 /6 1 /2 1 /6 1 /6 1 /6ki = E i (число шагов, необходимое чтобы попасть в 3).Соответствующие уравнения имеют вид23k0 = 1 + k0 + k1 ,715k + k1 + k2 ,16 04161k2 = 1 + (k0 + k1 + k2),6k1 = 1 +откуда получаем77,6k1 =34,3k2 =181.30n=1:56n=2:2536−14 5 n6Из граничных условий+ −1 n4, n > 1.=0инаходимПредположим, что цепь выходит из состояния 0. Найдите среднее числопереходов до того момента, когда цепь впервые попадет в состояние 3.Найдите вероятность того, что цепь в первый раз попадает в состояние2 на n-м шаге.Решение. Положим(n)(n−1)− p02=P 0 (T2 = n) = p024= 3/13,+116( n)дится. Таким образом, цепь (Vn) невозвратна, откуда и следует утверждение.Задача 1.16.12.

Рассмотрим ц.м.д.в. с пространством состояний{0, 1, 2, 3} и матрицей вероятностей переходаи(2n)k0 =Собственные значения равны 1, 5/6 и −1/4. Следовательно, 5 n −1 n(n)p02 = P 0 (T2 6 n) = A + B+C,(n)13.6Как и ранее, p (0,0,0) (0,0,0) = 0, когда n нечетно. Кроме того, p (0,0,0) (0,0,0) =1(2n) 3(2n)(2n) 3= p00, где p00= Cn2n . Следовательно, p00≈, и ряд схо3 /21 /37/16 1 /61 /21 /3 2 /3 07/16 1/4 5/16001n=0P=(n)p (0,0,0) (0,0,0)189Далее, из 0 цепь может попасть в состояние 2, только пройдя черезсостояние 1. Значит, можно рассмотреть приведенную цепь с матрицейперехода!∞X§ 1.16.

Вопросы по теории цепей Маркова с дискретным временем188=524= 10/13. Таким образом, ответ имеет вид 3 5 n10 −1 n+, n > 1.13 6134Задача 1.16.13. Последовательность случайных выпуклых многоугольников строится по следующей схеме. На каждом шаге имеющийсямногоугольник разбивают на два новых так: случайным образом выбирают два разных ребра и соединяют средние точки этих ребер; затемслучайным образом выбирают один из образовавшихся многоугольникови рассматривают его на следующем шаге. Каждый раз, когда делают случайный выбор, все возможные исходы считаются равновероятными, и всерезультаты такого случайного выбора независимы.

Для n = 0, 1, 2, . . .пусть Xn + 3 обозначает число ребер многоугольника на n-м шаге; такимобразом, Xn принимает неотрицательные целые значения. Найдите матрицувероятностей перехода для ц.м.д.в. {Xn , n > 0}.Объясните, почему предел limn→∞ P (Xn = i) существует и не зависитот числа ребер исходного многоугольника; найдите, чему равен этот пределдля каждого i = 0, 1, 2, . .

.Решение. Если рассматриваемый многоугольник — треугольник, то наследующем шаге может быть получен треугольник или четырехугольникс вероятностью 1/2. Если же на данном шаге имеется четырехугольник, тона следующем шаге могут появиться треугольник, или четырехугольник,или пятиугольник, каждый с вероятностью 1/3. Аналогично из пятиугольника можно получить треугольник, четырехугольник, пятиугольник илишестиугольник, каждый с вероятностью 1/4. Эти рассуждения наводят намысль, что матрица вероятностей перехода для01Xn = число ребер − 3 = 2 , n = 1, 2, .

. . , ...имеет вид1 /2 1 /2000 ...... . . .1 / 3 1 / 3 1 / 3 01 4 1 4 1 4 1 4 0 . . .  .////§ 1.16. Вопросы по теории цепей Маркова с дискретным временемявляется апериодической, поскольку pii > 0. Следовательно, она имеет неболее одного такого стационарного распределения = { i }, что P =(n)и j = lim pij ∀ j ∈ I. Чтобы решить уравнение P = , запишемn→∞0ит. е.i+1i==i(m + 3) (m + 2)P (Xn+1 = 0|Xn = m) = P (Xn+1 = m + 1|Xn = m) =121(m + 3)=.2(m + 3) (m + 2)m+2В общем случае, если мы выбираем ребра i и i + s mod m и при этом междуними находится s − 1 ребро (таких возможностей по-прежнему m + 3), тоследующим многоугольником может быть (s + 2)-угольник (и Xn+1 = s − 1)или (m + 5 − s)-угольник (и Xn+1 = m + 2 − s), 1 6 s 6 (m + 3) /2.

ТогдаP (Xn+1 = s − 1|Xn = m) = P (Xn+1 = m + 2 − s|Xn = m) =121(m + 3)=.2(m + 3) (m + 2)m+2(Для нечетного m значение s = (m + 3) /2 приводит к такому же значению1/ (m + 2) для вероятности P (Xn+1 = s − 1|Xn = m).) Отсюда следует нашеутверждение о матрице перехода.Рассмотренная выше матрица неприводима, так как p ij =(j−i−1)при j 6 i + 1 и pij0−13+i11> 0i+2> pii+1 pi+1i+2 .

. . pj−1j > 0 при j > i + 1. Она+14+ ... =−122−131Введем предположение индукцииi=1i!=2i+1=2+ ... =1+i + 1 i− 11i+1 ,i > 1,1. Отсюда находимi + 1 i−13. Еслито число способов выбрать два ребра равно C 2m+3 =2мы соединим соседние ребра i и i + 1 mod m (m + 3 возможностей), то следующим может быть треугольник (при этом Xn+1 = 0) или (m + 4)-угольник(при этом Xn+1 = m + 1).

Тогда=1211+i + 1 i− 1i+2........................===1иДействительно, если Xn = m, т. е. n-й многоугольник имеет m + 3 ребра,19101i!−=11i + 1 (i − 1)!Следовательно, 0 = e−1 иПуассона со средним 1.i=0=120=13!0.0.ТогдаГлава 1. Цепи Маркова с дискретным временем1900(i + 1)!1 −1e , т. е.i!(i + 1 − i) =0(i + 1)!.является распределениемЛев Толстой в повести «Дьявол» пишет: «Обыкновенно думают, что самые обычныеконсерваторы — это старики, а новаторы — это молодые люди. Это не совсем справедливо.Самые обычные консерваторы — это молодые люди. Молодые люди, которым хочется жить,но которые не думают и не имеют времени подумать о том, как надо жить, и которые поэтомуизбирают себе за образец ту жизнь, которая была.»Задача 1.16.14.

Предположим, что экзаменатор должен оценить оченьбольшое число ответов. Каждый ответ, независимо от остальных, являетсяправильным с вероятностью p и неправильным с вероятностью 1 − p.У экзаменатора есть две стратегии оценивания. Первая стратегия (которуюон применяет вначале) состоит в проверке каждого ответа, правильныйответ получает полный балл, а неправильный ответ получает нулевой балл.Вторая стратегия менее точная; каждый ответ с вероятностью q и независимо от предыдущих он оценивает по прежней схеме (т. е. выставляетполный балл для правильного ответа и нулевой балл для неправильного);либо с вероятностью 1 − q он просто выставляет полный балл, не проверяя,верен ответ или нет.

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

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