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

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

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

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

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

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

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

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

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

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

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

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

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

Если эргодический класс состоит из одного состояния, такое состояние называется поглощающим (absorbing).

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

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

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

Пусть [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].

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

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

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

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

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

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

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

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

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

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

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

Пример

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

На рисунке:

• достижимыми состояниями являются: [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] — массив состояний. Если i — посглощающее состояние absorbing[i] = true
• [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

Литература

• И.В. Романовский «Дискретный анализ». 3-е изд., 2003. стр. 270—279
• Дж. Кемени, Дж. Снелл "Конечные цепи Маркова"
• Википедия — Цепь Маркова
• Wikipedia — Absorbing Markov chain