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

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

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

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

Рассмотрим уравнения инвариантности11,,0 =1 = 0+2 12 211+ i+1 , i > 2.i =2 i− 12§ 1.9. Сходимость к положению равновесия.Предельные пропорцииВремя есть образ вечности.Лаэрт Диоген (II в. н. э.), греческий писательУравнение во второй строке имеет общее решение вида i = A + Bi, i > 1.Из первой строки находим B = 0 и 0 = A/2.

Следовательно, любаяинвариантная мера имеет вид1= A, i > 1,0 = A,2Pгде A > 0. Для этой мерыi = ∞, за исключением случая, когда A = 0.iСходимость к положению равновесия означает, что с течением времениц.м.д.в. «забывает» свое начальное распределение . В частности, если == (i) , мера Дирака, сосредоточенная в состоянии i, ц.м.д.в. «забывает»о начальном состоянии i. Очевидно, такое поведение цепи связано сосвойствами n-кратной матрицы перехода P n при n → ∞.

Рассмотримсначала случай конечной цепи.Теорема 1.9.1. Предположим, что (m × m)-матрица перехода Pnпоэлементно сходится к предельной матрице Π = ( ij)i(n)lim pij =n→∞(i)Тогда а) каждая строкапределениеij(i)Далее, в силу строго марковского свойстваP 0 (N = n) = P 0 (N > 1) ×× P 1 (достичь 0 без возвращений в 1) =P=матрицы Π задает инвариантное рас(i)илиij=Xil plj .l(1)б) Если матрица P неприводима, то все ее строки= .

. . = (m) = . В этом случаеlim P (Xn = j) =1.2n(1.9.1)∀ i, j ∈ I.Таким образом, стационарное распределение не существует и цепь (W n)имеет нулевую возвратность.Следовательно, для ц.м.д.в. (Wn) выполняется равенствоi, k > 1 или i = k = 0,1,ik=== 0, k > 1,12,i/ik2,i > 1, k = 0.× (P 1 (возвращение в 1 без прохождения цепи через 0)) n−1 ×12n→∞(i)jдля любого j ∈ I и любого начального распределения .совпадают:88Глава 1. Цепи Маркова с дискретным временем§ 1.9. Сходимость к положению равновесия.

Предельные пропорции89Д о к а з а т е л ь с т в о. а) Для любого состояния j можно записать((i)XP) j ==l∈IXil plj=(n)lim pil plj = limn→∞ln→∞Xl(n)(n+1)pil plj = lim pijn→∞=ij=((i)) j.(1.9.2)б) Если матрица P неприводима, то все строки (i) матрицы Π совпадают между собой, так как существует единственное инвариантное распределение.

А также,XX(n)(n)lim P (Xn = j) = lim(1.9.3)i pij =i lim pij = j .n→∞n→∞iin→∞Для счетной цепи в уравнении (1.9.2) следует обосновать возможностьменять порядок перехода к пределу и суммирования. Однако формула(1.9.3) остается верной и в общем случае, при условии, что нам известно,что матрица Pn сходится к матрице Π, у которой строки равны между собойи представляют собой инвариантное распределение .место?Итак, когда же эта сходимость P n → Π имеет Простой контр0 1пример, когда такая сходимость невозможна: P = 1 0 . Здесь 1 0 , n четно,0 1P n = 0 1 , n нечетно.1 0(1.9.4)Рис. 1.27Более того, если матрица P неприводима, то(n)pij > 0 для всех достаточно больших n ∀ i, j ∈ I.(1.9.6)Теорема 1.9.2.

Предположим, что матрица P неприводима, апериодична и положительно возвратна. ТогдаPn → Π при n → ∞.Элементы в столбцах матрицы Π постоянны. Иными словами,столбцы матрицы Π состоят из повторений одного и того жевектора , где — (единственное) стационарное распределениедля P. Следовательно, неприводимая, апериодическая и положительно возвратная цепь Маркова забывает свое начальное распределение:lim P (Xn = j) = j ∀ и j ∈ I.(i)Д о к а з а т е л ь с т в о. Рассмотрим две цепи Маркова: (X n ), заданную( )парой ( (i) , P), и цепь (Xn ), заданную парой ( , P).

Тогда0 1 0 ... 0(n)pij = P i (Xn(i) = j),0 0 1 . . . 0 P=,. . . . . . . . . . . .1 0 0 ... 0которая соответствует рис. 1.25.Тогда P2 отвечает рис. 1.26 и так далее, m-я степень Pm = I соответствует рис. 1.27.Рисунок затем повторяется по модулю m. Опять стационарное распределение единственно: = (1/m . . . , 1/m).Мы знаем, что в этих примерах матрица P периодическая. Напомним,что матрица P — апериодическая тогда и только тогда, когда(n)Рис.

1.26n→∞В общем случае рассмотрим (m × m)-матрицуpii > 0 для всех достаточно больших n ∀ i ∈ I.Рис. 1.25(1.9.5)j= P (Xn( ) = j).Чтобы оценить разность между этими вероятностями, мы определим их«общую часть», склеив эти две цепи Маркова, т. е. рассматривая их совместно. Одна из возможностей — рассмотреть их как одну цепь Маркова,состоящую из двух независимых компонент. Это означает, что мы рассматриваем цепь Маркова (Yn) на I × I, состояниями являются (k, l) гдеk, l ∈ I, переходные вероятности имеют видpY(k,l) (u,v) = pku plv , k, l, u, v ∈ I,а начальное распределениеP (Y0 = (k, l)) = 1(k = i) l ,k, l ∈ I.(1.9.7)Глава 1.

Цепи Маркова с дискретным временемОднако, лучший способ — рассмотреть цепь (Wn), вероятности переходакоторой равны(pku plv ,если k 6= l,(1.9.8)k, l, u, v ∈ I,pW(k,l) (u,v) =pku 1(u = v), если k = l,а начальное распределение такое же, как и вышеP (W0 = (k, l)) = 1(k = i) l ,k, l ∈ I.(1.9.9)В самом деле, уравнение (1.9.8) определяет матрицу вероятностей перехода на I × I: все ее элементы pW(k,l) (u,v) > 0 и суммы элементов по строкамравны 1. Проверим это:PP pku plv , если k 6= lXuv= 1.pWP(k,l) (u,v) = pku ,если k = lu,v∈I§ 1.9. Сходимость к положению равновесия.

Предельные пропорции(i)и|pij(n) −u∈IОбразно говоря, две компоненты цепи (Wn) по отдельности ведут себякак (Xn(i) ) и (Xn); рассматриваемые совместно, они эволюционируют какнезависимые компоненты (т. е. как в (Yn)) до того (случайного) моментавремени T, когда они совпадаютT = inf [n > 1 : Xn(i) = Xn ] ,6 P W (T > n) = P Y (T > n).(1.9.12)P Y (T (l,l) < ∞) = 1,гдеT (l,l) = inf [n > 0 : Xn(i) = Xn = l] .Так как T 6 T (l,l) , отсюда следует требуемое утверждение.В случае конечной неприводимой апериодической цепи можно доказать,(n)что скорость сходимости pij к j — геометрическая: см.

теорему 1.9.3.В действительности, если конечная ц.м.д.в. неприводима и апериодична,то существуют такие m > 1 и ∈ (0, 1), чтоv∈Ij|Эта оценка называется неравенством спаривания (склейки).Таким образом, достаточно проверить, что P Y (T > n) → 0, т. е. P (T << ∞) = 1. Но (Yn) является неприводимой положительно возвратнойцепью Маркова.

(Неприводимость следует из того факта, что исходнаяматрица P является неприводимой и апериодичной (см. уравнение (1.9.6)),а положительная возвратность следует из того факта, что (Y n) имеет инвариантное распределение ( × ) (k,l) = k l .) Следовательно, в силу теоремы1.5.9 ∀ состояний l ∈ I,uДалее, частичное («маргинальное») суммирование приводит к исходнымвероятностям перехода PXXpWpW(k,l) (u,v) = pku ,(k,l) (u,v) = plv .91так как события {Xn = j, T 6 n} и {Xn = j, T 6 n} совпадают. Следовательно,(n)pij − j = P (Xn(i) = j, T > n) − P (Xn = j, T > n)(m)pij >90для любых состояний i, j.(1.9.13)Теорема 1.9.3. Если P — конечная, неприводимая и апериодическая матрица, то для любых состояний i, j выполняется неравенство (n)(1.9.14)pij − j 6 (1 − ) n/m − 1 ,после которого они движутся синхронно.

Следовательно,= P W (Xn(i) = j) − P W (Xn = j).(1.9.10)P W (Xn = j) = P W (Xn = j, T 6 n) + P W (Xn = j, T > n),(1.9.11)иP W (Xn(i) = j, T 6 n) = P W (Xn = j, T 6 n),u∈IP W (Xn(i) = j) = P (Xn(i) = j, T 6 n) + P (Xn(i) = j, T > n)замечаем, что первое слагаемое в каждой сумме одно и то же:где m и такие, как в неравенстве (1.9.13).Д о к а з а т е л ь с т в о. Повторяем ту же схему доказательства, что и втеореме 1.4.2 мы должны оценить P Y (T > n).

Но для конечного случаяможно записатьX (m) (m)X (m)pku plu >plu = ,PW(k,l) (T 6 m) >Записавu∈Iт. е.PW(k,l) (T > m) 6 (1 − ) ∀ k, l ∈ I.j(n)pij −92Глава 1. Цепи Маркова с дискретным временемТогда в силу строго марковского свойстваhni P W (T > n) 6 P W T >m 6 P W (T > m) [n/m] ,mоткуда и следует утверждение теоремы.Поучительным является следующий пример.Пример 1.9.4. Рассмотрим колоду карт, пронумерованных 1, 2, . . . , 52.Процесс тасования карт происходит следующим образом: мы снимаемверхнюю карту и помещаем ее случайным образом равномерно на одну из52 возможных позиций, т.

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

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

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

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