1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|definition =
'''Цепь Маркова''' (англ. ''Markov chain'') {{---}} последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого.
Процесс в каждый момент времени находится в одном из <tex> n </tex> состояний.
При этом, если он находится в состоянии с номером <tex> i </tex>, то он перейдет в состояние <tex> j </tex> с вероятностью <tex> p_{ij} </tex>.
Матрицу <tex> P = ||p_{ij}|| </tex> называют '''матрицей переходов'''(англ. ''transition matrix'').
}}
<tex> c_{i + t} = c_{i} \times P^t </tex>.
Для марковской цепи иногда задают начальное распределение <tex> c_0 </tex>, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют '''предельным'''(англ. ''limiting distribution'')).
== Достижимость и сообщаемость ==
{{Определение
|definition=
'''Неразложимая цепь''' (англ. ''ireducible irreducible chain'') — цепь Маркова, в которой все состояния образуют один неразложимый класс.
}}
|id = sort_def
|definition=
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами'''(англ. ''ergodic classes''). Состояния в эргодических классах называются '''эргодическими''' (англ. ''ergodic''), '''возвратными''', или '''существенными'''(англ. ''essential''). Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными'''(англ. ''inessential'').
}}
{{Определение
|definition=
'''Эргодическая''' марковская цепь (англ. ''ergodic Markov chain'') — марковская цепь, целиком состоящая из одного эргодического класса.
}}
{{Лемма
|statement=
Для <tex> i </tex> и <tex> j </tex>, принадлежащих одному классу эквивалентностипо отношению достижимости, <tex> d_i = d_j = d </tex> и числа из множества <tex> N_{i, j} </tex> сравнимы между собой по модулю <tex> d </tex>.
|proof=
Пусть <tex> a \in N_{i, j}, \ b \in N_{i, j}, \ c \in N_{j, i} </tex>. Из <tex> i </tex> можно попасть в <tex> j </tex> и обратно, значит, <tex> a + c \in N_{i, i} </tex>. Также после попадания в <tex> j </tex> можно сколько угодно раз перейти из него в самого себя, и только потом перейти в <tex> i </tex>, для этого понадобится <tex> a + k \cdot d_j + c </tex> шагов при любом достаточно большом <tex> k </tex>. Значит, <tex> d_j </tex> должно делиться на <tex> d_i </tex>. Но аналогично можно доказать, что <tex> d_i </tex> делится на <tex> d_j </tex>, поэтому <tex> d_i = d_j = d </tex>. Также можно перейти за <tex> b </tex> шагов в <tex> j </tex>, а потом попасть в <tex> i </tex>, поэтому <tex> b + c \in N_{i, i} </tex>. Значит, <tex> a + c </tex> и <tex> b + c </tex> оба делятся на <tex> d </tex>, то есть <tex> a </tex> и <tex> b </tex> сравнимы между собой по модулю <tex> d </tex>.
{{Определение
|definition=
'''Циклический класс''' — (англ. ''cyclic class'') {{---}} класс, для любых элементов <tex> i </tex> и <tex> j </tex> которого верно равенство <tex> t_{i, j} = 0 </tex>.
}}
}}
Если цепь циклическая, у неё есть некоторый период <tex> d > 1 </tex>, а её состояния подразделяются на <tex> d </tex> циклических классов. Цепь движется по циклическим классам в определённом порядке, возвращаясь в класс с начальным состоянием через <tex> d </tex> шагов. Топология циклических цепей разнообразна. Самым тривиальным случаем является элементарный цикл из <tex> n </tex> состояний и, следовательно, содержащий <tex> n </tex> циклический классов. Более сложный случай – простые циклы. Простой цикл состоит изнескольких циклов, пересекающихся по вершинам, но не пересекающихся поребрам. Все эти циклы обязаны не быть взаимно простыми. Иначе НОД длинэтих циклов равен единице, и цепь регулярна. Общий случай циклической цепи – цепь, состоящая из циклов, пересекающихся по вершинам и ребрам в представлении цепи как графа. ==== Примеры циклических цепей ==== {| class = "wikitable"! Изображение !! Матрица переходов !! Описание|-|style="background-color:#FFF" |[[Файл:N steps chain.png|400px|center|Элементарный цикл]]|<tex>\begin{pmatrix}0 & 1 & 0 & \cdots & 0 & 0 & 0 \\0 & 0 & 1 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\0 & 0 & 0 & \cdots & 0 & 0 & 1 \\1 & 0 & 0 & \cdots & 0 & 0 & 0\end{pmatrix}_N</tex>| Стохастическая матрица элементарного цикла всегда имеет по одной единице в каждом столбце и каждой строке. Таким образом, нужно ровно <tex> n </tex> шагов, проходящих через все вершины, чтобы попасть из вершины <tex> j </tex> в неё же.|-|style="background-color:#FFF" |[[Файл:Prime cyclic chain.png|200px|center|Простой цикл]]|<tex>\begin{pmatrix}0 & 0 & 0,5 & 0,5 & 0 & 0 \\1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 1 \\1 & 0 & 0 & 0 & 0 & 0\end{pmatrix}</tex>|Этот простой цикл состоит из двух элементарных, пересекающихся в вершине <tex> 1 </tex>. НОД длин всех путей из вершины <tex> 1 </tex> в вершину <tex> 1 </tex> равен <tex> 1 </tex>, поэтому можно получить предельное распределение.|-|}
=== Поглощающая цепь ===
{{Определение
|definition='''Поглощающее состояние''' (англ. ''absorbing state'') — состояние, из которого нельзя попасть ни в какое другое, то есть <tex> i </tex> — поглощающее состояние, если <tex> p_{ii} = 1 </tex>.
}}
{{Определение
}}
В примере на рисунке поглощающими являются состояния <tex>3 </tex> и <tex>4</tex>, а непоглощающими — <tex>1 </tex> и <tex>2</tex>.
=== Пример ===
===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> — массив состояний. Если <tex>i </tex> — посглощающее состояние , то <tex>\mathtt{absorbing[i] } = true</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов
absorbing[transition[i][0]] = ''true''
'''return''' absorbing
== См. также ==
*[[Эргодическая марковская цепь]]
*[[Регулярная марковская цепь]]
*[[Отношение связности, компоненты связности]]
== Источники информации ==
