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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
  
 
Эргодические цепи могут быть [[Регулярная марковская цепь|регулярными]] или '''циклическими'''. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (цикл) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.
 
Эргодические цепи могут быть [[Регулярная марковская цепь|регулярными]] или '''циклическими'''. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (цикл) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.
−
 
−
называется эргодической, если существует дискретное распределение (называемое эргодическим) <tex>\pi = (\pi_1,\pi_2,\ldots )^{\top}</tex>, такое что <tex>\pi_i > 0,\; i \in \mathbb{N}</tex> и
 
−
:<tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, ~ \forall i \in \mathbb{N}</tex> (вероятность оказаться в <tex>j</tex>-ом состоянии, выйдя из <tex>i</tex>-ого, через <tex>n</tex> переходов).
 
−
 
−
 
  
 
==Стационарный режим==
 
==Стационарный режим==
Строка 20: Строка 15:
 
<tex>\pi_{i} = \sum\limits_{j=1}^{n}(\pi_{j} \times p_{ji})</tex>, где <tex>i = 1,2,...,n</tex>
 
<tex>\pi_{i} = \sum\limits_{j=1}^{n}(\pi_{j} \times p_{ji})</tex>, где <tex>i = 1,2,...,n</tex>
  
−
Можно заметить, что так как все свободные члены равны нулю, система имеет бесконечное число решений. Однако, у нас есть дополнительные условия на решение: <tex>\sum\limits_{j=1}^{n}\pi_{i} = 1</tex> и <tex> \pi_i > 0 </tex>. Следующая теорема утверждает единственность решения такой системы.
+
Можно заметить, что так как все свободные члены равны нулю, система имеет бесконечное число решений. Однако, у нас есть дополнительные условия на решение: <tex>\sum\limits_{j=1}^{n}\pi_{i} = 1</tex> и <tex> \pi_i \ge 0 </tex>. Следующая теорема утверждает единственность решения такой системы.
  
 
==Основная теорема об эргодических распределениях==
 
==Основная теорема об эргодических распределениях==
Строка 27: Строка 22:
 
|about=Основная теорема об эргодических распределениях
 
|about=Основная теорема об эргодических распределениях
 
|statement=
 
|statement=
−
Пусть <tex>\{X_n\}_{n \ge 0}</tex> - цепь Маркова с дискретным пространством состояний и [[Марковская цепь|матрицей переходных вероятностей]] <tex>P = (p_{ij}),\; i,j=1,2,\ldots</tex>. Тогда эта цепь является эргодической тогда и только тогда, когда она
+
Для эргодической марковской цепи эргодическое распределение <tex>\mathbf{\pi}</tex> является единственным решением системы:  
−
# Неразложима (т.е. цепь Маркова такова, что её состояния образуют лишь один неразложимый класс <ref>
+
:<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>\{X_n\}_{n \ge 0}</tex> — цепь Маркова с тремя состояниями <tex>\{1,2,3\}</tex>, и её матрица переходных вероятностей имеет вид
 
−
: <tex>P = \left(
 
−
\begin{matrix}
 
−
0.5 & 0.5 & 0 \\
 
−
0.1 & 0.9 & 0 \\
 
−
0 & 0 & 1
 
−
\end{matrix}
 
−
\right).</tex>
 
−
Состояния этой цепи образуют два '''неразложимых класса''': <tex>\{1,2\}</tex> и <tex>\{3\}</tex> <tex>(1 \leftrightarrow 2</tex>, но <tex>1 \not\rightarrow 3</tex> и <tex>3 \not\rightarrow 1)</tex>. Т.е. если представить матрицу переходных вероятностей в виде графа, то он будет иметь две компоненты связности.
 
−
 
 
−
</ref>);
 
−
# Положительно возвратна (т.е. находится в таком состоянии, выйдя из которого возвращается в него за конечное время);
 
−
# Апериодична (т.е. находится в таком состоянии, которое навещается цепью через промежутки времени, не кратные фиксированному числу).
 
−
Эргодическое распределение <tex>\mathbf{\pi}</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>.}}
 
  
  
Строка 52: Строка 32:
  
 
Рассмотрим матрицу, следующего вида: <tex>p_{ij}=0.5, i,j=1,2</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>p_{ij}=0.5, i,j=1,2</tex>. Такая матрица является стохастической, а, значит, корректно определяет марковскую цепь. Такая цепь является эргодической, так как существует эргодическое распределение <tex>\pi = (0.5,0.5)^{\top}</tex>, такое что <tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, i=1,2</tex>.
−
 
−
==Примечания==
 
−
 
−
<references />
 
  
 
==Ссылки==
 
==Ссылки==

Версия 06:03, 17 января 2012

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


Эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (цикл) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.

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

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

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

Для определения стационарных вероятностей [math]\pi_i[/math] нахождения системы в состоянии [math]S_{i}[/math] нужно составить систему [math]n[/math] линейных однородных алгебраических уравнений с [math]n[/math] неизвестными:

[math]\pi_{i} = \sum\limits_{j=1}^{n}(\pi_{j} \times p_{ji})[/math], где [math]i = 1,2,...,n[/math]

Можно заметить, что так как все свободные члены равны нулю, система имеет бесконечное число решений. Однако, у нас есть дополнительные условия на решение: [math]\sum\limits_{j=1}^{n}\pi_{i} = 1[/math] и [math] \pi_i \ge 0 [/math]. Следующая теорема утверждает единственность решения такой системы.

Основная теорема об эргодических распределениях

Теорема (Основная теорема об эргодических распределениях):
Для эргодической марковской цепи эргодическое распределение [math]\mathbf{\pi}[/math] является единственным решением системы:
[math]\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}[/math].


Пример

Пример эргодической цепи

Рассмотрим эксперимент по бросанию честной монеты. Тогда соответствующая этому эксперименту марковская цепь будет иметь 2 состояния. Состояние меняется на противоположное, при бросании монеты, с вероятностью [math]p = 0.5[/math].

Рассмотрим матрицу, следующего вида: [math]p_{ij}=0.5, i,j=1,2[/math]. Такая матрица является стохастической, а, значит, корректно определяет марковскую цепь. Такая цепь является эргодической, так как существует эргодическое распределение [math]\pi = (0.5,0.5)^{\top}[/math], такое что [math]\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, i=1,2[/math].

Ссылки

Литература

Дж. Кемени, Дж. Снелл "Конечные цепи Маркова" - Издательство "Наука", 1970 г - 129 c.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Эргодическая_марковская_цепь&oldid=16957»