Эта страница включает в себя множество исправленных упражнений на цепи Маркова в дискретном времени и асимптотическое поведение, класс, цепь эргодический, усвоение.
Упражнение 1
Построить цепь маркова соответствующей следующей стохастической матрице:
0.4 | 0.6 | 0 |
0.2 | 0.5 | 0.3 |
0 | 0.4 | 0.6 |
Сколько классов у строки? Является ли оно редуцируемым? Если да, то уменьшите. Вычислите стационарную вероятность неприводимой цепи, если она есть. Рассчитать периодичность занятий.
Чтобы представить цепочку, мы решили пронумеровать состояния от 1 до 3 в порядке строк матрицы перехода:
Чтобы проверить классы в цепочке, нам нужно проверить взаимодействующие состояния. Здесь 1 сообщается с 2, а 2 с 3 (поэтому доступно в обоих направлениях), по транзитивности 1 сообщается с 3. Цепь имеет только один класс, она неприводима. Таким образом, все состояния повторяются и являются апериодическими, поскольку все они имеют петлю сами по себе. В этих условиях цепочка допускает единственную стационарную вероятность. Достаточно решить следующую систему уравнений:
Что дает вектор (4/25, 12/25, 9/25).
Упражнение 2
То же, что и в упражнении 1 со следующей стохастической матрицей:
0 | 0.5 | 0.5 | 0 |
0 | 1 | 0 | 0 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
Заметим, что 2 ни с кем не общается, это поглощающее состояние. С 1 никто не общается, государство формирует переходный класс. Состояния 3 и 4 взаимодействуют друг с другом, они образуют рекуррентный класс. Итак, есть три класса {1}, {2}, {3,4}.
Не существует гарантированной стационарной вероятности. Решим следующую систему:
Система не допускает единственного решения. Пусть Pi2 находится между 0 и 1, тогда мы находим решение:
Замечаем в классе {3,4}, что вероятности равны на частоте 2k, делаем вывод, что класс периодичен на периоде 2. Класс {2} поглощающий, периода нет. Класс {1} является переходным, поэтому через время k популяции больше нет.
Упражнение 3
То же, что и в упражнении 1 со следующей стохастической матрицей:
0 | 1 | 0 |
0 | 0 | 1 |
1 | 0 | 0 |
Теперь обратимся к стационарной вероятности:
Что дает вектор (1/3, 1/3, 1/3). Что касается периодичности, мы замечаем, что матрица перехода становится единичной матрицей, когда она возведена в куб. Таким образом, мы можем сделать вывод, что цепь Маркова периодична с периодичностью 3. Следовательно, стационарной вероятности не существует, с другой стороны, мы можем сделать вывод, что на большом случайном шаге мы проводим 1/3 времени в каждом из состояний.
Упражнение 4
Восстановите из следующих трех графов переходов соответствующие цепи Маркова (пространство состояний и матрицу). Затем проанализируйте эти цепи Маркова: классы и характеристики, стационарный закон, вероятность поглощения, среднее время поглощения).
ПЕРВЫЙ ДИАГРАММА :
Все состояния обмениваются данными, поэтому существует только один неизбежно повторяющийся класс. Заметим, что матрица мощности 4 дает единичную матрицу, следовательно, периодичность равна 4.
Теперь вычислим стационарное распределение:
Поскольку есть периодичность, мы знаем, что сходимости нет. Кроме того, случайный шаг будет проводить ¼ своего времени в каждом состоянии. Что касается поглощения, у нас есть неприводимая цепочка, поэтому вероятность оказаться в уникальном классе равна 1.
ВТОРОЙ ГРАФИК:
Все состояния общаются, все состояния одного периода. Матрица кажется похожей на первый график, но обратите внимание, что состояние 1 имеет петлю, поэтому имеет период 1. Таким образом, уникальный класс является апериодическим (с периодом 1).
Поскольку цепь апериодична и неприводима, мы знаем, что она сходится к стационарному распределению.
Поскольку класс всего один, расчет вероятностей поглощения прост, из любого состояния мы всегда переходим в один и тот же класс.
ТРЕТИЙ ГРАФИК:
У нас есть четыре класса
{1}, который является временным, поэтому периодичность отсутствует.
[2}, который повторяется с циклом, поэтому периодичность равна 1.
{3} аналогично {1}
{4} аналогично {2}
Вычислите стационарное распределение. Учитывая, что есть переходные классы, мы знаем, что конвергенции не будет:
Заметим, что решений бесконечно много.
Рассчитайте вероятности поглощения. Начнем с состояния 2. Вычислим вектор v так, чтобы vя равна вероятности того, что цепь поглощается в точке 2, зная, что она начинается в точке i. Вычисления просты, поскольку у нас есть два переходных класса ожидания 1 (без циклов и с одним состоянием). Таким образом, мы знаем, что состояние 2 достигается с шагом максимум в 1, что значительно сокращает количество вычислений. Действительно, вероятность достижения 2, начиная с 1, известна, поскольку она равна p12. Таким образом, вероятности перехода представляют собой второй столбец таблицы P. Точно так же вероятности поглощения состояния 4 представляют собой четвертую колонку таблицы P. В общем случае вектор v должен быть рассчитан таким образом, чтобы (PI)v=0 .
Мы можем рассчитать среднее время поглощения. Состояния 2 и 4 повторяются, поэтому x2=х4=0. Быстро видно, что х1=х3=1+0=1.
Упражнение 5
Рассмотрим следующий пример:
Вычислите вероятность следующих траекторий (h, a, f, h), (h, a, f, a), (a, a, a).
Вычислить распределение состояний X1 в момент времени t = 1, если предположить, что X0 = (1, 0, 0).
Интерпретировать.
Покажите, что равномерное распределение X0 = (1/3, 1/3, 1/3) не является стационарным распределением для этой цепи Маркова.
Существует ли стационарное распределение для этой цепи Маркова?
P(h,a,f,h)= X0(h)*0,45*0,4*0=0
Р (ч, а, е, а) = 0,018 * X0 (ч)
Р(а,а,а)= 0,25*Х0(а)
Таким образом, после трех итераций половина участка покрыта травой, 0,45 кустами и 0,05 лесом, если предположить, что вначале была только трава.
Равномерное распределение не является стационарным. Для расчета стационарного распределения необходимо решить систему XP=X:
Это дает решение (2/53, 10/53, 41/53). Мы можем сделать вывод, что мы склоняемся к большей части леса с плотностью 41/53.
Упражнение 6
Рассмотрим цепь Маркова из четырех состояний согласно следующей матрице переходов:
Определите классы цепи, затем вероятность поглощения состояния 4, начиная с 2.
Определите время впитывания в 1 или 4, начиная со 2.
Мы замечаем, что состояние 1 и состояние 4 являются поглощающими состояниями, образующими два класса. Состояния 2 и 3 общаются, но могут перейти в поглощающий класс. Мы делаем вывод, что {2,3} образует переходный класс.
Согласно курсу вероятность поглощения поглощающего состояния k из состояния i решается следующей системой:
Это дает следующую систему:
Итак, вектор решения (0;1/3;2/3;1), h1=0, чтобы не влиять на другие уравнения. Выводим через h2 вероятность поглощения состояния 4, начиная с 2.
Согласно курсу, время поглощения поглощающим состоянием k из состояния i решается следующей системой:
Это дает следующую систему:
Итак, вектор решения равен (0;2;2;0). Время поглощения К2 дает правильный ответ.
Упражнение 7
Рассмотрим сеть дорог, состоящую из 5 городов A, B, C, D, S, следующим образом:
Для моделирования дорожного движения считаем, что автомобили выезжают из города по дороге справедливым (равномерным) образом. Отметим Хнет случайная величина, представляющая город, до которого доехала машина в момент времени n.
- Обоснуйте, что вероятностный процесс действительно является стохастическим и образует цепь Маркова. И дайте матрицу перехода.
- Какова вероятность того, что, начиная с B, автомобиль после двух итераций окажется в C.
- Разделите состояния на классы и рассчитайте их периоды.
- Напишите систему уравнений, проверяемую стационарными вероятностями.
- Обозначим количество маршрутов из i. Выведите распределение начальной популяции в зависимости от . Вычислите стационарное распределение. Она уникальна?
- Автомобиль наблюдается якобы очень большое время N. Примерно сколько времени он находится в данном состоянии?
- Какое среднее количество шагов необходимо сделать машине, начиная с S, чтобы вернуться в S?
- Какова вероятность того, что, начиная с S, машина поедет в город D раньше, чем в город С?
- Даже зная всю его прошлую траекторию, пункт назначения автомобиля определяется только его текущим положением. Более того, согласно определению упражнения, автомобиль имеет вероятность 1 покинуть свой текущий город, а значит, сделать шаг в сторону связанных городов. Выбор шага не зависит от прошлого, мы действительно имеем дело с цепью Маркова. Матрица перехода выглядит следующим образом:
- Есть только два пути, которые идут из B в C за два шага: BAC и BSC. Таким образом, вероятность перехода из B в C за два шага равна ½ * 1/3 + 1/2 * ¼ = 7/24.
- Как показывает график, все состояния связаны между собой, все они взаимодействуют между собой и, следовательно, образуют единый рекуррентный класс (поэтому положительный). Цепь неприводима. Что касается периодичности, обратите внимание, что существуют цепочки всех длин от А до А. Таким образом, цепь апериодична.
- Смотрите курс.
- Отметим, что вектор распределения, рассчитанный по количеству выездов из каждого города, соответствует вектору стационарных вероятностей (1/4, 1/6, 1/6, 1/12, 1/3). Эта вероятность уникальна, так как цепь эргодична.
- Поскольку цепь эргодична, мы знаем, что ее асимптотическое поведение эквивалентно стационарным вероятностям. Например, автомобиль проведет 1/12 своего времени в состоянии D.
- Опять же, цепь эргодична, мы знаем, что математическое ожидание обратно стационарной вероятности. Таким образом, среднее время возврата в S составляет 3 шага.
- Этот момент гораздо сложнее вывести. Идея состоит в том, чтобы гарантировать, что цепь Маркова поглощается в C или D. Таким образом, начиная с S, вероятность достижения D является вероятностью поглощения классом {D}. Во-первых, мы модифицируем состояния C и D следующим образом:
Затем у нас есть два рекуррентных (и поглощающих) класса и переходный класс, содержащий {A,B,S}. Осталось только рассчитать вероятности поглощения и сделать вывод (см. курс).
Упражнение 8
Рассмотрим цепь Маркова с тремя состояниями со следующей матрицей переходов:
Что такое рекуррентные, переходные состояния, стационарный режим? Рассчитайте время достижения каждого состояния. Вычислите период каждого состояния. Сделайте вывод о стационарном распределении.
Из состояния 1 мы можем перейти в состояния 2 и 3, из состояния 2 мы можем перейти в состояния 1 и 3, из состояния 3 мы можем перейти в состояние 1, и по транзитивности от 1 к 2 мы заключаем, что 3 может перейти в состояние 2. Все Таким образом, состояния сообщают, что цепь неприводима, все состояния являются положительно рекуррентными.
Таким образом, цепь допускает единственный стационарный закон ценности (4/9; 2/9; 3/9)
Время достижения состояния обратно величине стационарного закона.
При расчете Q² и Q3, мы замечаем, что значение нижнего индекса (1,1) положительное, поэтому точки нет. Бесполезно проверять всю диагональ, поскольку мы показали, что все состояния принадлежат одному и тому же классу.
Цепочка эргодическая, ее асимптотический характер стремится к стационарному распределению.
Упражнение 9
Для представления прохождения молекулы фосфора в экосистеме рассмотрим четыре возможных состояния:
- молекула находится в земле,
- молекула в траве,
- молекула была поглощена скотом,
- молекула выводится из экосистемы.
Матрица перехода выглядит следующим образом:
Представьте связанную цепь Маркова. Изучите цепь Маркова.
Pi=(0, 0, 0, 1) из-за поглощающего состояния. Можно рассчитать N и B следующим образом:
RU 
FR 
EN 
ES