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

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

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

Теорема:

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

Лемма

Лемма:

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

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

$\triangleright$

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

$\triangleleft$

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

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

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

Матрица А называется предельной матрицей, вектор $\alpha$ — предельным распределением.

Следствия

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

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

Примеры

Пример регулярной цепи

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

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

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

$P = \begin{bmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{bmatrix}$

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

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

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

$P = \begin{bmatrix} a & 1 - a \\ 1 - a & a \end{bmatrix}$

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

Литература

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