Цепи Маркова

Граф поведения Пети, у которого есть честная монета, и который хочет пойти в кино с вероятностью

Если занумеровать каждое состояние (числом от до ), можно рассмотреть рассмотрение случайной величины:
- вероятность находиться в -м состоянии.

Рассмотрим матрицу такую, что - вероятность перейти из в :

Тогда умножая начальное состояние на матрицу перехода будем получать вероятностные распределения для каждого броска монеты:

Заметим что и
Обобщим:

Граф цепи Маркова

1. Поглощающие (существенные) состояния
2. Непоглощающие (несущественные) состояния

Цепь Меркова - поглащающая состояния есть путь до поглощающего состояния

Эргодический класс

Компоненты сильной связанности графа Марковой цепи (класс эквивалентности на отношении достижимости) Поглащающий эргодический класс нет "выхода"

Эргодическая Маркова цепь состоит из одного эргодического класса

Периодический эргодический класс с периодом длина цикла делится на

Теорема (классификация Марковых цепей)

Любая м.ц. содержит поглащающий эргодический класс

Для непериодического эргодического класса предельное распределение
И

Заданы следующие задачи

1. Понять по начальному распределению и вероятности перехода в каком эргодическом классе мы поглотимся
2. Какое стационарное распределение у непериодических эргодических классов Марковских цепей

Задача о поглощении

Занумеруем состояния в матрице перехода так, чтобы сначала шли непоглащающие, потом поглащающиеся:

Если и - непогл., - часть вектора отвечающая за переход в неполг. Тогда

Заметим

Вектор непоглащённого состояния на переходе в другое неполгащённое состояние зависит только от , т.к. остальное обнуляется.

Теорема (о поглощении)

Поглощающая Марковская цепь переходит в поглощающее состояние с вероятностью .

- максимальная длина кратчайшего пути от вершины до поглащающей.

Теперь рассмотрим
Тогда

Значит вероятность перейти в не поглащающую вершину стремится к нулю

Но где же мы поглотимся?

Посчитаем мат. ожидание времени до поглощения 🫠 - начальное распределение - случайная величина числа шагов до поглощения

- число посещений -ого состояния

Лемма

- фундаментальная матрица Марковской цепи - количество посещений непоглащающих состояний до поглощений - Суммарное количество шагов до поглощений - Распределение вероятности поглощения в состоянии