Уравнения Чепмена-Колмогорова: как связаны переходы

Если процесс «забывает» свою историю и зависит только от текущего состояния, то вероятность попасть из одного состояния в другое за много шагов можно собрать из вероятностей более коротких переходов. Именно это утверждают уравнения Чепмена-Колмогорова - фундаментальное соотношение теории марковских процессов, которое связывает переход за $n + m$ шагов с переходами за $n$ и $m$ шагов через суммирование по всем промежуточным состояниям. Ниже разберём дискретную и непрерывную формы, их вывод из марковского свойства, связь с возведением матрицы переходов в степень и переход к стационарному распределению. В калькуляторе ниже можно покрутить вероятности перехода и увидеть, как $n$-шаговые вероятности сходятся к предельному распределению.

Марковское свойство как отправная точка

Уравнения Чепмена-Колмогорова существуют не сами по себе - они вытекают из марковского свойства (свойства отсутствия последействия). Случайный процесс $\{X_t\}$ марковский, если будущее зависит от прошлого только через настоящее:

$P(X_{n+1} = j \mid X_n = i,\ X_{n-1}, \dots, X_0) = P(X_{n+1} = j \mid X_n = i).$

Иными словами, чтобы предсказать следующее состояние, достаточно знать текущее; вся предыстория несущественна. Это и есть та «потеря памяти», которая делает возможным разбиение длинного перехода на части - процесс в промежуточный момент не помнит, как он туда попал, поэтому дальнейшее движение зависит только от того, где он оказался. Если вы только знакомитесь с тем, как устроены вероятности совместных событий, полезно сначала посмотреть совместное распределение двух случайных величин, а уже потом возвращаться к цепям.

Дискретная форма уравнения Чепмена-Колмогорова

Обозначим $p_{ij}^{(n)} = P(X_n = j \mid X_0 = i)$ - вероятность перейти из состояния $i$ в состояние $j$ ровно за $n$ шагов. Тогда для любого разбиения $n + m$ на два слагаемых выполняется дискретное уравнение Чепмена-Колмогорова:

$p_{ij}^{(n+m)} = \sum_{k} p_{ik}^{(n)}\, p_{kj}^{(m)}.$

Смысл прозрачен: чтобы попасть из $i$ в $j$ за $n + m$ шагов, процесс за первые $n$ шагов должен оказаться в каком-то промежуточном состоянии $k$, а за оставшиеся $m$ шагов - добраться из $k$ в $j$. Поскольку промежуточное состояние может быть любым, мы перебираем все варианты $k$ и складываем вероятности. Произведение $p_{ik}^{(n)}\,p_{kj}^{(m)}$ корректно именно из-за марковского свойства: попав в $k$, процесс «не помнит» путь $i \to k$, поэтому вероятности независимо умножаются.

Рассчитать для своей задачи

Связь с матрицей переходов и её степенями

Удобнее всего записать уравнение в матричной форме. Соберём одношаговые вероятности $p_{ij} = p_{ij}^{(1)}$ в матрицу переходов $P$, где строка $i$ - это распределение вероятностей следующего состояния при старте из $i$. Каждая строка стохастическая: её элементы неотрицательны и в сумме дают единицу. Тогда $n$-шаговая матрица - это просто $n$-я степень:

$P^{(n)} = P^n.$

Уравнение Чепмена-Колмогорова при такой записи превращается в тождество для умножения матриц:

$P^{(n+m)} = P^{(n)} \cdot P^{(m)} = P^n \cdot P^m = P^{n+m}.$

То есть сумма $\sum_k p_{ik}^{(n)} p_{kj}^{(m)}$ - это в точности элемент $(i, j)$ произведения матриц $P^n P^m$. Поэтому на практике для конечной цепи $n$-шаговые вероятности находят не суммированием по путям, а возведением одной матрицы в степень - численно это намного дешевле. Логика степеней матрицы здесь та же, что в задачах на случайные величины и их функции распределения, только объект - матрица, а не одно число.

Непрерывная форма: процессы с непрерывным временем

Если время течёт непрерывно, переход описывается не степенью матрицы, а переходной функцией $p_{ij}(t) = P(X_{s+t} = j \mid X_s = i)$ (для однородного процесса она не зависит от $s$). Уравнение Чепмена-Колмогорова принимает вид:

$p_{ij}(t + s) = \sum_{k} p_{ik}(t)\, p_{kj}(s).$

Для непрерывного пространства состояний сумма заменяется интегралом по плотностям переходных вероятностей:

$p(x, t + s \mid y) = \int p(x, t \mid z)\, p(z, s \mid y)\, dz.$

Из этого функционального уравнения дифференцированием по времени выводят прямое и обратное уравнения Колмогорова - дифференциальные уравнения, которым подчиняется $p_{ij}(t)$. Они описывают, например, диффузию (уравнение Фоккера-Планка как частный случай), очереди, химическую кинетику и популяционную динамику. Уравнение Чепмена-Колмогорова здесь играет роль «закона согласованности»: семейство переходных вероятностей должно склеиваться по времени без противоречий.

Рассчитать для своей задачи

Стационарное распределение как предел

Чаще всего уравнения Чепмена-Колмогорова применяют, чтобы понять долгосрочное поведение цепи. Для эргодической (неприводимой апериодической) цепи $n$-шаговые вероятности перестают зависеть от стартового состояния:

$\lim_{n \to \infty} p_{ij}^{(n)} = \pi_j,$

где $\pi = (\pi_1, \pi_2, \dots)$ - стационарное распределение. Оно находится как решение системы

$\pi P = \pi, \qquad \sum_j \pi_j = 1.$

Стационарное распределение - это собственный вектор матрицы переходов с собственным значением $1$, нормированный к сумме единиц. Содержательно $\pi_j$ - доля времени, которую цепь в среднем проводит в состоянии $j$ на длинном горизонте. Именно к этому пределу сходятся строки $P^n$ при росте $n$, что хорошо видно в калькуляторе выше: чем больше шагов, тем ближе любая строка $n$-шаговой матрицы к одному и тому же вектору $\pi$.

Где это работает: примеры применения

Уравнения Чепмена-Колмогорова - не абстракция, а рабочий инструмент. В алгоритме PageRank веб-граф моделируется марковской цепью, а стационарное распределение задаёт «вес» страниц. В теории очередей переходная функция описывает число заявок в системе. В биоинформатике скрытые марковские модели опираются на $n$-шаговые переходы при выравнивании последовательностей. В финансах кредитные рейтинги моделируют матрицей миграций, а уравнение Чепмена-Колмогорова даёт вероятность дефолта за несколько лет из годовой матрицы. Во всех случаях ключевой трюк один: длинный горизонт собирается из коротких переходов через суммирование по промежуточным состояниям.

Особенно показателен сценарий с кредитными миграциями. Пусть дана годовая матрица $P$ переходов между рейтингами (AAA, AA, …, дефолт). Чтобы оценить вероятность дефолта за три года, не нужно строить отдельную трёхлетнюю модель: достаточно посчитать $P^3$ и взять нужный элемент столбца «дефолт». Уравнение Чепмена-Колмогорова гарантирует, что $P^3 = P \cdot P \cdot P$ корректно описывает трёхлетний переход - при условии, что миграции рейтингов обладают марковским свойством (вероятность будущего рейтинга зависит только от текущего, а не от всей кредитной истории). Это допущение и его нарушения - отдельная тема при валидации риск-моделей, но именно уравнение Чепмена-Колмогорова делает такой пересчёт законным.

Частые ошибки

• Путают $p_{ij}^{(n)}$ и $(p_{ij})^n$. $n$-шаговая вероятность - это элемент матрицы $P^n$, а не $n$-я степень одного числа $p_{ij}$. Возводить в степень нужно всю матрицу.
• Забывают марковское свойство. Без отсутствия последействия произведение $p_{ik}^{(n)} p_{kj}^{(m)}$ некорректно: в немарковском процессе путь до $k$ влияет на дальнейшее движение, и просто перемножать нельзя.
• Теряют стохастичность. После арифметических ошибок строки $P^n$ не суммируются к единице. Это сигнал, что в расчёте опечатка, а не свойство цепи.
• Считают стационарным любой предел. Стационарное распределение существует и единственно только для эргодической цепи; у периодической или приводимой цепи строки $P^n$ могут не сходиться.
• Смешивают строки и столбцы. В записи $\pi P = \pi$ распределение $\pi$ - строка, и умножается слева. Перепутав на $P\pi$, получают неверную систему.

FAQ

Чем уравнение Чепмена-Колмогорова отличается от уравнений Колмогорова? Уравнение Чепмена-Колмогорова - это интегральное (или матричное) соотношение согласованности переходных вероятностей по времени. Прямое и обратное уравнения Колмогорова - это дифференциальные уравнения для $p_{ij}(t)$, которые получаются из уравнения Чепмена-Колмогорова дифференцированием в непрерывном времени.

Зачем нужно суммирование по всем промежуточным состояниям? Промежуточное состояние $k$ - это «развилка»: процесс может оказаться в любом из них. События «прошёл через $k_1$» и «прошёл через $k_2$» несовместны, поэтому полная вероятность перехода - это сумма по всем возможным $k$ (формула полной вероятности применённая к марковскому шагу).

Всегда ли $P^n$ сходится к стационарному распределению? Нет. Сходимость строк $P^n$ к одному вектору $\pi$ гарантирована для конечной неприводимой апериодической (эргодической) цепи. У периодической цепи (например, переходы строго туда-обратно) степени осциллируют и предела в обычном смысле нет, хотя стационарное распределение как решение $\pi P = \pi$ всё равно может существовать.

Коротко

Уравнения Чепмена-Колмогорова связывают переход за $n + m$ шагов с переходами за $n$ и $m$ шагов: $p_{ij}^{(n+m)} = \sum_k p_{ik}^{(n)} p_{kj}^{(m)}$, а в непрерывном времени сумма становится интегралом. Опираются они на марковское свойство, в матричной форме сводятся к $P^{(n)} = P^n$, а в пределе дают стационарное распределение $\pi$, к которому сходятся строки $P^n$ для эргодической цепи.