Математика

Цепи Маркова

Матрицы переходов, стационарность, поглощение и возврат цепи.

Как выбрать подходящий материал

Матрица переходов задаёт вероятности одного шага. Для нескольких шагов используют её степени, сохраняя принятое направление вектора вероятностей.
Стационарное распределение, поглощение и время возврата отвечают на разные вопросы; существование стационарного вектора ещё не доказывает сходимость к нему.

5 формул

Формулы темы

Распределение цепи Маркова через n шагов: матрица переходов

Распределение конечной однородной цепи после n шагов получается умножением начальной строки вероятностей на степень матрицы переходов. Элементы Pⁿ суммируют вероятности всех траекторий нужной длины между состояниями.

$p_n=p_0P^n,\qquad p_{n+1,j}=\sum_i p_{n,i}P_{ij}$

Стационарное распределение цепи Маркова и условие сходимости

Стационарное распределение сохраняется после одного шага цепи. Для конечной неприводимой цепи оно единственно, но сходимость распределений из любого старта дополнительно требует апериодичности.

$\pi P=\pi,\qquad \sum_i\pi_i=1,\quad \pi_i\ge0$

Фундаментальная матрица поглощения и среднее число шагов

Фундаментальная матрица поглощающей цепи считает ожидаемые посещения переходных состояний до поглощения. Сумма строки даёт среднее число шагов до выхода из временной части цепи, включая возможные повторные визиты.

$N=(I-Q)^{-1}=\sum_{n=0}^{\infty}Q^n,\qquad t=N\mathbf1$

Вероятности конечных исходов поглощающей цепи: B=NR

Матрица B показывает вероятность каждого поглощающего исхода при каждом временном старте. Она получается из фундаментальной матрицы посещений N и блока прямых выходов R; сумма каждой строки B равна 1 при неизбежном поглощении.

$B=(I-Q)^{-1}R=NR,\qquad B=R+QB$

Среднее время первого возвращения: обратная стационарная доля

В конечной неприводимой цепи среднее число шагов до первого возвращения в состояние i равно 1/πᵢ. Самопереход на первом шаге считается возвращением; апериодичность для этого равенства не требуется.

$T_i^+=\min\{n\ge1:X_n=i\},\qquad \mathbb E_iT_i^+=\frac1{\pi_i}$