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

Определение:

Цепь Маркова (англ. Markov chain) — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого. Процесс в каждый момент времени находится в одном из [math] n [/math] состояний. При этом, если он находится в состоянии с номером [math] i [/math], то он перейдет в состояние [math] j [/math] с вероятностью [math] p_{ij} [/math]. Матрицу [math] P = ||p_{ij}|| [/math] называют матрицей переходов (англ. transition matrix).

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

1. [math] p_{ij} \geqslant 0 [/math]
2. [math] \forall i\ \ \sum\limits_{j} p_{ij} = 1 [/math]

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

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

Распределение вероятностей

Марковскую цепь в любой момент времени [math] t [/math] можно охарактеризовать вектором-строкой [math] c_t [/math] — распределением вероятностей по состояниям цепи ([math] c_{ti} [/math] — вероятность цепи в момент времени [math] t [/math] быть в состоянии [math] i [/math]).

Если [math] c_i [/math] — текущее распределение вероятностей, то можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода:

[math] c_{i + 1} = c_{i} \times P [/math].

Из ассоциативности произведения матриц следует, что для того, чтобы узнать распределение вероятностей через [math] t [/math] шагов, нужно умножить [math] c_i [/math] на матрицу перехода, возведённую в степень [math] t [/math]:

[math] c_{i + t} = c_{i} \times P^t [/math].

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

Достижимость и сообщаемость

Обозначим вероятность попасть из состояния [math] i [/math] в состояние [math] j [/math] за [math] n [/math] переходов как [math] p_{ij}^{(n)} [/math].

Определение:

Состояние [math] j [/math] достижимо (англ. accesible) из состояния [math] i [/math], если существует такое [math] n [/math], что [math] p_{ij}^{(n)} \gt 0 [/math]. Достижимость [math] j [/math] из [math] i [/math] обозначается [math] i \rightarrow j [/math].

Определение:

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

Классификация цепей и состояний

Неразложимая цепь

Определение:

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

Определение:

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

Эргодическая цепь

Определение:

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

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

Определение:

Эргодическая марковская цепь (англ. ergodic Markov chain) — марковская цепь, целиком состоящая из одного эргодического класса.

Пусть [math] N_{i, j} [/math] — множество таких [math] n [/math], что находясь в состоянии [math] i [/math], можно оказаться в состоянии [math] j [/math] через [math] n [/math] шагов. [math] d_i [/math] — наибольший общий делитель чисел из множества [math] N_{i, i} [/math].

Лемма:

Для [math] i [/math] и [math] j [/math], принадлежащих одному классу эквивалентности по отношению достижимости, [math] d_i = d_j = d [/math] и числа из множества [math] N_{i, j} [/math] сравнимы между собой по модулю [math] d [/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math] a \in N_{i, j}, \ b \in N_{i, j}, \ c \in N_{j, i} [/math]. Из [math] i [/math] можно попасть в [math] j [/math] и обратно, значит, [math] a + c \in N_{i, i} [/math]. Также после попадания в [math] j [/math] можно сколько угодно раз перейти из него в самого себя, и только потом перейти в [math] i [/math], для этого понадобится [math] a + k \cdot d_j + c [/math] шагов при любом достаточно большом [math] k [/math]. Значит, [math] d_j [/math] должно делиться на [math] d_i [/math]. Но аналогично можно доказать, что [math] d_i [/math] делится на [math] d_j [/math], поэтому [math] d_i = d_j = d [/math]. Также можно перейти за [math] b [/math] шагов в [math] j [/math], а потом попасть в [math] i [/math], поэтому [math] b + c \in N_{i, i} [/math]. Значит, [math] a + c [/math] и [math] b + c [/math] оба делятся на [math] d [/math], то есть [math] a [/math] и [math] b [/math] сравнимы между собой по модулю [math] d [/math].

[math]\triangleleft[/math]

Введём числа [math] t_{i, j}, 0 \leqslant t_{i, j} \lt d [/math], так, что любой элемент из [math] N_{i, j} [/math] сравним с [math] t_{i, j} [/math] по модулю [math] d [/math].

Циклический класс

Определение:

Циклический класс (англ. cyclic class) — класс, для любых элементов [math] i [/math] и [math] j [/math] которого верно равенство [math] t_{i, j} = 0 [/math].

Определение:

Если цепь состоит целиком из одного циклического класса, её называют регулярной, иначе — циклической.

Если цепь циклическая, у неё есть некоторый период [math] d \gt 1 [/math], а её состояния подразделяются на [math] d [/math] циклических классов. Цепь движется по циклическим классам в определённом порядке, возвращаясь в класс с начальным состоянием через [math] d [/math] шагов.

Топология циклических цепей разнообразна. Самым тривиальным случаем является элементарный цикл из [math] n [/math] состояний и, следовательно, содержащий [math] n [/math] циклический классов. Более сложный случай – простые циклы. Простой цикл состоит из нескольких циклов, пересекающихся по вершинам, но не пересекающихся по ребрам. Все эти циклы обязаны не быть взаимно простыми. Иначе НОД длин этих циклов равен единице, и цепь регулярна. Общий случай циклической цепи – цепь, состоящая из циклов, пересекающихся по вершинам и ребрам в представлении цепи как графа.

Примеры циклических цепей

Изображение	Матрица переходов	Описание
	[math]\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 [/math]	Стохастическая матрица элементарного цикла всегда имеет по одной единице в каждом столбце и каждой строке. Таким образом, нужно ровно [math] n [/math] шагов, проходящих через все вершины, чтобы попасть из вершины [math] j [/math] в неё же.
	[math]\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} [/math]	Этот простой цикл состоит из двух элементарных, пересекающихся в вершине [math] 1 [/math]. НОД длин всех путей из вершины [math] 1 [/math] в вершину [math] 1 [/math] равен [math] 1 [/math], поэтому можно получить предельное распределение.

Поглощающая цепь

Определение:

Поглощающее состояние (англ. absorbing state) — состояние, из которого нельзя попасть ни в какое другое, то есть [math] i [/math] — поглощающее состояние, если [math] p_{ii} = 1 [/math].

Определение:

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

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

Пример

Пример марковской цепи

На рисунке:

• достижимыми состояниями являются: [math] 2 [/math] из [math] 1 [/math] (непосредственно), [math] 3 [/math] из [math] 1 [/math] (непосредственно), [math] 6 [/math] из [math] 3 [/math] (к примеру, через цепочку состояний [math] 3 \rightarrow 2 \rightarrow 4 \rightarrow 6 [/math]) и т.д.
• сообщаются состояния [math] 1 [/math] и [math] 2 [/math] (непосредственно), [math] 6 [/math] и [math] 7 [/math] (непосредственно), [math] 1 [/math] и [math] 3 [/math] (достижимы друг из друга) и т. д.
• неразложимыми классами являются множества вершин [math] \left \{ 1, 2, 3 \right \} [/math], [math] \left \{ 4 \right \} [/math], [math] \left \{ 5 \right \} [/math], [math] \left \{ 6, 7 \right \} [/math];
• эргодическими классами являются множества вершин [math] \left \{ 5 \right \} [/math], [math] \left \{ 6, 7 \right \} [/math];
• поглощающим состоянием является состояние [math] 5 [/math].
• если расматривать [math] \{6, 7\} [/math] отдельно, можно выделить два циклических класса [math] \{6\} [/math] и [math] \{7\} [/math] (на каждом шаге цепь переходит из одного состояния в другое, а через [math] d = 2 [/math] шага возвращается в одно и то же состояние.

Подсчет количества поглощащих состояний

Пусть [math]\mathtt{transition}[/math] — массив переходов марковской цепи, где [math]\mathtt{transition[i][2]}[/math] — вероятность перехода из состояния [math]\mathtt{transition[i][0]}[/math] в [math]\mathtt{transition[i][1]}[/math]. Тогда, по определению поглощающего состояния, если [math]\mathtt{j}[/math] — поглощающее состояние, то [math]\mathtt{transition[j][2] = 1}[/math]. По этому признаку помно определить все поглощающие состояния в цепи.

Псевдокод

• [math]\mathtt{absorbing}: boolean:[\mathtt{n}][/math] — массив состояний. Если [math]i[/math] — посглощающее состояние, то [math]\mathtt{absorbing[i]} = true[/math]
• [math]\mathtt{n}[/math] — количество состояний
• [math]\mathtt{m}[/math] — количество переходов

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

См. также

• Эргодическая марковская цепь
• Регулярная марковская цепь
• Отношение связности, компоненты связности

Источники информации

• Романовский И. В. Дискретный анализ. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 270—279. — ISBN 5-7940-0114-3
• Кемени Дж., Снелл Дж. Конечные цепи Маркова. — М. : Наука, 1970. — 272 c.
• Википедия — Цепь Маркова
• Wikipedia — Absorbing Markov chain