Марковские цепи

Иногда будущее системы зависит только от того, где она находится сейчас, и совсем не зависит от того, как она туда попала. Такие системы описываются марковскими цепями — и они на удивление мощный инструмент, от прогноза погоды до ранжирования веб-страниц.

Марковская цепь — это математическая модель системы, которая в каждый момент находится в одном из конечного набора состояний и переходит между ними с фиксированными вероятностями. Главное свойство (марковское): вероятность следующего состояния зависит только от текущего состояния, а не от всей предыдущей истории.

Зачем это нужно? Огромное число процессов «не помнит» прошлого: погода завтра зависит в основном от погоды сегодня, страница, на которую перейдёт сёрфер, — от текущей страницы. Марковские цепи позволяют такие процессы аккуратно описать и предсказать их долгосрочное поведение.

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

Пусть у системы есть состояния 0, 1, 2. Поведение задаётся матрицей переходов P, где P[i][j] — вероятность за один шаг перейти из состояния i в состояние j. Каждая строка — это распределение вероятностей выхода из одного состояния, поэтому сумма каждой строки равна 1.

          в 0     в 1     в 2
  из 0 [  0.7     0.2     0.1  ]  сумма = 1
  из 1 [  0.3     0.4     0.3  ]  сумма = 1
  из 2 [  0.2     0.3     0.5  ]  сумма = 1

Возьмём метеорологическую интерпретацию: 0 — солнечно, 1 — облачно, 2 — дождь. Тогда P[0][0] = 0.7 означает «если сегодня солнечно, завтра снова солнечно с вероятностью 0.7», а P[2][0] = 0.2 — «после дождя солнце наступает с вероятностью 0.2».

Марковское свойство

«Будущее зависит только от настоящего» — звучит как ограничение, но это и есть источник простоты. Нам не нужно хранить всю историю: достаточно текущего состояния (или текущего распределения вероятностей по состояниям). Цепь без памяти — как игральная кость, которой всё равно, что выпадало раньше.

Шаг во времени = умножение вектора на матрицу

Состояние знания о системе удобно хранить как вектор вероятностей v, где v[i] — вероятность находиться в состоянии i. Один шаг во времени — это умножение этого вектора на матрицу P: новая вероятность оказаться в j складывается из всех способов туда попасть, v_new[j] = сумма по i от v[i] * P[i][j].

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

P = [[0.7, 0.2, 0.1],
     [0.3, 0.4, 0.3],
     [0.2, 0.3, 0.5]]
v = [1.0, 0.0, 0.0]
for _ in range(50):
    v = [sum(v[i] * P[i][j] for i in range(3)) for j in range(3)]
print("Стационарное распределение:", [round(x, 4) for x in v])
print("Сумма:", round(sum(v), 4))

Вывод:

Стационарное распределение: [0.4565, 0.2826, 0.2609]
Сумма: 1.0

Итог: в долгосрочной перспективе около 45.65% дней солнечные, 28.26% облачные и 26.09% дождливые. Мы стартовали из «точно солнечно» (вектор [1, 0, 0]), но после многих шагов это начальное условие забылось — система пришла в своё устойчивое распределение. Сумма осталась равна 1: вероятности никуда не делись, они лишь перераспределились.

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

Разберём ключевые места.

Внутренний comprehension — это умножение вектор×матрица. Выражение sum(v[i] * P[i][j] for i in range(3)) при фиксированном j перебирает все исходные состояния i и складывает «сколько вероятности перетекает из i в j». Внешний comprehension [... for j in range(3)] делает это для каждого целевого состояния j, собирая новый вектор.

Почему распределение сходится. Если из любого состояния можно (хотя бы за несколько шагов) попасть в любое другое и цепь не «зациклена» строго периодически, она называется эргодической. У эргодической цепи есть единственное стационарное распределение, и итерации к нему сходятся из любого старта. Наша матрица именно такая: все вероятности положительны, перейти можно куда угодно.

Сумма сохраняется. Поскольку каждая строка P суммируется в 1, операция «вектор×матрица» сохраняет суммарную вероятность: стартовали с суммой 1 — на каждом шаге сумма остаётся 1. Если в выводе сумма «уплыла», значит, в матрице ошибка — строка не суммируется в единицу.

Геометрически шаги сходятся к одной точке так:

старт [1.00, 0.00, 0.00]
шаг 1 [0.70, 0.20, 0.10]
шаг 2 [0.55, 0.25, 0.20]
 ...        сходится
предел [0.4565, 0.2826, 0.2609]  <-- стационарное

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

Перепутать направление в P[i][j]. Здесь i — откуда, j — куда. Если случайно транспонировать матрицу, получится цепь с другими переходами и неверным результатом.
Строки не суммируются в 1. Каждая строка — распределение вероятностей выхода из состояния. Если сумма не равна 1, вероятность будет «утекать» или «возникать из ниоткуда».
Ждать, что старт повлияет на предел. Для эргодической цепи стационарное распределение одно и то же из любого начального вектора. Старт влияет лишь на скорость сходимости, а не на предел.
Считать слишком мало шагов. Для одних матриц хватает 5 итераций, для других нужны десятки. Если результат ещё «дрожит», увеличьте число шагов.
Забыть про марковское свойство. Если реальный процесс зависит от двух последних состояний, обычная цепь его не опишет — нужно расширять пространство состояний.

Итоги

Марковская цепь — система из конечного набора состояний с фиксированными вероятностями переходов между ними.
Марковское свойство: будущее зависит только от текущего состояния, а не от всей истории — поэтому хранить нужно лишь «настоящее».
Поведение задаётся матрицей переходов P, где P[i][j] — вероятность перейти из i в j, а каждая строка суммируется в 1.
Один шаг во времени — это умножение вектора вероятностей на матрицу; повторяя его, мы прокручиваем цепь вперёд.
У эргодической цепи итерации сходятся к стационарному распределению, единому для любого старта — оно и описывает долгосрочное поведение системы.