Регулярная марковская цепь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 9 участников)
Строка 1: Строка 1:
== Регулярная цепь Маркова ==
 
 
{{Определение
 
{{Определение
|definition=Марковская цепь называется регулярной (нормальной), если в матрице перехода P  <tex>\forall i,j \ \ p_{ij} \neq 0</tex>.
+
|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> минимальный элемент этой матрицы. Пусть х — произвольный r-мерный вектор-столбец, имеющий максимальный элемент <tex>M_0</tex> и минимальный <tex>m_0</tex>. Пусть <tex>M_1</tex> и <tex>m_1</tex> - максимальный и минимальный элементы <tex>Px</tex>. <br>
+
|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>
 
Тогда <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=
 
|proof=
Пусть х' - вектор, полученный из х заменой всех элементов, кроме <tex>m_0</tex> на <tex>M_0</tex>. Тогда <tex>x \leqslant x'</tex>. Каждый элемент <tex>Px'</tex> имеет вид
+
Пусть <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>, где а - элемент P, который домножается на <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>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>-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>, ч.т.д.
+
Складывая эти два неравенства, получаем <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>
+
|statement=Регулярная марковская цепь [[Эргодическая марковская цепь|эргодична]]. Другими словами:<br>
 +
Пусть <tex>P</tex> {{---}} регулярная переходная матрица. Тогда:<br>
 
<tex>\exists A: \displaystyle \lim_{n \to \infty}P^n = A</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>
 
каждая строка А представляет собой один и тот же вероятностный вектор <tex>\alpha = \{a_1, a_2, \ldots, a_r \}</tex>
 
|proof=
 
|proof=
Рассмотрим вектор-столбец <tex>\rho _j</tex>, у которого j-й элемент равен 1, а все остальные равны 0. Пусть <tex>M_n</tex> и <tex>m_n</tex> - минимальный и максимальный элементы столбца <tex>P^n \rho _j</tex>.  
+
Рассмотрим вектор-столбец <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 \rho _j = P \cdot P^{n-1} \rho _j</tex>, то из леммы следует, что <tex>M_1 \geqslant M_2 \geqslant \ldots</tex> и <tex>m_1 \leqslant m_2 \leqslant \ldots</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>M_n - m_n \leqslant (1 - 2\varepsilon )(M_{n-1} - m_{n-1})</tex>. Пусть <tex>d_n = M_n - m_n</tex>, тогда
Строка 35: Строка 37:
 
<tex>d_n \leqslant (1 - 2 \varepsilon )^n d_0 = (1 - 2 \varepsilon)^n \to 0</tex>.
 
<tex>d_n \leqslant (1 - 2 \varepsilon )^n d_0 = (1 - 2 \varepsilon)^n \to 0</tex>.
  
Значит <tex>P^n \rho _j</tex> сходится к вектору, все элементы которого равны между собой. Пусть <tex>a_j</tex> - их общее значение. Тогда <tex>0 \leqslant a_j \leqslant 1</tex>. Заметим, что <tex>P^n \rho _j</tex> - j-тый столбец матрицы <tex>P^n</tex>. Рассмотрим все <tex>\rho _j</tex> для <tex>j = 1, 2, \ldots</tex>. Тогда <tex>P^n</tex> сходится к матрице А, у которой по строкам стоит один и тот же вектор <tex>\alpha = \{a_1, a_2, \ldots, a_r \}</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> сумма элементов в строке равна 1, то то же самое справедливо и для предельной матрицы А. Теорема доказана.
+
Так как в каждой матрице <tex>P^n</tex> сумма элементов в строке равна <tex>1</tex>, то то же самое справедливо и для предельной матрицы <tex>A</tex>. Теорема доказана.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition=Матрица А называется ''предельной матрицей'', вектор <tex>\alpha</tex> - ''предельным распределением''.
+
|definition=Матрица <tex>A</tex> называется '''предельной матрицей''' (англ. ''limiting matrix''), вектор <tex>\alpha</tex> {{---}} '''предельным распределением''' (англ. ''limiting distribution'').
 
}}
 
}}
  
 
+
== Следствия ==
== Следствие из теоремы ==
 
  
 
{{Теорема
 
{{Теорема
|statement=Пусть <tex>P, A, \alpha</tex> - объекты из предыдущей теоремы.
+
|statement=Пусть <tex>P, A, \alpha</tex> {{---}} объекты из предыдущей теоремы.
 
Тогда справедливы факты:<br>
 
Тогда справедливы факты:<br>
 
* для любого вероятностного вектора <tex>\pi \ \ \ \displaystyle \lim_{n \to \infty} \pi P^n = \alpha</tex>
 
* для любого вероятностного вектора <tex>\pi \ \ \ \displaystyle \lim_{n \to \infty} \pi P^n = \alpha</tex>
* <tex>\alpha</tex> - единственный вектор, для которого <tex>\alpha P = \alpha</tex>
+
* <tex>\alpha</tex> {{---}} единственный вектор, для которого <tex>\alpha P = \alpha</tex>
 
* <tex>AP = PA = A</tex>
 
* <tex>AP = PA = A</tex>
 
|proof=
 
|proof=
Пусть <tex>\xi</tex> - вектор-столбец, состоящий из единиц.
+
Пусть <tex>\xi</tex> {{---}} вектор-столбец, состоящий из единиц.
  
* <tex>\pi</tex> - вероятностный вектор, значит <tex>\pi \xi = 1</tex>(сумма его элементов равна 1), значит <tex>\pi A = \pi \xi \alpha = \alpha</tex>. Но <tex>\displaystyle \lim_{n \to \infty} \pi P^n = \pi A = \alpha</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} \pi P^n = \pi A = \alpha</tex> {{---}} первый пункт доказан.
 
* Пусть <tex>\beta : \ \ \beta P = \beta</tex>. Тогда <tex>\forall n \ \beta P^n = \beta \Rightarrow \beta = \beta A = \alpha</tex>. Второй пункт доказан.
 
* Пусть <tex>\beta : \ \ \beta P = \beta</tex>. Тогда <tex>\forall n \ \beta P^n = \beta \Rightarrow \beta = \beta A = \alpha</tex>. Второй пункт доказан.
 
* <tex>\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</tex>. Третий пункт доказан.
 
* <tex>\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</tex>. Третий пункт доказан.
 
}}
 
}}
  
Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии <tex>s_i</tex>, и эта вероятность не зависит от началоного распределения, а зависит только от матрицы P.
+
Таким образом у регулярных цепей есть свойство: через достаточно большое количество ходов будет существовать постоянная вероятность нахождения цепи в состоянии <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>, таким образом от честности монеты ничего не зависит.
 +
 
 +
== См. также ==
 +
*[[Марковская цепь]]
 +
*[[Эргодическая марковская цепь]]
  
== Литература ==
+
== Источники информации ==
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова", стр 93
+
*''Дж. Кемени, Дж. Снелл''  Конечные цепи Маркова, стр 93
 +
[[Категория:Дискретная математика и алгоритмы]]
  
[[Категория: Динамическое программирование]][[Категория: Марковские цепи]]
+
[[Категория: Марковские цепи ]]

Текущая версия на 19:17, 4 сентября 2022

Определение:
Марковская цепь называется регулярной (англ. 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