Главная » Просмотр файлов » Цепи Маркова

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

Файл №1121219 Цепи Маркова (Лекции в различных форматах) 13 страницаЦепи Маркова (1121219) страница 132019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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−pkp 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) не имеет стационарного распределения.

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

Тип файла
PDF-файл
Размер
4,15 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6510
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее