Цепи Маркова и стационарное распределение

Моделируем системы, где будущее зависит только от настоящего, и находим их долгосрочное равновесие.

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

Погода (солнечно/дождливо), статус игрока, поведение пользователя на сайте — всё это часто моделируют цепями Маркова. Их главное свойство — «отсутствие памяти»: чтобы предсказать завтра, достаточно знать сегодня. У многих таких систем есть удивительное долгосрочное равновесие — стационарное распределение, которое мы найдём численно. Цепи Маркова — одна из самых прикладных моделей во всей теории вероятностей. Алгоритм PageRank, благодаря которому Google ранжирует страницы, — это, по сути, поиск стационарного распределения гигантской цепи Маркова, где состояния это веб-страницы, а переходы — ссылки. Системы прогноза текста и старые модели распознавания речи опираются на марковские переходы между словами и звуками. В биоинформатике цепями Маркова моделируют последовательности ДНК, в экономике — смену фаз делового цикла. Объединяет все эти применения одно свойство «отсутствия памяти»: достаточно знать текущее состояние, чтобы предсказывать будущее, а долгосрочное поведение системы описывается единственным равновесным распределением.

Матрица переходов

Цепь задаётся вероятностями перехода между состояниями. Пусть погода бывает «солнечно» (С) и «дождливо» (Д), и

$$P(\text{С}\to\text{С})=0{,}8,\ P(\text{С}\to\text{Д})=0{,}2,\ P(\text{Д}\to\text{С})=0{,}4,\ P(\text{Д}\to\text{Д})=0{,}6.$$

Каждая строка матрицы переходов в сумме даёт 1 — из любого состояния система обязательно куда-то перейдёт. Вопрос: какую долю дней в долгосрочной перспективе будет солнечно, независимо от сегодняшней погоды?

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

Стационарное распределение $\pi=(\pi_C,\pi_D)$ — это то, что не меняется при шаге цепи: $\pi P=\pi$. Для нашей погоды система уравнений

$$\pi_C=0{,}8\,\pi_C+0{,}4\,\pi_D,\qquad \pi_C+\pi_D=1$$

даёт $\pi_C=\frac{2}{3}\approx 0{,}6667$ и $\pi_D=\frac{1}{3}$. То есть в среднем две трети дней солнечны. Найдём это число симуляцией, прогнав цепь много шагов и посчитав долю солнечных дней.

import random
random.seed(43)

P = {"C": {"C": 0.8, "D": 0.2}, "D": {"C": 0.4, "D": 0.6}}

state = "D"           # стартуем с дождя — стационар не зависит от старта
steps = 2000000
sunny = 0
for _ in range(steps):
    probs = P[state]
    state = "C" if random.random() < probs["C"] else "D"
    if state == "C":
        sunny += 1
print("Доля солнечных дней:", round(sunny / steps, 4))
print("Теория 2/3:        ", round(2/3, 4))

Вывод:

Доля солнечных дней: 0.6669
Теория 2/3:         0.6667

Несмотря на старт с дождливого дня, доля солнечных дней сошлась к $\frac{2}{3}$ — система «забыла» начало и пришла к равновесию.

Эргодичность: почему старт не важен

Для «хороших» цепей (где из любого состояния достижимо любое и нет жёсткой периодичности) стационарное распределение единственно, и долгосрочные доли времени в состояниях не зависят от того, откуда мы стартовали. Это свойство называют эргодичностью; именно оно делает симуляцию надёжным способом найти $\pi$.

Как работает под капотом

На каждом шаге код смотрит на текущее состояние, берёт его строку вероятностей и разыгрывает следующее состояние одним сравнением random.random() < probs["C"]. Накопленная доля шагов в состоянии «солнечно» по закону больших чисел сходится к стационарной вероятности $\pi_C$. Мы не решаем систему уравнений в коде — равновесие возникает само из многократного применения правил перехода. Это численный аналог решения $\pi P=\pi$, и потому результаты совпадают.

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

Первая ошибка — думать, что стационарное распределение зависит от стартового состояния: для эргодических цепей не зависит. Вторая — путать вероятность перехода $P(\text{С}\to\text{Д})$ со стационарной долей $\pi_D$: это разные вещи, одна про шаг, другая про долгосрочный итог. Третья — забыть, что строки матрицы переходов обязаны суммироваться в 1; иначе это не вероятности и цепь некорректна.

Итог

В цепи Маркова будущее зависит только от текущего состояния.
Стационарное распределение $\pi$ удовлетворяет $\pi P=\pi$.
Для эргодических цепей долгосрочные доли не зависят от старта.
Симуляция находит $\pi$ как доли времени в состояниях.