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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 66 промежуточных версий 10 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition=[[Марковская цепь|Марковская цепь]] называется эргодической, если существует дискретное распределение (называемое эргодическим) <tex>\pi = (\pi_1,\pi_2,\ldots )^{\top}</tex>, такое что <tex>\pi_i > 0,\; i \in \mathbb{N}</tex> и
+
|definition=
:<tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, \quad \forall i=1,2, \ldots</tex>.
+
'''Эргодическая''' [[Марковская цепь|марковская цепь]] (англ. ''ergodic Markov chain'') {{---}} марковская цепь, целиком состоящая из одного  [[Марковская цепь#sort_def| эргодического класса]].
 
}}
 
}}
  
Марковскую цепь обладающую следующими свойствами называют '''слабо эргодическиой''', если она обладает следующими свойствами:
+
==Стационарный режим==
# Для любых двух различных вершин графа переходов <tex>i,j \, (i\neq j)</tex> найдется такая вершина <tex>k</tex> графа («общий сток»), что существуют ориентированные пути от вершины <tex>i</tex> к вершине <tex>k</tex> и от вершины <tex>j</tex> к вершине <tex>k</tex>. ''Замечание'': возможен случай <tex>k=i</tex> или <tex>k=j</tex>; в этом случае тривиальный (пустой) путь от <tex>i</tex> к <tex>i</tex> или от <tex>j</tex> к <tex>j</tex> также считается ориентированным путем.
+
Эргодические марковские цепи описываются [[Отношение связности, компоненты связности|сильно связным графом]]. Это означает, что в такой системе возможен переход из любого состояния <tex>S_i</tex> в любое состояние <tex>S_{j}, (i,j = 1,2,\ldots,n)</tex> за конечное число шагов.
# Нулевое собственное число матрицы интенсивности невырождено.
 
# При <tex>t \to \infty</tex> матрица переходных вероятностей стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
 
  
 +
Для эргодических цепей при достаточно большом времени функционирования (<tex>t \to \infty</tex>) наступает '''стационарный режим''', при котором вероятности <tex>\alpha_i</tex> состояний системы не зависят от времени и не зависят от распределения вероятностей в начальный момент времени, то есть: <tex>\alpha_i = const</tex>.
  
[[Файл:MarkovTriangle.png|thumb|350px|Примеры графов переходов для цепей Маркова:
+
== Классификация эргодических цепей ==
a) цепь не является слабо эргодической (не существует общего стока <tex>^{[1]}</tex> для состояний <tex>A_2, \, A_3</tex>); 
 
b) слабо эргодическая, но не эргодическая цепь (граф переходов является слабо-связным <tex>^{[2]}</tex>)
 
c) эргодическая цепь (сильно-связный <tex>^{[3]}</tex> граф переходов).]]
 
  
==Основная теорема об эргодических распределениях==
+
{{Определение
 +
|definition=
 +
В эргодической цепи можно выделить '''циклические классы''' (англ. ''cyclic classes''). Количество циклических классов <tex> d </tex> называют '''периодом цепи''' (англ. ''period of Markov chain''), если цепь состоит целиком из одного циклического класса, её называют [[Регулярная марковская цепь|регулярной]]. С течением времени текущее состояние движется по циклическим классам в определенном порядке, причем каждые <tex>d</tex> шагов она оказывается в одном и том же циклическом классе.
 +
}}
 +
 
 +
Таким образом, эргодические цепи делятся на [[Регулярная марковская цепь|регулярные]] и '''циклические'''.
 +
 
 +
== Эргодическая теорема ==
 +
{{Определение
 +
|definition=
 +
'''Эргодическое (стационарное) распределение''' (англ. ''stationary distribution'') {{---}} распределение <tex>\alpha = (\alpha_1 \ldots \alpha_n )</tex>, такое что <tex>\alpha_i > 0</tex> и
 +
<tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \alpha_j</tex> (где <tex>p_{ij}^{(n)}</tex> {{---}} вероятность оказаться в <tex>j</tex>-ом состоянии, выйдя из <tex>i</tex>-ого, через <tex>n</tex> переходов).
 +
}}
 +
 
 +
=== Для регулярных цепей ===
 +
Доказательство теоремы для случая регулярных цепей приведено в конспекте про [[Регулярная марковская цепь#Эргодическая теорема для регулярных цепей | регулярные цепи]].
 +
 
 +
=== Для циклических цепей ===
 
{{
 
{{
 
Теорема
 
Теорема
|about=Основная теорема об эргодических распределениях
+
|about=Эргодическая теорема
 
|statement=
 
|statement=
Пусть <tex>\{X_n\}_{n \ge 0}</tex> - цепь Маркова с дискретным пространством состояний и матрицей переходных вероятностей <tex>P = (p_{ij}),\; i,j=1,2,\ldots</tex>. Тогда эта цепь является эргодической тогда и только тогда, когда она
+
Для любой эргодической цепи последовательность степеней <tex>P^{n}</tex> [http://en.wikipedia.org/wiki/Euler_summation суммируется по Эйлеру] к предельной матрице <tex>A</tex>, и эта предельная матрица имеет вид <tex>A = \xi\alpha</tex>, где <tex>\alpha</tex> {{---}} положительный вероятностный вектор, <tex>\xi</tex> - вектор-столбец из единиц.
# Неразложима <tex>^{[4]}</tex>;
+
|proof=
# Положительно возвратна <tex>^{[5]}</tex>;
+
 
# Апериодична <tex>^{[6]}</tex>.
+
 
Эргодическое распределение <tex>\mathbf{\pi}</tex> тогда является единственным решением системы:
+
В случае циклической цепи переходы из одного циклического класса в другой возможны только при определенных значениях <tex> n </tex>, которые периодически повторяются. Таким образом, никакая степень матрицы переходов <tex>P</tex> не является положительной матрицей, и различные степени содержат нули на различных местах. С увеличением степени расположение этих нулей периодически повторяется. Следовательно, последовательность <tex>P^{n}</tex> не может сходиться в обычном смысле, для нее требуется так называемая суммируемость по Эйлеру.
:<tex>\sum\limits_{i=0}^{\infty} \pi_i = 1,\; \pi_j \ge 0,\; \pi_j = \sum\limits_{i=0}^{\infty} \pi_i\, p_{ij},\quad \, j\in \mathbb{N}</tex>.}}
+
 
 +
Рассмотрим матрицу <tex>(kI + (1 - k)P)</tex> при некотором <tex>k, ~ 0 < k < 1</tex>. Эта матрица является ''переходной матрицей''. Она имеет положительные элементы на всех тех же местах, что и <tex>P</tex>, следовательно, она также ''задает эргодическую цепь''. Также диагональные элементы этой матрицы положительны. Значит, в каждое состояние можно возвратиться за один шаг, а это значит, что <tex>d = 1</tex>. Таким образом, новая цепь является регулярной.
 +
 
 +
Из [[Регулярная марковская цепь#Эргодическая теорема для регулярных цепей | эргодической теоремы для регулярных цепей]] следует, что <tex>(kI + (1 - k)P)^{n}</tex> стремится к матрице <tex>A = \xi\alpha</tex>, где <tex>\alpha</tex> {{---}} положительный вероятностный вектор. Таким образом:
 +
: <tex> A = \lim\limits_{x\to \infty} (kI + (1 - k)P)^{n}</tex>
 +
: <tex> A = \lim\limits_{x\to \infty} \sum\limits_{i = 0}^{n} {n\choose i} k^{n - i} (1 - k)^{i} P^{i} ~~~~~ (1)</tex>
 +
Но последнее равенство в точности означает, что последовательность <tex>P^{n}</tex> суммируема по Эйлеру к <tex>A</tex>, причем суммируема при каждом значении <tex>k</tex>.
 +
}}
 +
 
 +
==== Следствия ====
 +
 
 +
{{Теорема
 +
|statement=Если <tex>P, A, \alpha</tex> {{---}} объекты из предыдущей теоремы. Тогда справедливы факты:
 +
 
 +
* Для любого вероятностного вектора <tex>\pi</tex> последовательность <tex>\pi P^{n}</tex> суммируема по Эйлеру к <tex>\alpha</tex>
 +
* Вектор <tex>\alpha</tex> является единственным неподвижным вектором матрицы <tex>P</tex>
 +
* <tex>PA = AP = A</tex>
 +
|proof=
 +
Домножим <tex>(1)</tex> на <tex>\pi</tex>. Таким образом, мы получим, что предел последовательности <tex>\pi P^{n}</tex> в смысле Эйлера равен <tex>\pi A = \pi \xi \alpha</tex>. Значит, '''первый факт''' доказан.
 +
 
 +
 
 +
Так как вектор <tex>\alpha</tex> был получен из предельной матрицы для <tex>(kI + (1 - k)P)</tex>, являющейся регулярной переходной матрицей, то он будет её единственным неподвижным вероятностным вектором. Но матрица <tex>(kI + (1 - k)P)</tex> должна иметь те же неподвижные векторы, что и <tex>P</tex>, так как из соотношения
 +
:<tex>\pi (kI + (1 - k)P) = \pi</tex>,  
 +
следует, что
 +
:<tex>\pi (1 - k) P = \pi (1 - k)</tex>
 +
и поскольку <tex>k \ne 1</tex>, то <tex>\pi P = \pi</tex>. Получается, что '''второй факт''' доказан.
  
 +
 +
'''Третий факт''' следует из того, что <tex>P \xi = \xi</tex> для любой переходной матрицы и что <tex>\alpha P = \alpha</tex>.
 +
}}
  
 
==Пример==
 
==Пример==
[[File:Temp.gif|thumb|250px|Пример эргодической цепи]]
+
[[File:Ergo.jpg‎|thumb|250px|Пример циклической цепи]]
Рассмотрим эксперимент по бросанию честной монеты. Тогда соответствующая этому эксперименту марковская цепь будет иметь 2 состояния.
+
Самым простым примером циклической цепи является цепь из двух состояний, с переходной матрицей:
Рассмотрим матрицу, следующего вида: <tex>p_{ij}=0.5, i,j=1,2</tex>.
+
:<tex>P = \begin{pmatrix}
 +
0 & 1 \\       
 +
1 & 0
 +
\end{pmatrix}</tex> .
  
Такая матрица является стохастической, а, значит, корректно определяет марковскую цепь. Такая цепь является эргодической, так как существует эргодическое распределение <tex>\pi = (0.5,0.5)^{\top}</tex>, такое что <tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, i=1,2</tex>.
+
Стационарным распределением этой цепи будет <tex> \alpha = (0.5, 0.5) </tex>.
  
 
==См. также==
 
==См. также==
* [http://neerc.ifmo.ru/mediawiki/index.php/Марковская_цепь Марковская цепь]
+
*[[Марковская цепь]]
 
+
*[[Регулярная марковская цепь]]
* [http://neerc.ifmo.ru/mediawiki/index.php/Регулярная_марковская_цепь Регулярная марковская цепь]
+
*[[Примеры использования Марковских цепей]]
 
 
==Примечания==
 
# '''Общий сток''' - такая <tex>k</tex> вершина графа, что для любых двух различных вершин графа переходов <tex>i,j \, (i\neq j)</tex>, существуют ориентированные пути от вершины <tex>i</tex> к вершине <tex>k</tex> и от вершины <tex>j</tex> к вершине <tex>k</tex>.
 
# Ориентированный граф называется '''слабо-связным''', если является связным неориентированный граф, полученный из него заменой ориентированных рёбер неориентированными.
 
# Ориентированный граф называется '''сильно-связным''', если в нём существует (ориентированный) путь из любой вершины в любую другую, или, что эквивалентно, граф содержит ровно одну сильно связную компоненту.
 
# Если цепь Маркова такова, что её состояния образуют лишь один неразложимый класс <tex>^{[7]}</tex>, то она называется '''неразложимой'''.
 
# Возвратное состояние <tex>i</tex> называется '''положительным''', если <tex> \mathbb{E}[T_i] = \sum\limits_{n=1}^{\infty} n f^{(n)}_{ii} < \infty</tex> <tex>(</tex>где <tex>f_{ii}^{(n)} = \mathbb{P}(X_n = i,\; X_k \not= i, \, k=1,\ldots, n-1 \mid X_0 = i )</tex> — вероятность, выйдя из состояния <tex>i</tex>, вернуться в него ровно за <tex>n</tex> шагов<tex>)</tex>.
 
# Если <tex>d(j) = 1</tex>, то состояние j называется '''апериодическим''' <tex>(d(j) = \gcd \left(n \in \mathbb{N} \mid p_{jj}^{(n)} > 0 \right)</tex>, где <tex>gcd</tex>  обозначает наибольший общий делитель, называется периодом состояния <tex>j</tex>, <tex>p_{jj}^{(n)}</tex> матрица переходных вероятностей за <tex>n</tex> шагов<tex>)</tex>.
 
# Свойство сообщаемости порождает на пространстве состояний [[Отношение эквивалентности|отношение эквивалентности]]. Порождаемые классы эквивалентности называются '''неразложимыми классами'''.
 
  
==Ссылки==
+
== Источники информации ==
*[http://ru.wikipedia.org/wiki/Эргодическое_распределение Эргодическое распределение - Википедия]
 
  
*[http://ru.wikipedia.org/wiki/Дискретное_распределение#.D0.94.D0.B8.D1.81.D0.BA.D1.80.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F Дискретное распределение - Википедия]
+
*[http://ru.wikipedia.org/wiki/Эргодическое_распределение Википедия {{---}} Эргодическое распределение ]
 +
*[http://ru.wikipedia.org/wiki/Дискретное_распределение#.D0.94.D0.B8.D1.81.D0.BA.D1.80.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F Википедия {{---}} Дискретное распределение]
 +
*[http://en.wikipedia.org/wiki/Euler_summation Wikipedia {{---}} Euler summation]
 +
*Дж. Кемени, Дж. Снелл {{---}} Конечные цепи Маркова {{---}} изд. "Наука", 1970 г. {{---}} 129 c.
  
==Литература==
+
[[Категория:Дискретная математика и алгоритмы]]
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"
 
  
 
[[Категория: Марковские цепи]]
 
[[Категория: Марковские цепи]]

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

Определение:
Эргодическая марковская цепь (англ. ergodic Markov chain) — марковская цепь, целиком состоящая из одного эргодического класса.


Стационарный режим

Эргодические марковские цепи описываются сильно связным графом. Это означает, что в такой системе возможен переход из любого состояния [math]S_i[/math] в любое состояние [math]S_{j}, (i,j = 1,2,\ldots,n)[/math] за конечное число шагов.

Для эргодических цепей при достаточно большом времени функционирования ([math]t \to \infty[/math]) наступает стационарный режим, при котором вероятности [math]\alpha_i[/math] состояний системы не зависят от времени и не зависят от распределения вероятностей в начальный момент времени, то есть: [math]\alpha_i = const[/math].

Классификация эргодических цепей

Определение:
В эргодической цепи можно выделить циклические классы (англ. cyclic classes). Количество циклических классов [math] d [/math] называют периодом цепи (англ. period of Markov chain), если цепь состоит целиком из одного циклического класса, её называют регулярной. С течением времени текущее состояние движется по циклическим классам в определенном порядке, причем каждые [math]d[/math] шагов она оказывается в одном и том же циклическом классе.


Таким образом, эргодические цепи делятся на регулярные и циклические.

Эргодическая теорема

Определение:
Эргодическое (стационарное) распределение (англ. stationary distribution) — распределение [math]\alpha = (\alpha_1 \ldots \alpha_n )[/math], такое что [math]\alpha_i \gt 0[/math] и [math]\lim\limits_{n \to \infty} p_{ij}^{(n)} = \alpha_j[/math] (где [math]p_{ij}^{(n)}[/math] — вероятность оказаться в [math]j[/math]-ом состоянии, выйдя из [math]i[/math]-ого, через [math]n[/math] переходов).


Для регулярных цепей

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

Для циклических цепей

Теорема (Эргодическая теорема):
Для любой эргодической цепи последовательность степеней [math]P^{n}[/math] суммируется по Эйлеру к предельной матрице [math]A[/math], и эта предельная матрица имеет вид [math]A = \xi\alpha[/math], где [math]\alpha[/math] — положительный вероятностный вектор, [math]\xi[/math] - вектор-столбец из единиц.
Доказательство:
[math]\triangleright[/math]

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

Рассмотрим матрицу [math](kI + (1 - k)P)[/math] при некотором [math]k, ~ 0 \lt k \lt 1[/math]. Эта матрица является переходной матрицей. Она имеет положительные элементы на всех тех же местах, что и [math]P[/math], следовательно, она также задает эргодическую цепь. Также диагональные элементы этой матрицы положительны. Значит, в каждое состояние можно возвратиться за один шаг, а это значит, что [math]d = 1[/math]. Таким образом, новая цепь является регулярной.

Из эргодической теоремы для регулярных цепей следует, что [math](kI + (1 - k)P)^{n}[/math] стремится к матрице [math]A = \xi\alpha[/math], где [math]\alpha[/math] — положительный вероятностный вектор. Таким образом:

[math] A = \lim\limits_{x\to \infty} (kI + (1 - k)P)^{n}[/math]
[math] A = \lim\limits_{x\to \infty} \sum\limits_{i = 0}^{n} {n\choose i} k^{n - i} (1 - k)^{i} P^{i} ~~~~~ (1)[/math]
Но последнее равенство в точности означает, что последовательность [math]P^{n}[/math] суммируема по Эйлеру к [math]A[/math], причем суммируема при каждом значении [math]k[/math].
[math]\triangleleft[/math]

Следствия

Теорема:
Если [math]P, A, \alpha[/math] — объекты из предыдущей теоремы. Тогда справедливы факты:
  • Для любого вероятностного вектора [math]\pi[/math] последовательность [math]\pi P^{n}[/math] суммируема по Эйлеру к [math]\alpha[/math]
  • Вектор [math]\alpha[/math] является единственным неподвижным вектором матрицы [math]P[/math]
  • [math]PA = AP = A[/math]
Доказательство:
[math]\triangleright[/math]

Домножим [math](1)[/math] на [math]\pi[/math]. Таким образом, мы получим, что предел последовательности [math]\pi P^{n}[/math] в смысле Эйлера равен [math]\pi A = \pi \xi \alpha[/math]. Значит, первый факт доказан.


Так как вектор [math]\alpha[/math] был получен из предельной матрицы для [math](kI + (1 - k)P)[/math], являющейся регулярной переходной матрицей, то он будет её единственным неподвижным вероятностным вектором. Но матрица [math](kI + (1 - k)P)[/math] должна иметь те же неподвижные векторы, что и [math]P[/math], так как из соотношения

[math]\pi (kI + (1 - k)P) = \pi[/math],

следует, что

[math]\pi (1 - k) P = \pi (1 - k)[/math]

и поскольку [math]k \ne 1[/math], то [math]\pi P = \pi[/math]. Получается, что второй факт доказан.


Третий факт следует из того, что [math]P \xi = \xi[/math] для любой переходной матрицы и что [math]\alpha P = \alpha[/math].
[math]\triangleleft[/math]

Пример

Пример циклической цепи

Самым простым примером циклической цепи является цепь из двух состояний, с переходной матрицей:

[math]P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}[/math] .

Стационарным распределением этой цепи будет [math] \alpha = (0.5, 0.5) [/math].

См. также

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