Изменения

'''Цепь Маркова''' — процесс, находящийся в одном из <tex>n</tex> состояний(англ. При этом''Markov chain'') {{---}} последовательность случайных событий с конечным или счётным числом исходов, если он находится в состоянии с номером <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_0 i </tex>, где в <tex>\ c_{0i} j </tex> — написана вероятность тогоперехода из <tex> i </tex> в <tex> j </tex>, что в начале процесса марковская цепь находится в состоянии то есть <tex> i p_{ij} </tex>. Тогда можно узнать распределение вероятностей на следующем шаге, умножив вектор на матрицу перехода:

<tex> c_1 = c_0 \times P </tex>.= Распределение вероятностей ==

Для того, чтобы узнать распределение вероятностей через Марковскую цепь в любой момент времени <tex> t </tex> шагов, найдём вектор можно охарактеризовать вектором-строкой <tex> c_t </tex> — распределением вероятностей по состояниям цепи (вектор через <tex> t c_{ti} </tex> шагов), для чего нужно умножить — вероятность цепи в момент времени <tex> c_0 t </tex> на матрицу перехода, возведённую быть в степень состоянии <tex> t i </tex>:).

Если <tex> c_t = c_0 \times P^t c_i </tex>.— текущее распределение вероятностей, то можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода:

Марковскую цепь можно представить в виде графа, в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из <tex> c_{i + 1} = c_{i} \times P </tex> в . Из ассоциативности произведения матриц следует, что для того, чтобы узнать распределение вероятностей через <tex> j t </tex> написана вероятность перехода из шагов, нужно умножить <tex> i c_i </tex> на матрицу перехода, возведённую в степень <tex> j t </tex>, то есть : <tex> p_c_{i + t} = c_{iji} \times P^t </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>. {{Лемма|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>.

Из свойств частичного упорядоченияВведём числа <tex> t_{i, в j}, 0 \leqslant t_{i, j} < d </tex>, так, что любой цепи Маркова найдется хотя бы один эргодический классэлемент из <tex> N_{i, j} </tex> сравним с <tex> t_{i, j} </tex> по модулю <tex> d </tex>.

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

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

Если цепь циклическая, у неё есть некоторый период <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> 2 </tex> из <tex> 1 </tex>(непосредственно), <tex> 1 3 </tex> из <tex> 2 1 </tex>(непосредственно), <tex> 6 </tex> из <tex> 3 </tex> из (к примеру, через цепочку состояний <tex> 1 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> (достижимы друг из друга) и т. д.

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

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