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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
:<tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, \quad \forall i=1,2, \ldots</tex>.
 
:<tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j, \quad \forall i=1,2, \ldots</tex>.
 
}}
 
}}
−
 
−
Марковскую цепь обладающую следующими свойствами называют '''слабо эргодическиой''', если она обладает следующими свойствами:
 
−
# Для любых двух различных вершин графа переходов <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>t \to \infty</tex> матрица переходных вероятностей стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
 
−
 
  
 
[[Файл:MarkovTriangle.png|thumb|350px|Примеры графов переходов для цепей Маркова:
 
[[Файл:MarkovTriangle.png|thumb|350px|Примеры графов переходов для цепей Маркова:
Строка 21: Строка 15:
 
|statement=
 
|statement=
 
Пусть <tex>\{X_n\}_{n \ge 0}</tex> - цепь Маркова с дискретным пространством состояний и матрицей переходных вероятностей <tex>P = (p_{ij}),\; i,j=1,2,\ldots</tex>. Тогда эта цепь является эргодической тогда и только тогда, когда она
 
Пусть <tex>\{X_n\}_{n \ge 0}</tex> - цепь Маркова с дискретным пространством состояний и матрицей переходных вероятностей <tex>P = (p_{ij}),\; i,j=1,2,\ldots</tex>. Тогда эта цепь является эргодической тогда и только тогда, когда она
−
# Неразложима <tex>^{[4]}</tex>;
+
# Неразложима (т.е. цепь Маркова такова, что её состояния образуют лишь один неразложимый класс <ref>Свойство сообщаемости порождает на пространстве состояний [[Отношение эквивалентности|отношение эквивалентности]]. Порождаемые классы эквивалентности называются '''неразложимыми классами'''.</ref>);
−
# Положительно возвратна <tex>^{[5]}</tex>;
+
# Положительно возвратна;
−
# Апериодична <tex>^{[6]}</tex>.
+
# Апериодична.
 
Эргодическое распределение <tex>\mathbf{\pi}</tex> тогда является единственным решением системы:  
 
Эргодическое распределение <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>.}}
 
:<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>.}}
Строка 43: Строка 37:
  
 
<references />
 
<references />
−
 
−
# Если цепь Маркова такова, что её состояния образуют лишь один неразложимый класс <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>.
 
−
# Свойство сообщаемости порождает на пространстве состояний [[Отношение эквивалентности|отношение эквивалентности]]. Порождаемые классы эквивалентности называются '''неразложимыми классами'''.
 
  
 
==Ссылки==
 
==Ссылки==
Строка 55: Строка 44:
  
 
==Литература==
 
==Литература==
−
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова" стр.129 (Издательство "Наука", 1970 г)
+
Дж. Кемени, Дж. Снелл "Конечные цепи Маркова" - Издательство "Наука", 1970 г - 129 c.
  
 
[[Категория: Марковские цепи]]
 
[[Категория: Марковские цепи]]

Версия 05:38, 28 декабря 2011

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


Примеры графов переходов для цепей Маркова: a) цепь не является слабо эргодической (не существует общего стока [1] для состояний [math]A_2, \, A_3[/math]); b) слабо эргодическая, но не эргодическая цепь (граф переходов является слабо-связным) c) эргодическая цепь (сильно-связный граф переходов).

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

Теорема (Основная теорема об эргодических распределениях):
Пусть [math]\{X_n\}_{n \ge 0}[/math] - цепь Маркова с дискретным пространством состояний и матрицей переходных вероятностей [math]P = (p_{ij}),\; i,j=1,2,\ldots[/math]. Тогда эта цепь является эргодической тогда и только тогда, когда она
  1. Неразложима (т.е. цепь Маркова такова, что её состояния образуют лишь один неразложимый класс [2]);
  2. Положительно возвратна;
  3. Апериодична.

Эргодическое распределение [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_{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].

См. также

Примечания

  1. ↑ Общий сток - такая [math]k[/math] вершина графа, что для любых двух различных вершин графа переходов [math]i,j \, (i\neq j)[/math], существуют ориентированные пути от вершины [math]i[/math] к вершине [math]k[/math] и от вершины [math]j[/math] к вершине [math]k[/math].
  2. ↑ Свойство сообщаемости порождает на пространстве состояний отношение эквивалентности. Порождаемые классы эквивалентности называются неразложимыми классами.

Ссылки

Литература

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

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