Марковская цепь

2012-03-10T11:41:08Z

109.188.173.170:

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

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

На матрицу переходов накладываются следующие условия:

# <tex> p_{ij} \geqslant 0 </tex>
# <tex> \forall i\ \ \sum\limits_{j} p_{ij} = 1 </tex>

Такая матрица называется ''стохастической''.

Марковскую цепь можно представить в виде графа, в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из <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>, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют '''предельным''').

== Достижимость и сообщаемость ==
Обозначим вероятность попасть из состояния <tex> i </tex> в состояние <tex> j </tex> за <tex> n </tex> переходов как <tex> p_{ij}^{(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'') — класс эквивалентности множества состояний по отношению сообщаемости. Если представить марковскую цепь как граф, неразложимый класс будет аналогичен компоненте сильной связности.
}}

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

=== [[Эргодическая марковская цепь|Эргодическая цепь]] ===
{{Определение
|id = sort_def
|definition=
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами'''. Состояния в эргодических классах называются '''эргодическими''' (''ergodic''), '''возвратными''', или '''существенными'''. Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными'''.
}}

{{Определение
|id=absorb
|definition=
Если эргодический класс состоит из одного состояния, такое состояние называется '''поглощающим''' (''absorbing'').
}}

Из свойств частичного упорядочения, в любой цепи Маркова найдется хотя бы один эргодический класс.

{{Определение
|definition=
'''Эргодическая''' марковская цепь — марковская цепь, целиком состоящая из одного эргодического класса.
}}

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

Таким образом, эргодические цепи делятся на [[Регулярная марковская цепь|регулярные]] и '''циклические'''.

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

В примере на рисунке поглощающими являются состояния 3 и 4, а непоглощающими — 1 и 2.

=== Пример ===
[[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> шага возвращается в одно и то же состояние.

== Литература ==

* И.В. Романовский «Дискретный анализ». 3-е изд., 2003. стр. 270—279
* Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"
* [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 Википедия — Цепь Маркова]

[[Категория:Дискретная математика и алгоритмы]]

[[Категория: Марковские цепи ]]

Викиконспекты - Вклад участника [ru]

Марковская цепь