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

Материал из Викиконспекты
Перейти к: навигация, поиск
(переструктурировал, выпилил треш)
Строка 3: Строка 3:
 
'''Эргодическая''' [[Марковская цепь|марковская цепь]] {{---}} марковская цепь, целиком состоящая из одного эргодического класса.
 
'''Эргодическая''' [[Марковская цепь|марковская цепь]] {{---}} марковская цепь, целиком состоящая из одного эргодического класса.
 
}}
 
}}
−
 
−
{{Определение
 
−
|definition=
 
−
'''Эргодическое распределение''' - распределение <tex>\pi = (\pi_1,\pi_2,\ldots )</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>p_{ij}^{(n)}</tex> - вероятность оказаться в <tex>j</tex>-ом состоянии, выйдя из <tex>i</tex>-ого, через <tex>n</tex> переходов).
 
−
}}
 
−
 
−
Эргодические цепи могут быть [[Регулярная марковская цепь|регулярными]] или '''циклическими'''. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (цикл) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.
 
−
 
−
Эргодическая цепь характеризуется тем, что она состоит из одного эргодического класса, т.е. что можно перейти их каждого состояния в любое другое. Но если <tex>d > 1</tex> (<tex>d</tex> - количество циклических классов), то такие переходы возможны только при некоторых специальных значениях числа шагов <tex>n</tex>. Таким образом, никакая степень матрицы переходов <tex>P</tex> не является положительной матрицей, и различные степени содержат нули на различных местах. С увеличением степени расположение этих нулей циклически повторяется. Следовательно, последовательность <tex>P^{n}</tex> не может сходиться. В этом и состоит основное различие между ''циклическими'' и ''регулярными'' цепями.
 
  
 
==Стационарный режим==
 
==Стационарный режим==
Строка 19: Строка 9:
 
Для эргодических цепей при достаточно большом времени функционирования (<tex>t \to \infty</tex>) наступает '''стационарный режим''', при котором вероятности <tex>\pi_i</tex> состояний системы не зависят от времени и не зависят от распределения вероятностей в начальный момент времени, т.е. <tex>\pi_i = const</tex>.
 
Для эргодических цепей при достаточно большом времени функционирования (<tex>t \to \infty</tex>) наступает '''стационарный режим''', при котором вероятности <tex>\pi_i</tex> состояний системы не зависят от времени и не зависят от распределения вероятностей в начальный момент времени, т.е. <tex>\pi_i = const</tex>.
  
−
Для определения стационарных вероятностей <tex>\pi_i</tex> нахождения системы в состоянии <tex>S_{i}</tex> нужно составить систему <tex>n</tex> линейных однородных алгебраических уравнений с <tex>n</tex> неизвестными:
+
== Классификация эргодических цепей ==
 +
 
 +
{{Определение
 +
|definition=
 +
В эргодической цепи можно выделить '''циклические классы'''. Количество циклических классов <tex> d </tex> называют '''периодом цепи''', если цепь состоит целиком из одного циклического класса, её называют [[Регулярная марковская цепь|регулярной]]. С течением времени текущее состояние движется по циклическим классам в определенном порядке, причем каждые '''d''' шагов она оказывается в одном и том же циклическом классе.
 +
}}
 +
 
 +
Таким образом, эргодические цепи делятся на [[Регулярная марковская цепь|регулярные]] и '''циклические'''.
  
−
<tex>\pi_{i} = \sum\limits_{j=1}^{n}(\pi_{j} \times p_{ji})</tex>, где <tex>i = 1,2,...,n</tex>
+
== Эргодическая теорема ==
 +
{{Определение
 +
|definition=
 +
'''Эргодическое (стационарное) распределение''' - распределение <tex>\pi = (\pi_1,\pi_2,\ldots )</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>p_{ij}^{(n)}</tex> - вероятность оказаться в <tex>j</tex>-ом состоянии, выйдя из <tex>i</tex>-ого, через <tex>n</tex> переходов).
 +
}}
  
−
Можно заметить, что так как все свободные члены равны нулю, система имеет бесконечное число решений. Однако, у нас есть дополнительные условия на решение: <tex>\sum\limits_{j=1}^{n}\pi_{i} = 1</tex> и <tex> \pi_i \ge 0 </tex>. Следующая теорема утверждает единственность решения такой системы.
+
=== Для регулярных цепей ===
 +
Доказательство теоремы для случая регулярных цепей приведено в конспекте про [[Регулярная марковская цепь#Эргодическая теорема для регулярных цепей | регулярные цепи]].
  
−
==Основная теорема об эргодических распределениях==
+
=== Для циклических цепей ===
 
{{
 
{{
 
Теорема
 
Теорема
−
|about=Основная теорема об эргодических распределениях
+
|about=Эргодическая теорема
 
|statement=
 
|statement=
−
Для эргодической марковской цепи эргодическое распределение <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>.
+
|proof=
 +
 
 +
 
 +
В случае циклической цепи переходы из одного циклического класса в другой возможны только при определенных значениях <tex> n </tex>, которые периодически повторяются. Таким образом, никакая степень матрицы переходов <tex>P</tex> не является положительной матрицей, и различные степени содержат нули на различных местах. С увеличением степени расположение этих нулей периодически повторяется. Следовательно, последовательность <tex>P^{n}</tex> не может сходиться в обычном смысле, для нее требуется так называемая суммируемость по Эйлеру. блаблабла доказательство
 
}}
 
}}
  

Версия 22:51, 6 февраля 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] d [/math] называют периодом цепи, если цепь состоит целиком из одного циклического класса, её называют регулярной. С течением времени текущее состояние движется по циклическим классам в определенном порядке, причем каждые d шагов она оказывается в одном и том же циклическом классе.


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

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

Определение:
Эргодическое (стационарное) распределение - распределение [math]\pi = (\pi_1,\pi_2,\ldots )[/math], такое что [math]\pi_i \gt 0,\; i \in \mathbb{N}[/math] и [math]\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, ~ \forall i \in \mathbb{N}[/math] (где [math]p_{ij}^{(n)}[/math] - вероятность оказаться в [math]j[/math]-ом состоянии, выйдя из [math]i[/math]-ого, через [math]n[/math] переходов).


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

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

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

Теорема (Эргодическая теорема):
здесь был треш
Доказательство:
[math]\triangleright[/math]
В случае циклической цепи переходы из одного циклического класса в другой возможны только при определенных значениях [math] n [/math], которые периодически повторяются. Таким образом, никакая степень матрицы переходов [math]P[/math] не является положительной матрицей, и различные степени содержат нули на различных местах. С увеличением степени расположение этих нулей периодически повторяется. Следовательно, последовательность [math]P^{n}[/math] не может сходиться в обычном смысле, для нее требуется так называемая суммируемость по Эйлеру. блаблабла доказательство
[math]\triangleleft[/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=18033»