Математика / Вероятность и статистика

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

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

Опубликовано: 28 октября 2026 г.Обновлено: 28 октября 2026 г.

Формула

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

Схема Два пути к состоянию B за два шага

Отдельные маршруты A→A→B и A→B→B дают 3/16 и 2/16; их сумма 5/16.

Обозначения

$Pᵢⱼ$: вероятность следующего состояния j при текущем i, безразмерная
$p₀$: строка начального распределения, безразмерная
$pₙ$: строка распределения после n переходов, безразмерная
$n$: неотрицательное целое число переходов, шаг
$(Pⁿ)ᵢⱼ$: n-шаговая вероятность перехода из i в j, безразмерная

Условия применения

Число состояний конечно, матрица P не меняется во времени и имеет неотрицательные элементы с единичными суммами строк. Будущее условное распределение зависит только от текущего состояния. Здесь распределения записываются строками, а n является целым числом шагов.

Ограничения

Марковское свойство и однородность являются предположениями модели, а не следствием наличия таблицы наблюдений. Для меняющихся матриц используют упорядоченное произведение P₀P₁… вместо одной степени. Число переходов нельзя автоматически считать физическим временем без определения длительности шага.

Подробное объяснение

По формуле полной вероятности шанс оказаться в j на следующем шаге равен сумме по всем текущим состояниям i: pᵢPᵢⱼ. Множитель pᵢ отвечает за попадание в i, а Pᵢⱼ — за последующий переход. Независимость соседних состояний для этого не требуется: используются условные вероятности.

После двух переходов(P²)ᵢⱼ=∑ₖPᵢₖPₖⱼ. Каждый индекс k обозначает промежуточное состояние; произведение описывает путь i→k→j, а сумма объединяет взаимоисключающие пути. Повторение аргумента даёт Pⁿ и затем p₀Pⁿ для случайного старта.

Сумма координат после умножения остаётся 1: ∑ⱼ∑ᵢpᵢPᵢⱼ=∑ᵢpᵢ·1. Неотрицательность тоже сохраняется. Это полезные проверки арифметики, но они не доказывают соответствие модели реальным наблюдениям. Другая неверная стохастическая матрица также прошла бы проверку нормировки.

При n=0 используется единичная матрица P⁰=I, и распределение остаётся исходным. Для больших n последовательное умножение строки на P часто проще вычисления полной матрицы Pⁿ. Сходимость при n→∞ — отдельная задача: конечность и нормировка сами по себе её не обеспечивают.

Как пользоваться формулой

Зафиксируйте порядок состояний и заполните строки условными вероятностями выхода; проверьте сумму каждой строки и неотрицательность.
Запишите начальную строку p₀ в том же порядке; для известного начального состояния поставьте 1 на его месте и нули на остальных.
Умножайте строку справа на P требуемое число раз или вычислите Pⁿ; сохраняйте дроби до окончательного представления ответа.
Проверьте сумму и диапазон координат, затем назовите событие и число переходов; не выдавайте распределение за единственную траекторию.

Историческая справка

Конечные цепи Маркова сформировали матричный язык зависимых последовательных испытаний. Название связано с А. А. Марковым, но вычисление n-шаговых вероятностей является частью последующего систематического развития теории. Смысл матричного произведения здесь совпадает с правилом полной вероятности.

Книга Kemeny и Snell «Finite Markov Chains» первоначально вышла в 1960 году; издание Springer1976 года содержит дополнительное приложение. Такая учебная традиция закрепила удобное разделение матрицы переходов, начального распределения и длительности прогноза.

В версии «Introduction to Probability» Grinstead и Snell, опубликованной проектом CHANCE, введению в цепи посвящена отдельная глава 11. Наглядные конечные примеры показывают, как переход от перечисления маршрутов к степеням матриц сокращает вычисления. Современный компьютер ускоряет умножение, но не изменяет вероятностный смысл индексов.

Историческая линия формулы

Теория названа в честь А. А. Маркова. Степень матрицы переходов представляет правило суммирования вероятностей последовательных путей; современная строковая запись относится к общей матричной традиции и не объявляется самостоятельным открытием авторов выбранного учебника.

Пример

Рассмотрим P=((3/4,1/4),(1/2,1/2)) для состояний A,B и старт p₀=(1,0). После шага p₁=(3/4,1/4). После двух шагов p₂,A=(3/4)(3/4)+(1/4)(1/2)=9/16+2/16=11/16; p₂,B=3/16+2/16=5/16. Третий шаг даёт p₃,A=(11/16)(3/4)+(5/16)(1/2)=33/64+10/64=43/64, p₃,B=21/64. Суммы равны 1. Независимо вероятность B через два шага можно получить по двум маршрутам A→A→B и A→B→B: их вероятности 3/16 и 1/8 дают 5/16. Наиболее вероятный путь A→A→A сам по себе не заменяет полного расчёта. Дроби 11/16 и 5/16 описывают состояние через два перехода, а не вероятность первого посещения этих состояний.

Частая ошибка

Не умножайте P на строку слева как на столбец без смены соглашения. Не возводите отдельные элементы P в степень вместо матричного произведения. Не заменяйте сумму маршрутов одним самым вероятным. Не считайте P⁰ нулевой матрицей и не теряйте порядок разных P при неоднородной модели.

Практика

Задачи с решением

Случайный старт

Условие. Для той же P возьмите p₀=(1/2,1/2). Найдите p₁.

Решение. p₁,A=(1/2)(3/4)+(1/2)(1/2)=5/8; p₁,B=1/8+1/4=3/8.

Ответ. (5/8,3/8).

Чередование

Условие. P=((0,1),(1,0)), p₀=(1,0). Найдите p₂ и p₃.

Решение. P²=I. После чётного числа шагов распределение исходное, после нечётного —(0,1).

Ответ. p₂=(1,0); p₃=(0,1).

Дополнительные источники

https://math.dartmouth.edu/~prob/prob/prob.pdf
https://link.springer.com/book/9780387901923

Связанные формулы

Математика

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

$\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$

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

Математика

Формула Байеса для условных вероятностей

$P(H_k\mid A)=\frac{P(H_k)P(A\mid H_k)}{\sum_iP(H_i)P(A\mid H_i)}$

Формула «Формула Байеса для условных вероятностей» задает численную характеристику вероятностной модели. Она переводит исходы, вероятности или наблюдения в показатель, который удобно считать, сравнивать и проверять.