1632
правки
Изменения
м
[[File:Markov_chain_example.png|thumb|273px|Пример марковской цепи]]
В общем случае для марковской цепи задают вектор Марковскую цепь можно представить в виде [[Основные определения теории графов#Ориентированные графы | графа]], в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из <tex> i </tex> в <tex> j </tex> написана вероятность перехода из <tex> i </tex> в <tex> j </tex>, то есть <tex> c_0p_{ij} </tex>. == Распределение вероятностей == Марковскую цепь в любой момент времени <tex> t </tex> можно охарактеризовать вектором-строкой <tex> c_t </tex> — распределением вероятностей по состояниям цепи (<tex>\ c_{0iti} </tex> {{---}} — вероятность того, что цепи в начале процесса марковская цепь находится момент времени <tex> t </tex> быть в состоянии <tex> i </tex>).
Марковскую цепь можно представить в виде графа, в котором вершины {{---}} это состояния процесса, а ребра {{---}} переходы между состояниями, и на ребре из <tex> i </tex> в <tex> j Если </tex> написана вероятность перехода из <tex> i </tex> в <tex> j c_i </tex>— текущее распределение вероятностей, то есть <tex> p_{ij} </tex>.можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода:
Вероятность Из ассоциативности произведения матриц следует, что для того, что чтобы узнать распределение вероятностей через <tex> r t </tex> шагов марковская цепь будет находиться , нужно умножить <tex> c_i </tex> на матрицу перехода, возведённую в степень <tex> t </tex>: <tex> c_{i + t} = c_{i} \times P^t </tex>. Для марковской цепи иногда задают начальное распределение <tex> c_0 </tex>, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют '''предельным''' (англ. ''limiting distribution'')). == Достижимость и сообщаемость ==Обозначим вероятность попасть из состояния <tex> i </tex> в состоянии состояние <tex> j </tex> равна за <tex> n </tex> переходов как <tex> c_p_{rjij} ^{(n)} </tex>. {{Определение|definition= Состояние <tex> j </tex> '''достижимо''' (c_0 Pангл. ''accesible'') из состояния <tex> i </tex>, если существует такое <tex> n </tex>, что <tex> p_{ij}^r{(n)} > 0 </tex>. Достижимость <tex> j </tex> из <tex> i </tex> обозначается <tex> i \rightarrow j </tex>. <br>}} {{Определение|definition=Состояния <tex> i </tex> и <tex> j </tex> '''сообщаются''' (англ. ''communicate'') [, если они достижимы друг из друга. Сообщаемость <tex> i </tex> и <tex> j] </tex>обозначается <tex> i \leftrightarrow j </tex>.}}
<tex> p_{ij}^{'''Неразложимая цепь''' (nангл. ''irreducible chain'')} </tex> {{---}} вероятность попасть из — цепь Маркова, в которой все состояния <tex> i </tex> в состояние <tex> j </tex> за <tex> n </tex> переходовобразуют один неразложимый класс.
Состояние <tex> j </tex> Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами''' (англ. ''ergodic classes''). Состояния в эргодических классах называются '''эргодическими''' (англ. ''ergodic''), '''возвратными''', или '''существенными''' (англ. ''essential''). Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''достижимонесущественными''' (англ. ''accesibleinessential'') .}} Если эргодический класс состоит из одного состояния , такое состояние является [[Марковская цепь#Поглощающая цепь|поглощающим]]. Из свойств частичного упорядочения, в любой цепи Маркова найдется хотя бы один эргодический класс. {{Определение|definition='''Эргодическая''' марковская цепь (англ. ''ergodic Markov chain'') — марковская цепь, целиком состоящая из одного эргодического класса.}} Пусть <tex> N_{i , j} </tex> — множество таких <tex> n </tex>, если существует такое что находясь в состоянии <tex> i </tex>, можно оказаться в состоянии <tex> j </tex> через <tex> n </tex>шагов. <tex> d_i </tex> — наибольший общий делитель чисел из множества <tex> N_{i, i} </tex>. {{Лемма|statement=Для <tex> i </tex> и <tex> j </tex>, принадлежащих одному классу эквивалентности по отношению достижимости, <tex> d_i = d_j = d </tex> и числа из множества <tex> N_{i, что j} </tex> сравнимы между собой по модулю <tex> d </tex>.|proof=Пусть <tex> p_a \in N_{iji, j}^, \ b \in N_{(n)i, j}, \ c \in N_{j, i} </tex>. Из <tex> 0 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 \rightarrow j in N_{i, i} </tex>. Значит, <brtex> a + c </tex> и <tex> b + c </tex> оба делятся на <tex> d </tex>Состояния '''сообщаются''' (''communicate''), если они достижимы друг из другато есть <tex> a </tex> и <tex> b </tex> сравнимы между собой по модулю <tex> d </tex>.
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами'''. Состояния в эргодических классах называются '''эргодическими''' (''ergodic''), '''возвратными''', или '''существенными'''. Если эргодический класс цепь состоит целиком из одного состояния, такое состояние называется '''поглощающим''' (''absorbing'').<br>Из свойств частичного упорядоченияциклического класса, в любой цепи Маркова найдется хотя бы один эргодический класс. <br>Все остальные неразложимые классы называются её называют '''невозвратными классами[[Регулярная марковская цепь|регулярной]]'''. Состояния, входящие в них, называются '''невозвратными''' или иначе — '''несущественнымициклической'''.
В примере на рисунке поглощающими являются состояния 3 и 4==Подсчет количества поглощащих состояний==Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, а непоглощающими где <tex>\mathtt{transition[i][2]}</tex> — вероятность перехода из состояния <tex>\mathtt{---transition[i][0]}</tex> в <tex>\mathtt{transition[i][1]} </tex>.Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition[j][2] = 1 и 2}</tex>. По этому признаку помно определить все поглощающие состояния в цепи.
* '''function''' findAbsorbings(transition: '''int'''[m][Теорема о поглощении2]): '''boolean''' absorbing[m]* '''for''' i = 0 '''to''' m - 1 '''if''' transition[http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D0%B8_%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D0%B0 Цепь Марковаi][0] == transition[i][1] '''and''' transition[i][2] == 1 absorbing[transition[i][0]]= ''true'' '''return''' absorbing
rollbackEdits.php mass rollback
{{Определение | definition ='''Цепь Маркова''' (англ. ''Markov chain'') {{---}} процесс, находящийся в одном из <tex>n</tex> состояний. При этомпоследовательность случайных событий с конечным или счётным числом исходов, если он находится в состоянии с номером <tex>i</tex>характеризующаяся тем, то он перейдет в состояние <tex>j</tex> с вероятностью <tex>p_{ij}</tex>что при фиксированном настоящем будущее независимо от прошлого.
Процесс в каждый момент времени находится в одном из <tex> n </tex> состояний. При этом, если он находится в состоянии с номером <tex> i </tex>, то он перейдет в состояние <tex> j </tex> с вероятностью <tex> p_{ij} </tex>. Матрицу <tex>P = ||p_{ij}||</tex> называют '''матрицей переходов'''(англ. ''transition matrix'').
}}
На матрицу переходов накладываются следующие условия:
Такая матрица называется ''стохастической''.
<tex> c_{i + 1} = c_{i} \times P </tex>.
== Классификация цепей и состояний ==
=== Неразложимая цепь ===
{{Определение
|definition=
'''Неразложимый класс''' (англ. ''communicating class'') — класс эквивалентности множества состояний по отношению сообщаемости. Если представить марковскую цепь как граф, неразложимый класс будет аналогичен [[Отношение связности, компоненты связности#Сильная связность | компоненте сильной связности]].
}}
{{Определение
|definition=
}}
=== [[Эргодическая марковская цепь|Эргодическая цепь]] ===
{{Определение
|id = sort_def
|definition=
}}
Введём числа <tex> t_{i, j}, 0 \leqslant t_{i, j} < d </tex>, так, что любой элемент из <tex> N_{i, j} </tex> сравним с <tex> t_{i, j} </tex> по модулю <tex> d </tex>.
=== Циклический класс ===
{{Определение
|definition=
'''Неразложимый Циклический класс''' (англ. ''communicating cyclic class'') {{---}} класс эквивалентности множества состояний по отношению сообщаемости. Если представить Марковскую цепь как граф, неразложимый класс будет аналогичен компоненте сильной связности. для любых элементов <tex> i </tex> и <tex> j </tex> которого верно равенство <brtex>'''Неразложимая цепь''' (''ireducible chain'') t_{{---i, j}} цепь Маркова, в которой все состояния образуют один неразложимый класс= 0 </tex>.
}}
{{Определение
|definition=
}}
Если цепь циклическая, у неё есть некоторый период <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 chainstate'') называется марковская цепь— состояние, из которого нельзя попасть ни в которой какое другое, то есть хотя бы одно <tex> i </tex> — поглощающее состояние и из любого состояния достижимо хотя бы одно поглощающее, если <tex> p_{ii} = 1 </tex>.
}}
{{Определение
|definition='''Поглощающей''' (англ. ''absorbing chain'') называется марковская цепь, в которой есть хотя бы одно поглощающее состояние и из любого состояния достижимо хотя бы одно поглощающее.
}}
В примере на рисунке поглощающими являются состояния <tex>3</tex> и <tex>4</tex>, а непоглощающими — <tex>1</tex> и <tex>2</tex>.
=== Пример ===
[[File:Markov-chain-example-complete.png|thumb|500px|Пример марковской цепи]]
На рисунке:
* достижимыми состояниями являются: <tex> 2 </tex> из <tex> 1 </tex> (непосредственно), <tex> 3 </tex> из <tex> 1 </tex> (непосредственно), <tex> 6 </tex> из <tex> 3 </tex> (к примеру, через цепочку состояний <tex> 3 \rightarrow 2 \rightarrow 4 \rightarrow 6 </tex>) и т.д.
* сообщаются состояния <tex> 1 </tex> и <tex> 2 </tex> (непосредственно), <tex> 6 </tex> и <tex> 7 </tex> (непосредственно), <tex <tex> 1 </tex> и <tex> 3 </tex> (достижимы друг из друга) и т. д.
* неразложимыми классами являются множества вершин <tex> \left \{ 1, 2, 3 \right \} </tex>, <tex> \left \{ 4 \right \} </tex>, <tex> \left \{ 5 \right \} </tex>, <tex> \left \{ 6, 7 \right \} </tex>;
* эргодическими классами являются множества вершин <tex> \left \{ 5 \right \} </tex>, <tex> \left \{ 6, 7 \right \} </tex>;
* поглощающим состоянием является состояние <tex> 5 </tex>.
* если расматривать <tex> \{6, 7\} </tex> отдельно, можно выделить два циклических класса <tex> \{6\} </tex> и <tex> \{7\} </tex> (на каждом шаге цепь переходит из одного состояния в другое, а через <tex> d = 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> — количество переходов
== Литература См. также ==*[[Эргодическая марковская цепь]]*[[Регулярная марковская цепь]]*[[Отношение связности, компоненты связности]]
== Источники информации ==* ''Романовский И.В. Романовский'' Дискретный анализ. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 270—279. — ISBN 5-7940-0114-3* ''«Дискретный анализ»Кемени Дж., Снелл Дж.''Конечные цепи Маркова. — М. : Наука, 1970. — 272 c.* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D0%B8_%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D0%B0 Википедия {{---}} Цепь Маркова]* [https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia {{---}} Absorbing Markov chain]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Марковские цепи ]]
