Изменения

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

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

Марковскую цепь можно представить в виде [[Основные определения теории графов#Ориентированные графы | графа]], в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из <tex> i </tex> в <tex> j </tex> написана вероятность перехода из <tex> i </tex> в <tex> j </tex>, то есть <tex> p_{ij} </tex>.

Для марковской цепи иногда задают начальное распределение <tex> c_0 </tex>, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют '''предельным'''(англ. ''limiting distribution'')).

Состояние <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>

Состояния <tex> i </tex> и <tex> j </tex> '''сообщаются''' (англ. ''communicate''), если они достижимы друг из друга. Сообщаемость <tex> i </tex> и <tex> j </tex> обозначается <tex> i \leftrightarrow j </tex>.

'''Неразложимый класс''' (англ. ''communicating class'') — класс эквивалентности множества состояний по отношению сообщаемости. Если представить марковскую цепь как граф, неразложимый класс будет аналогичен [[Отношение связности, компоненты связности#Сильная связность | компоненте сильной связности]].

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

Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами'''(англ. ''ergodic classes''). Состояния в эргодических классах называются '''эргодическими''' (англ. ''ergodic''), '''возвратными''', или '''существенными'''(англ. ''essential''). Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными'''(англ. ''inessential'').

Если эргодический класс состоит из одного состояния, такое состояние называется '''поглощающимЭргодическая''' марковская цепь (англ. ''absorbingergodic 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>.

'''ЭргодическаяЦиклический класс''' марковская цепь — марковская цепь(англ. ''cyclic class'') {{---}} класс, для любых элементов <tex> i </tex> и <tex> j </tex> которого верно равенство <tex> t_{i, целиком состоящая из одного эргодического классаj} = 0 </tex>.

В эргодической цепи можно выделить циклические классы. Количество циклических классов <tex> d </tex> называют '''периодом цепи''', если Если цепь состоит целиком из одного циклического класса, её называют '''[[Регулярная марковская цепь|регулярной]]. С течением времени текущее состояние движется по циклическим классам в определенном порядке, причем каждые '''d''' шагов она оказывается в одном и том же циклическом классе. Таким образом, иначе — '''циклический классциклической''' — класс, в котором цепь оказывается каждый <tex> d </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>.

|definition='''Поглощающей''' (англ. ''absorbing chain'') называется марковская цепь, в которой есть хотя бы одно поглощающее состояние и из любого состояния достижимо хотя бы одно поглощающее.

В примере на рисунке поглощающими являются состояния <tex>3 </tex> и <tex>4</tex>, а непоглощающими — <tex>1 </tex> и <tex>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:[\mathtt{n}]</tex> — массив состояний. Если <tex>i</tex> — посглощающее состояние, то <tex>\mathtt{absorbing[i]} = true</tex>*<tex>\mathtt{n}</tex> — количество состояний*<tex>\mathtt{m}</tex> — количество переходов  '''function''' findAbsorbings(transition: '''int'''[m][2]): '''boolean''' absorbing[m] '''for''' i = 0 '''to''' m - 1 '''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1 absorbing[transition[i][0]] = ''true'' '''return''' absorbing == См. также ==*[[Эргодическая марковская цепь]]*[[Регулярная марковская цепь]]*[[Отношение связности, компоненты связности]]

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