Изменения

== {{Определение |definition =='''Цепь Маркова''' (англ. ''Markov chain'') {{---}} последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого.

{{Определение | definition ='''Цепь Маркова''' {{---}} процесс, находящийся Процесс в каждый момент времени находится в одном из <tex>n</tex> состояний. При этом, если он находится в состоянии с номером <tex>i</tex>, то он перейдет в состояние <tex>j</tex> с вероятностью <tex>p_{ij}</tex>.

При этом, если он находится в состоянии с номером <tex> i </tex>, то он перейдет в состояние <tex> j </tex> с вероятностью <tex> p_{ij} </tex>. Матрицу <tex>P = ||p_{ij}||</tex> называют '''матрицей переходов'''(англ. ''transition matrix'').

В общем случае Марковскую цепь можно представить в виде [[Основные определения теории графов#Ориентированные графы | графа]], в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из <tex> i </tex> в <tex> j </tex> написана вероятность перехода из <tex> i </tex> в <tex> j </tex>, то есть <tex> p_{ij} </tex>. == Распределение вероятностей == Марковскую цепь в любой момент времени <tex> t </tex> можно охарактеризовать вектором-строкой <tex> c_t </tex> — распределением вероятностей по состояниям цепи (<tex> c_{ti} </tex> — вероятность цепи в момент времени <tex> t </tex> быть в состоянии <tex> i </tex>). Если <tex> c_i </tex> — текущее распределение вероятностей, то можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода: <tex> c_{i + 1} = c_{i} \times P </tex>. Из ассоциативности произведения матриц следует, что для того, чтобы узнать распределение вероятностей через <tex> 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_{ij}^{0i(n)} </tex> . {{Определение|definition=Состояние <tex> j </tex> '''достижимо''' (англ. ''accesible'') из состояния <tex> i </tex>, если существует такое <tex> n </tex>, что <tex> p_{ij}^{---(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>.}}

Марковскую == Классификация цепей и состояний ===== Неразложимая цепь можно ==={{Определение|definition='''Неразложимый класс''' (англ. ''communicating class'') — класс эквивалентности множества состояний по отношению сообщаемости. Если представить в виде графамарковскую цепь как граф, в котором вершины {{---}} это состояния процессанеразложимый класс будет аналогичен [[Отношение связности, а ребра {{---компоненты связности#Сильная связность | компоненте сильной связности]].}} переходы между состояниями, и на ребре из <tex> i </tex> в <tex> j </tex> написана вероятность перехода из <tex> i </tex> в <tex> j </tex>, то есть <tex> p_{ij} </tex>.

{{Определение|definition== Состояния =='''Неразложимая цепь''' (англ. ''irreducible chain'') — цепь Маркова, в которой все состояния образуют один неразложимый класс.}}

<tex> p_{ij}^{Упорядочим (nочевидно, упорядочение будет частичным)} </tex> {{---}} вероятность попасть из состояния <tex> i </tex> неразложимые классы отношением достижимости. Минимальные элементы в состояние <tex> j </tex> за <tex> n </tex> переходовтаком упорядочении называются '''эргодическими классами''' (англ. ''ergodic classes''). Состояния в эргодических классах называются '''эргодическими''' (англ. ''ergodic''), '''возвратными''', или '''существенными''' (англ. ''essential''). Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными''' (англ. ''inessential'').

Состояние <tex> j </tex> '''достижимоЭргодическая''' из состояния <tex> i </tex>, если существует такое <tex> n </tex>, что <tex> p_{ij}^{марковская цепь (n)} > 0 </tex>англ. Достижимость <tex> j </tex> из <tex> i </tex> обозначается <tex> i \rightarrow j </tex>. <br>Состояния '''сообщаются'ergodic Markov chain'') — марковская цепь, если они достижимы друг целиком состоящая из другаодного эргодического класса.

'''Неразложимый Циклический класс''' (англ. ''cyclic class'') {{---}} класс эквивалентности множества состояний по отношению сообщаемости. Если представить Марковскую цепь как граф, неразложимый класс будет аналогичен компоненте сильной связности. для любых элементов <tex> i </tex> и <tex> j </tex> которого верно равенство <brtex>'''Неразложимая цепь''' 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|Элементарный цикл]]|<brtex>\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}<br/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> 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\} 1 </tex> и <tex> \{7\} </tex> (на каждом шаге цепь переходит из одного состояния в другое, а через <tex> d = 2</tex> шага возвращается в одно и то же состояние.

== Смотри также Подсчет количества поглощащих состояний==Пусть <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}</tex>. По этому признаку помно определить все поглощающие состояния в цепи.

===Псевдокод===* <tex>\mathtt{absorbing}: boolean:[http:\mathtt{n}]</tex> — массив состояний. Если <tex>i</neerc.ifmo.rutex> — посглощающее состояние, то <tex>\mathtt{absorbing[i]} = true</mediawikitex>*<tex>\mathtt{n}</index.phptex> — количество состояний*<tex>\mathtt{m}</Теорема_о_поглощении Теорема о поглощении]tex> — количество переходов

* '''function''' findAbsorbings(transition: '''int'''[m][http2])://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 Цепь Маркова '''boolean''' absorbing[m] '''for''' i = 0 '''to''' m - 1 '''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2]== 1* absorbing[transition[i][http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2,_%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B9_%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B5%D0%B2%D0%B8%D1%87_(%D1%81%D1%82%D0%B0%D1%80%D1%88%D0%B8%D0%B9) Андрей Андреевич Марков0]]= ''true'' '''return''' absorbing

== Литература См. также ==*[[Эргодическая марковская цепь]]*[[Регулярная марковская цепь]]*[[Отношение связности, компоненты связности]]

== Источники информации ==* ''Романовский И.В. Романовский'' Дискретный анализ. — СПб.: Невский Диалект; БХВ-Петербург, 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]