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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 11: Строка 11:
  
 
Эргодические цепи могут быть [[Регулярная марковская цепь|регулярными]] или '''циклическими'''. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (цикл) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.
 
Эргодические цепи могут быть [[Регулярная марковская цепь|регулярными]] или '''циклическими'''. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (цикл) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.
 +
 +
Эргодическая цепь характеризуется тем, что она состоит из одного эргодического класса, т.е. что можно перейти их каждого состояния в любое другое. Но если <tex>d > 1</tex> (<tex>d</tex> - количество циклических классов), то такие переходы возможны только при некоторых специальных значениях числа шагов <tex>n</tex>. Таким образом, никакая степень матрицы переходов <tex>P</tex> не является положительной матрицей, и различные степени содержат нули на различных местах. С увеличением степени расположение этих нулей циклически повторяется. Следовательно, последовательность <tex>P^{n}</tex> не может сходиться. В этом и состоит основное различие между ''циклическими'' и ''регулярными'' цепями.
  
 
==Стационарный режим==
 
==Стационарный режим==

Версия 03:26, 4 февраля 2012

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


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

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

Эргодические марковские цепи описываются сильно связным графом. Это означает, что в такой системе возможен переход из любого состояния [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.