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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
  
 
Марковскую цепь обладающую следующими свойствами называют '''слабо эргодическиой''', если она обладает следующими свойствами:
 
Марковскую цепь обладающую следующими свойствами называют '''слабо эргодическиой''', если она обладает следующими свойствами:
# Для любых двух различных вершин графа переходов <tex>i,j \, (i\neq j)</tex> найдется такая вершина <tex>k</tex> графа («общий сток»), что существуют ориентированные пути от вершины <math>i</math> к вершине <math>k</math> и от вершины <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>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> матрица переходных вероятностей стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
 
# При <tex>t \to \infty</tex> матрица переходных вероятностей стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
Строка 11: Строка 11:
  
 
[[Файл:MarkovTriangle.png|thumb|350px|Примеры графов переходов для цепей Маркова:
 
[[Файл:MarkovTriangle.png|thumb|350px|Примеры графов переходов для цепей Маркова:
  a) цепь не является слабо эргодической (не существует общего стока для состояний <math>A_2, \, A_3</math>);   
+
  a) цепь не является слабо эргодической (не существует общего стока<tex>^1</tex> для состояний <math>A_2, \, A_3</math>);   
  b) слабо эргодическая, но не эргодическая цепь (граф переходов является слабо-связным<tex>^1</tex>)  
+
  b) слабо эргодическая, но не эргодическая цепь (граф переходов является слабо-связным<tex>^2</tex>)  
  c) эргодическая цепь (сильно-связный<tex>^2</tex> граф переходов).]]
+
  c) эргодическая цепь (сильно-связный<tex>^3</tex> граф переходов).]]
  
 
==Основная теорема об эргодических распределениях==
 
==Основная теорема об эргодических распределениях==
Строка 41: Строка 41:
  
 
==Примечания==
 
==Примечания==
 +
# '''Общий сток''' - такая <tex>k</tex> вершина графа, что для любых двух различных вершин графа переходов <tex>i,j \, (i\neq j)</tex>, существуют ориентированные пути от вершины <tex>i</tex> к вершине <tex>k</tex> и от вершины <tex>j</tex> к вершине <tex>k</tex>.
 
# Ориентированный граф называется '''слабо-связным''', если является связным неориентированный граф, полученный из него заменой ориентированных рёбер неориентированными.
 
# Ориентированный граф называется '''слабо-связным''', если является связным неориентированный граф, полученный из него заменой ориентированных рёбер неориентированными.
 
# Ориентированный граф называется '''сильно-связным''', если в нём существует (ориентированный) путь из любой вершины в любую другую, или, что эквивалентно, граф содержит ровно одну сильно связную компоненту.
 
# Ориентированный граф называется '''сильно-связным''', если в нём существует (ориентированный) путь из любой вершины в любую другую, или, что эквивалентно, граф содержит ровно одну сильно связную компоненту.

Версия 07:44, 24 декабря 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].


Марковскую цепь обладающую следующими свойствами называют слабо эргодическиой, если она обладает следующими свойствами:

  1. Для любых двух различных вершин графа переходов [math]i,j \, (i\neq j)[/math] найдется такая вершина [math]k[/math] графа («общий сток»), что существуют ориентированные пути от вершины [math]i[/math] к вершине [math]k[/math] и от вершины [math]j[/math] к вершине [math]k[/math]. Замечание: возможен случай [math]k=i[/math] или [math]k=j[/math]; в этом случае тривиальный (пустой) путь от [math]i[/math] к [math]i[/math] или от [math]j[/math] к [math]j[/math] также считается ориентированным путем.
  2. Нулевое собственное число матрицы интенсивности невырождено.
  3. При [math]t \to \infty[/math] матрица переходных вероятностей стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).


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

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

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

Ссылки

Литература

Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"