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

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

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

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

е. состояние k возвратно.3. Если матрица P неприводима, то для любых i, k ∈ I существуют(n)(m)такие m, n > 0, что pik > 0 и pki > 0. При условии, что матрица Pkявляется инвариантным и, следовательно, k Pm =возвратна, векторk nk= P = . Таким образом,X(m)kk (m)k (m)i =l pli > k pki = pki .а эта сумма стремится к kj при n → ∞.2) Пусть теперь матрица P неприводима и возвратна. Тогда k является− k тожеинвариантным вектором: k P = k . Значит, вектор e =инвариантен: e = e P, и в силу п. 1. он неотрицателен: e i > 0 ∀ i ∈ I,а при i = k вектор e k = k − kk = 1 − 1 = 0.(n)Далее, для заданного i ∈ I существует такое n > 1, что p ik > 0.

Тогда,посколькуX(n)(n)e l plk0 = ek => ei pik,kk.16n<∞P k (Tk = n) = P k (Tk < ∞) := fk 6 1 ==P k (X1 = j, Tk > 1) + P k (X2 = j, Tk > 2) + . . . + P k (Xn = j, Tk > n),26n<∞X73Теперь в силу неотрицательности последнее выражение ограничено снизувеличинойi : i6=k 16n<∞§ 1.7. Инвариантные распределения.

Положительная и нулевая возвратность. I72l pli1. . . pin−1 j .Определение 1.7.6. В случае а) говорят, что неприводимая цепь Маркова (или матрица P) положительно возвратна, а в случае б) — нульвозвратна.Если число состояний #I конечно, то случай б) невозможен. Следовательно, неприводимая конечная ц.м.д.в. всегда положительно возвратна74Глава 1. Цепи Маркова с дискретным временемположительны. Тогдаа) невозвратность: Pi (время возвращения Ti < ∞) < 1, т. e. Pi (Ti == ∞) > 0 ∀ i ∈ I. Или, что эквивалентно,kii=.Pi ((Xn) не посещала i после какого-то конечного момента времени) = 1kk, т. е.1=iiстационарному распределению, у которого всеможно восстановить, выполнив деление:k75и имеет (единственное) инвариантное распределение = ( i). Более того,стационарные вероятности i строго положительны.Теперь видно, что в общем. Pслучае, если матрица P положительновозвратна, то нормировка ji =j приводит к (единственному)§ 1.7.

Инвариантные распределения. Положительная и нулевая возвратность. I(1.7.12)k∞X{ i}(n)pii < ∞ ∀ i ∈ I, или, что эквивалентно, hj = Pj (попасть в i) < 1n=0для некоторых состояний j и i;б) возвратность: Pi (время возвращения Ti < ∞) = 1, т. e. Pi (Ti = ∞) == 0 ∀ i ∈ I. Или, что эквивалентно,Pi ((Xn) может попасть в i в бесконечно большие моменты времени) = 1Другими словами, нами получена следующая теорема.Теорема 1.7.7.

В неприводимой положительно возвратной цепидля любых состояний k 6= iсо стационарным распределениемвыполняется равенствои(1.7.13)и∞X{ i}(n)pii = ∞ ∀ i ∈ I, или, что эквивалентно, hj = Pj (попасть в i) = 1n=0для всех состояний j и i. В этом случае для любого i для вектора i = ( ij)из равенства (1.7.12) вытекает, что 0 < ij < ∞, и этот вектор задаетi.инвариантную меру для (Xt); все такие инвариантные меры имеют видki−1i= (bk) × вектор для любых состояний i, k.В частности, вектор3. Далее, для неприводимой возвратной ц.м.д.в. может выполнятьсяследующее:∀ i ∈ I;а) нулевая возвратность: mi = Ei (время возвращения Ti) = ∞ Pв этом случае не существует такой инвариантной меры = ( i), чтоj <,kоткуда следует, что mk = 1/ k .Мы завершим этот параграф подведением итогов по утверждениямотносительно возвратности и невозвратности, приведенным выше.1.

Для переходных вероятностей неприводимой ц.м.д.в. с более чем од(m)ним состоянием справедливы неравенства 0 < pij < 1 для всех состоянийi, j ∈ I, где m > 1 может зависеть от i и j (поглощение отсутствует).2. Неприводимая ц.м.д.в. (Xn) может быть невозвратной или возвратной:1и существует единственное стационарное распределение= Pi> 0; в этом случаеjk= m k , E i Ti =1k=j< ∞; следовательно, не существует стационарного распределения;б) положительная возвратность: mi < ∞ ∀ i ∈ I; в этом случаедляPлюбой инвариантной меры = ( i) справедливо неравенствоj < ∞j= ( i), гдеиijiiiXmk =Таким образом,i : i6=kД о к а з а т е л ь с т в о. Из уравнения (1.7.4) мы находим, чтоXXkkE k Tk = 1 + E k (Tk − 1) = 1 +i =i < ∞.Ei (время, проведенное в k до Ti) =k< ∞.(1.7.14)k1mk := E k Tk = среднее время возвращения в состояние k =Для случая i = k имеет место следующий результат.Теорема 1.7.8.

В неприводимой положительно возвратной цеписо стационарным распределением для любого состояния k выполняется равенство.kE k (число попаданий в i, прежде чем цепь вернется в k) =iдля любых состояний i, k.iКонечная неприводимая ц.м.д.в. всегда положительно возвратна.i=76Глава 1. Цепи Маркова с дискретным временем§ 1.8.

Положительная и нулевая возвратность. IIНе знать того, что было сделано в былые времена,означает навсегда остаться ребенком.Не извлекая никакой пользы из прошлого,человечество навсегда останется в младенчестве.§ 1.8. Положительная и нулевая возвратность. II77задают времена между (l − 1)-м и l-м моментами возвращения в состояниеi или продолжительность l-й экскурсии из состояния i, l = 1, 2, .

. .Очевидно, Ti(1) = Ti ; см. рис. 1.23.Марк Тулий Цицерон, (106–143 до н.э.), римский оратор и государственный деятельВ этом параграфе мы будем работать с начальным распределением= i , т. e. будем рассматривать цепи, стартующие из определенногосостояния, и использовать обозначения P i и E i . Предполагаем, что пространство состояний I счетно. Чтобы упростить формулы, будем опускатьиндекс I: утверждения типа «∀ i» означают ∀ i ∈ I. Мы также предполагаем, что переходная матрица P рассматриваемой ц.м.д.в.

(X n) неприводима.Начнем с повторения определений 1.5.1 и 1.7.6. Напомним, чтоTi = min[n > 1 : Xn = i]обозначает время возвращения в состояние i.Определение 1.8.1. Положим fi = P i (Ti < ∞) и mi = E i Ti . Состояние i называетсявозвратным (В),если fi = 1, илиPnpii(n)< ∞, илиP i (Xn = i для бесконечного числа n) = 1,положительновозвратным (ПВ),если mi = E i Ti < ∞,nP i (Xn = i для бесконечного числа n) = 0.(1.8.1)Эти свойства являются свойствами класса, и если переходная матрицаP неприводима, то все состояния ПВ, или НВ, или Н.Определение 1.8.2.

Для l = 0, 1, . . . определим последовательные(l)времена возвращения H (l) (= Hi ) в состояние i соотношениями H (0) == 0, H (1) = Ti(1) и(l−1)Hi = inf [n > HiРазностиTi(l)«Живите всегда в интересные времена возвращения».Из серии «Так говорил суперлектор».с нулевойвозвратностью (НВ), если mi = E i Ti = ∞, но fi = 1,P (n)pii < ∞, илиневозвратным (Н),если fi < 1, или(l)Рис.

1.23((l)(l−1)Hi − H i,=0,+ 1 : Xn = i] , l > 1.(l−1)если Hi< ∞,(l−1)= ∞,если Hi(1.8.2)(1.8.3)Анализ положительной и нулевой возвратности, проведенный выше,в сочетании со строго марковским свойством приводит к следующемурезультату.Теорема 1.8.3. Предположим, что цепь (Xn) возвратна, и пустьi — произвольное состояние. При заданном распределении P i случайные величины Ti(1) , Ti(2) , . . . н.о.р., принимают значения из Z+и конечны с вероятностью 1. Это означает, что при всех k > 1и t1 , . .

. tk ∈ Z+ выполняется равенствоXY(1)(k)P i (Ti = tl) иP i (Ti = t) = 1. (1.8.4)P i (Ti = t1 , . . . , Ti = tk) =16l6kt=1,2,...Далее, средние значения удовлетворяют условию1/ i , если цепь (Xn) положительно возвратна,mi := E i Ti = ∞,если цепь (Xn) имеет нулевую возвратностьили невозвратна.(1.8.5)(1.8.6)Мы не будем обсуждать доказательство теоремы 1.8.4; заинтересованный читатель может прочитать его в книгах [D] , [GS1] , [St1] .Пример 1.8.5. Случайные блуждания на Zd .a) Симметричное случайное блуждание «по ближайшим соседям».Мы уже знаем, что симметричное случайное блуждание «по ближайшимсоседям» на Zd (называемое также простым случайным блужданием)возвратно при d = 1 и d = 2 и невозвратно при d = 3.

Рассмотрим сначаласлучай d = 1. Уравнения инвариантности в этом случае принимают видi=11+ i+1 ,2 i− 12i ∈ Z,с точи, очевидно, имеют неотрицательное решение i ≡ 1 (единственноеPностью до положительного множителя). Поскольку сумма1 расходится,i∈Zто блуждание имеет нулевую возвратность.> 0 имеет компонентыСледовательно, любая инвариантная мера=const>0.Тогда∀i=6kikiСм. также пример 1.8.7 ниже. Кроме того,mk = E k (время возвращения в k) = ∞, k ∈ Z.При d = 2 уравнения инвариантности выглядят аналогично:1X( (i1 ±1,i2) + (i1 ,i2 ±1) ), i = (i1 , i2) ∈ Z2 ,(i1 ,i2) == E k (числа посещений состояния i, прежде чем цепь вернется в k) = 1.ki≡ 1.При d = 3 мера i ≡ 1 по-прежнему является инвариантной (чтов действительности верно вообще для всех d). Однако, поскольку блуждание невозвратно, векторы k являются субинвариантными, а не инваkриантными.

Следовательно, тождество i ≡ 1 уже не выполняется, хотяпо-прежнему mk ≡ ∞.б) Асимметричное случайное блуждание «по ближайшим соседям»на Z. Уравнения инвариантности в этом случае имеют вид= 1.2|k − i|l=12|k − i|i=pi−1+ (1 − p)i+1 ,i ∈ Z,где p 6= 1/2. Случайное блуждание невозвратно.

Общее неотрицательноерешение p ii =A+B1−pPзависит от двух параметров A, B > 0 и не удовлетворяет условиюi <i< ∞. Мы видим, что не все инвариантные мерыпропорциональны.В этом случае опять векторы k являются субинвариантными, а не инвариантными.

Кроме того, они ki уже не могут быть представлены в виде i / k ,где — некоторая инвариантная мера. Однако, как и прежде, m k ≡ ∞,посколькуPiP k (числа посещений состояния i, прежде чем цепь вернется в k, равно n) = 1 2 n−11=1−.и опять решением является i ≡ 1. Следовательно, блуждание имеетнулевую возвратность и, как и выше,стремится к математическому ожиданию mi (приведенному в соотношении (1.8.5)) при n → ∞.

Это означает, чтоn1 X (l)limTi = m in→∞ n(Это может показаться несколько удивительным, так как можно было быожидать, что должно выполняться неравенство 1 < kk+1 < kk+2 < . . .)Точнее,41 (1)(T + Ti(2) + . . . + Ti(n) )n i79Здесь = ( i) обозначает (единственное) стационарное распределение для положительно возвратной ц.м.д.в. (Xn).Приведенный пример независимых одинаково распределенных случай(1)(2)ных величин (н.о.р.с.в.) Ti , Ti , . . . довольно интригующий, так как их(совместное) распределение определяется переходной матрицей P и меняется довольно сложным способом при изменении P. Таким образом, чтобы(l)проанализировать последовательность (Ti ), нужно разработать общуютеорию н.о.р.с.в.

(в частности, это один из важных мотивов для разработкиэтой теории).В качестве примера одного из основных утверждений о н.о.р.с.в., который мы будем использовать в следующей главе, приведем «усиленный»(n)закон больших чисел (з.б.ч.) для последовательности (T i ).Теорема 1.8.4. С вероятностью 1 среднее§ 1.8. Положительная и нулевая возвратность. IIГлава 1. Цепи Маркова с дискретным временем781 − fk = P k (возвращение в k за конечное время не происходит) > 0.Глава 1.

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

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

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

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