Регулярная марковская цепь — различия между версиями
Vsklamm (обсуждение | вклад) м |
м (rollbackEdits.php mass rollback) |
(не показана 1 промежуточная версия 1 участника) | |
(нет различий)
|
Текущая версия на 19:17, 4 сентября 2022
Определение: |
Марковская цепь называется регулярной (англ. regular Markov chain), если она целиком состоит из одного циклического класса. |
Теорема: |
Цепь регулярна тогда и только тогда, когда существует такое , что в матрице все элементы ненулевые, то есть из любого состояния можно перейти в любое за переходов. |
Лемма
Лемма: |
Пусть — матрица перехода регулярной цепи, — минимальный элемент этой матрицы. Пусть — произвольный -мерный вектор-столбец, имеющий максимальный элемент и минимальный . Пусть и — максимальный и минимальный элементы . Тогда , и |
Доказательство: |
Пусть — вектор, полученный из заменой всех элементов, кроме на . Тогда . Каждый элемент имеет вид, где — элемент , который домножается на , причем . Поэтому наше выражение не превосходит . Отсюда и из неравенства получается: . Применяя те же рассуждения для вектора Складывая эти два неравенства, получаем , получим: . . |
Эргодическая теорема для регулярных цепей
Теорема: |
Регулярная марковская цепь эргодична. Другими словами: Пусть |
Доказательство: |
Рассмотрим вектор-столбец , у которого -й элемент равен , а все остальные равны . Пусть и — минимальный и максимальный элементы столбца . Так как , то из леммы следует, что и и. Пусть , тогда . Значит Так как в каждой матрице сходится к вектору, все элементы которого равны между собой. Пусть — их общее значение. Тогда . Заметим, что — -тый столбец матрицы . Рассмотрим все для . Тогда сходится к матрице , у которой по строкам стоит один и тот же вектор . сумма элементов в строке равна , то то же самое справедливо и для предельной матрицы . Теорема доказана. |
Определение: |
Матрица | называется предельной матрицей (англ. limiting matrix), вектор — предельным распределением (англ. limiting distribution).
Следствия
Теорема: |
Пусть — объекты из предыдущей теоремы.
Тогда справедливы факты:
|
Доказательство: |
Пусть — вектор-столбец, состоящий из единиц.
|
Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии
, и эта вероятность не зависит от начального распределения, а зависит только от матрицы .Примеры
Самый очевидный и тривиальный пример регулярной цепи:
Пусть у нас есть два состояния —
и . Каждый ход мы кидаем честную монету — если выпал , то цепь остается в предыдущем состоянии, если — цепь меняет свое состояние.Матрица переходов будет выглядеть так:
Тогда
то есть через достаточно большое количество ходов наша система будет равновероятно находится как в состоянии , так и в состоянии , независимо от начального распределения.Более интересный пример — если мы будем управлять переходом состояний с помощью нечестной монеты. Пусть
— вероятность выпадения на монете.Матрица переходов будет выглядеть так:
Тогда при возведении
в степень элементы будут стремится к с разных сторон. То есть вектор , таким образом от честности монеты ничего не зависит.См. также
Источники информации
- Дж. Кемени, Дж. Снелл Конечные цепи Маркова, стр 93