200
правок
Изменения
м
== Регулярная цепь Маркова ==
== Литература ==Дж. Кемени, Дж. Снелл "Конечные [[Категория: Марковские цепи Маркова"]]
Нет описания правки
{{Определение
|definition=Регулярной марковской [[Марковская цепь |Марковская цепь]] называется '''регулярной''' (англ. ''regular Markov chain''), если она целиком состоит из одного [[Эргодическая марковская цепь без невозвратных состояний и имеющая единственное эргодическое множество с одним циклическим классом#Циклический класс | циклического класса]].
}}
{{Теорема
|statement=
Цепь регулярна тогда и только тогда, когда существует такое <tex> n </tex>, что в матрице <tex> P^n </tex> все элементы ненулевые, то есть из любого состояния можно перейти в любое за <tex> n </tex> переходов.
}}
== Лемма ==
{{Лемма
|statement=Пусть <tex>P_{[r\times r]}</tex> {{---}} матрица перехода регулярной цепи, <tex>\varepsilon</tex> {{---}} минимальный элемент этой матрицы. Пусть <tex>x</tex> {{---}} произвольный <tex>r</tex>-мерный вектор-столбец, имеющий максимальный элемент <tex>M_0</tex> и минимальный <tex>m_0</tex>. Пусть <tex>M_1</tex> и <tex>m_1</tex> {{---}} максимальный и минимальный элементы <tex>Px</tex>. <br>
Тогда <tex>M_1 \leqslant M_0</tex>, <tex>m_1 \geqslant m_0</tex> и <tex>M_1 - m_1 \leqslant (1 - 2\varepsilon)(M_0 - m_0)</tex>
|proof=
Пусть <tex>x'</tex> {{---}} вектор, полученный из <tex>x</tex> заменой всех элементов, кроме <tex>m_0</tex> на <tex>M_0</tex>. Тогда <tex>x \leqslant x'</tex>. Каждый элемент <tex>Px'</tex> имеет вид
<tex>am_0 + (1 - a)M_0 = M_0 - a(M_0 - m_0)</tex>, где <tex>a</tex> {{---}} элемент <tex>P</tex>, который домножается на <tex>m_0</tex>, причем <tex>a \geqslant \varepsilon</tex>. Поэтому наше выражение не превосходит <tex>M_0 - \varepsilon(M_0 - m_0)</tex>. Отсюда и из неравенства <tex>x \leqslant x'</tex> получается: <tex>M_1 \leqslant M_0 - \varepsilon (M_0 - m_0)</tex>.
Применяя те же рассуждения для вектора <tex>-x</tex>, получим: <tex>-m_1 \leqslant -m_0 - \varepsilon (-m_0 + M_0)</tex>.
Складывая эти два неравенства, получаем <tex>M_1 - m_1 \leqslant M_0 - m_0 - 2\varepsilon (M_0 - m_0) = (1 - 2\varepsilon )(M_0 - m_0)</tex>.
}}
== Эргодическая теорема для регулярных цепей ==
{{Теорема
|statement=Регулярная марковская цепь [[Эргодическая марковская цепь|эргодична]]. Другими словами:<br>
Пусть <tex>P</tex> {{---}} регулярная переходная матрица. Тогда:<br>
<tex>\exists A: \displaystyle \lim_{n \to \infty}P^n = A</tex>;<br>
каждая строка А представляет собой один и тот же вероятностный вектор <tex>\alpha = \{a_1, a_2, \ldots, a_r \}</tex>
|proof=
Рассмотрим вектор-столбец <tex>e_j</tex>, у которого <tex>j</tex>-й элемент равен <tex>1</tex>, а все остальные равны <tex>0</tex>. Пусть <tex>M_n</tex> и <tex>m_n</tex> {{---}} минимальный и максимальный элементы столбца <tex>P^n e_j</tex>.
Так как <tex>P^n e_j = P \cdot P^{n-1} e_j</tex>, то из леммы следует, что <tex>M_1 \geqslant M_2 \geqslant \ldots</tex> и <tex>m_1 \leqslant m_2 \leqslant \ldots</tex> и
<tex>M_n - m_n \leqslant (1 - 2\varepsilon )(M_{n-1} - m_{n-1})</tex>. Пусть <tex>d_n = M_n - m_n</tex>, тогда
<tex>d_n \leqslant (1 - 2 \varepsilon )^n d_0 = (1 - 2 \varepsilon)^n \to 0</tex>.
Значит <tex>P^n e_j</tex> сходится к вектору, все элементы которого равны между собой. Пусть <tex>a_j</tex> {{---}} их общее значение. Тогда <tex>0 \leqslant a_j \leqslant 1</tex>. Заметим, что <tex>P^n e_j</tex> {{---}} <tex>j</tex>-тый столбец матрицы <tex>P^n</tex>. Рассмотрим все <tex>e_j</tex> для <tex>j = 1, 2, \ldots</tex>. Тогда <tex>P^n</tex> сходится к матрице <tex>A</tex>, у которой по строкам стоит один и тот же вектор <tex>\alpha = \{a_1, a_2, \ldots, a_r \}</tex>.
Так как в каждой матрице <tex>P^n</tex> сумма элементов в строке равна <tex>1</tex>, то то же самое справедливо и для предельной матрицы <tex>A</tex>. Теорема доказана.
}}
{{Определение
|definition=Состояние Матрица <tex>iA</tex> называется возвратным'''предельной матрицей''' (англ. ''limiting matrix''), если вектор <tex>p_{ii} = 1\alpha</tex>{{---}} '''предельным распределением''' (англ. ''limiting distribution'').
}}
== Эргодическая теорема для регулярной марковской цепи Следствия == {{УтверждениеТеорема|statement=Для регулярной марковской цепи существует такой Пусть <tex>P, A, \alpha</tex> {{---}} объекты из предыдущей теоремы.Тогда справедливы факты:<br>* для любого вероятностного вектора <tex>\pi \ \ \ \displaystyle \lim_{n \to \infty} \pi P^n = \alpha</tex>* <tex>\alpha</tex> {{---}} единственный вектор , для которого <tex>\omega alpha P = \limalpha</tex>* <tex>AP = PA = A</tex>|proof=Пусть <tex>\limitsxi</tex> {{---}} вектор-столбец, состоящий из единиц. _* <tex>\pi</tex> {{---}} вероятностный вектор, значит <tex>\pi \xi = 1 </tex> ( сумма его элементов равна <tex>1</tex> ), значит <tex>\pi A = \pi \xi \alpha = \alpha</tex>. Но <tex>\displaystyle \lim_{n \to +\infty} cP\pi P^n, = \pi A = \alpha</tex> {{---}} первый пункт доказан.* Пусть <tex>\beta : \ \ \beta P = \beta</tex>. Тогда <tex>\forall cn \ \beta P^n = \beta \Rightarrow \beta = \beta A = \alpha</tex> такой, что . Второй пункт доказан.* <tex>\omega displaystyle \lim_{n \to \infty} P^n = A \Leftrightarrow P \cdot \lim_{n \to \infty} P^n = A \Leftrightarrow \lim_{n \to \omega infty} P^n \cdot P = A</tex>. Третий пункт доказан.
}}
Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии <tex>s_i</tex>, и эта вероятность не зависит от начального распределения, а зависит только от матрицы <tex>P</tex>.
== Примеры ==
[[File:Пример регулярной цепи.jpg|thumb|270px|Пример регулярной цепи (черным цветом обозначена вероятность, красным - выпавшая сторона монеты)]]
Самый очевидный и тривиальный пример регулярной цепи:
Пусть у нас есть два состояния {{---}} <tex>1</tex> и <tex>2</tex>. Каждый ход мы кидаем честную монету {{---}} если выпал <tex>0</tex>, то цепь остается в предыдущем состоянии, если <tex>1</tex> {{---}} цепь меняет свое состояние.
Матрица переходов будет выглядеть так:
<tex>
P = \begin{bmatrix}
0.5 & 0.5 \\
0.5 & 0.5
\end{bmatrix}
</tex>
Тогда <tex>\forall n \ \ P^n = P = A,\ \alpha = \{ 0.5, 0.5 \} ,\,</tex>
то есть через достаточно большое количество ходов наша система будет ''равновероятно'' находится как в состоянии <tex>1</tex>, так и в состоянии <tex>2</tex>, независимо от начального распределения.
Более интересный пример {{---}} если мы будем управлять переходом состояний с помощью нечестной монеты.
Пусть <tex>a</tex> {{---}} вероятность выпадения <tex>0</tex> на монете.
Матрица переходов будет выглядеть так:
<tex>
P = \begin{bmatrix}
a & 1 - a \\
1 - a & a
\end{bmatrix}
</tex>
Тогда при возведении <tex>P</tex> в степень <tex>n</tex> элементы будут стремится к <tex>\dfrac{1}{2}</tex> с разных сторон.
То есть вектор <tex>\alpha = \{ 0.5, 0.5 \}</tex>, таким образом от честности монеты ничего не зависит.
== См. также ==
*[http://ru[Марковская цепь]]*[[Эргодическая марковская цепь]] == Источники информации ==*''Дж.wikipediaКемени, Дж.org/wiki/%D0%92%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B5_%D1%81%D0%BE%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5 ВикипедияСнелл'' Конечные цепи Маркова, стр 93[[Категория: возвратное состояниеДискретная математика и алгоритмы]]
