Регулярная марковская цепь

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение:

Марковская цепь называется регулярной (англ. regular Markov chain), если она целиком состоит из одного циклического класса.

Теорема:

Цепь регулярна тогда и только тогда, когда существует такое [math] n [/math], что в матрице [math] P^n [/math] все элементы ненулевые, то есть из любого состояния можно перейти в любое за [math] n [/math] переходов.

Лемма

Лемма:

Пусть [math]P_{[r\times r]}[/math] — матрица перехода регулярной цепи, [math]\varepsilon[/math] — минимальный элемент этой матрицы. Пусть [math]x[/math] — произвольный [math]r[/math]-мерный вектор-столбец, имеющий максимальный элемент [math]M_0[/math] и минимальный [math]m_0[/math]. Пусть [math]M_1[/math] и [math]m_1[/math] — максимальный и минимальный элементы [math]Px[/math]. Тогда [math]M_1 \leqslant M_0[/math], [math]m_1 \geqslant m_0[/math] и [math]M_1 - m_1 \leqslant (1 - 2\varepsilon)(M_0 - m_0)[/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math]x'[/math] — вектор, полученный из [math]x[/math] заменой всех элементов, кроме [math]m_0[/math] на [math]M_0[/math]. Тогда [math]x \leqslant x'[/math]. Каждый элемент [math]Px'[/math] имеет вид [math]am_0 + (1 - a)M_0 = M_0 - a(M_0 - m_0)[/math], где [math]a[/math] — элемент [math]P[/math], который домножается на [math]m_0[/math], причем [math]a \geqslant \varepsilon[/math]. Поэтому наше выражение не превосходит [math]M_0 - \varepsilon(M_0 - m_0)[/math]. Отсюда и из неравенства [math]x \leqslant x'[/math] получается: [math]M_1 \leqslant M_0 - \varepsilon (M_0 - m_0)[/math]. Применяя те же рассуждения для вектора [math]-x[/math], получим: [math]-m_1 \leqslant -m_0 - \varepsilon (-m_0 + M_0)[/math]. Складывая эти два неравенства, получаем [math]M_1 - m_1 \leqslant M_0 - m_0 - 2\varepsilon (M_0 - m_0) = (1 - 2\varepsilon )(M_0 - m_0)[/math].

[math]\triangleleft[/math]

Эргодическая теорема для регулярных цепей

Теорема:

Регулярная марковская цепь эргодична. Другими словами: Пусть [math]P[/math] — регулярная переходная матрица. Тогда: [math]\exists A: \displaystyle \lim_{n \to \infty}P^n = A[/math]; каждая строка А представляет собой один и тот же вероятностный вектор [math]\alpha = \{a_1, a_2, \ldots, a_r \}[/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим вектор-столбец [math]e_j[/math], у которого [math]j[/math]-й элемент равен [math]1[/math], а все остальные равны [math]0[/math]. Пусть [math]M_n[/math] и [math]m_n[/math] — минимальный и максимальный элементы столбца [math]P^n e_j[/math]. Так как [math]P^n e_j = P \cdot P^{n-1} e_j[/math], то из леммы следует, что [math]M_1 \geqslant M_2 \geqslant \ldots[/math] и [math]m_1 \leqslant m_2 \leqslant \ldots[/math] и [math]M_n - m_n \leqslant (1 - 2\varepsilon )(M_{n-1} - m_{n-1})[/math]. Пусть [math]d_n = M_n - m_n[/math], тогда [math]d_n \leqslant (1 - 2 \varepsilon )^n d_0 = (1 - 2 \varepsilon)^n \to 0[/math]. Значит [math]P^n e_j[/math] сходится к вектору, все элементы которого равны между собой. Пусть [math]a_j[/math] — их общее значение. Тогда [math]0 \leqslant a_j \leqslant 1[/math]. Заметим, что [math]P^n e_j[/math] — [math]j[/math]-тый столбец матрицы [math]P^n[/math]. Рассмотрим все [math]e_j[/math] для [math]j = 1, 2, \ldots[/math]. Тогда [math]P^n[/math] сходится к матрице [math]A[/math], у которой по строкам стоит один и тот же вектор [math]\alpha = \{a_1, a_2, \ldots, a_r \}[/math]. Так как в каждой матрице [math]P^n[/math] сумма элементов в строке равна [math]1[/math], то то же самое справедливо и для предельной матрицы [math]A[/math]. Теорема доказана.

[math]\triangleleft[/math]

Определение:

Матрица [math]A[/math] называется предельной матрицей (англ. limiting matrix), вектор [math]\alpha[/math] — предельным распределением (англ. limiting distribution).

Следствия

Теорема:

Пусть [math]P, A, \alpha[/math] — объекты из предыдущей теоремы. Тогда справедливы факты: для любого вероятностного вектора [math]\pi \ \ \ \displaystyle \lim_{n \to \infty} \pi P^n = \alpha[/math] [math]\alpha[/math] — единственный вектор, для которого [math]\alpha P = \alpha[/math] [math]AP = PA = A[/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math]\xi[/math] — вектор-столбец, состоящий из единиц. [math]\pi[/math] — вероятностный вектор, значит [math]\pi \xi = 1 [/math] ( сумма его элементов равна [math]1[/math] ), значит [math]\pi A = \pi \xi \alpha = \alpha[/math]. Но [math]\displaystyle \lim_{n \to \infty} \pi P^n = \pi A = \alpha[/math] — первый пункт доказан. Пусть [math]\beta : \ \ \beta P = \beta[/math]. Тогда [math]\forall n \ \beta P^n = \beta \Rightarrow \beta = \beta A = \alpha[/math]. Второй пункт доказан. [math]\displaystyle \lim_{n \to \infty} P^n = A \Leftrightarrow P \cdot \lim_{n \to \infty} P^n = A \Leftrightarrow \lim_{n \to \infty} P^n \cdot P = A[/math]. Третий пункт доказан.

[math]\triangleleft[/math]

Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии [math]s_i[/math], и эта вероятность не зависит от начального распределения, а зависит только от матрицы [math]P[/math].

Примеры

Пример регулярной цепи (черным цветом обозначена вероятность, красным - выпавшая сторона монеты)

Самый очевидный и тривиальный пример регулярной цепи:

Пусть у нас есть два состояния — [math]1[/math] и [math]2[/math]. Каждый ход мы кидаем честную монету — если выпал [math]0[/math], то цепь остается в предыдущем состоянии, если [math]1[/math] — цепь меняет свое состояние.

Матрица переходов будет выглядеть так:

[math] P = \begin{bmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{bmatrix} [/math]

Тогда [math]\forall n \ \ P^n = P = A,\ \alpha = \{ 0.5, 0.5 \} ,\,[/math] то есть через достаточно большое количество ходов наша система будет равновероятно находится как в состоянии [math]1[/math], так и в состоянии [math]2[/math], независимо от начального распределения.

Более интересный пример — если мы будем управлять переходом состояний с помощью нечестной монеты. Пусть [math]a[/math] — вероятность выпадения [math]0[/math] на монете.

Матрица переходов будет выглядеть так:

[math] P = \begin{bmatrix} a & 1 - a \\ 1 - a & a \end{bmatrix} [/math]

Тогда при возведении [math]P[/math] в степень [math]n[/math] элементы будут стремится к [math]\dfrac{1}{2}[/math] с разных сторон. То есть вектор [math]\alpha = \{ 0.5, 0.5 \}[/math], таким образом от честности монеты ничего не зависит.

См. также

• Марковская цепь
• Эргодическая марковская цепь

Источники информации

• Дж. Кемени, Дж. Снелл Конечные цепи Маркова, стр 93