Что мы строим и зачем: цепь Маркова на трёх состояниях
Цепь Маркова описывает систему, которая переходит из состояния в состояние, и при известном текущем состоянии прошлое не влияет на прогноз следующего шага. Это марковское свойство, оно же отсутствие памяти у цепи первого порядка. Практический разбор на Towards Data Science формулирует правило коротко: дано текущее состояние, история нерелевантна.
Дальше идёт код, который можно запустить: матрица переходов на NumPy, вероятности на n дней вперёд через уравнение Чепмена-Колмогорова, стационарное распределение и график сходимости за 20 дней на Matplotlib. В конце разберём, где модель врёт, даже когда матрица сходится.
Пример учебный. Берём писателя и каждый день относим к одному из трёх взаимоисключающих состояний: Drafting (D), активное написание текста; Revising (R), правка и улучшение готового; Distracted (X), всё остальное, кроме работы над статьёй. Вероятности взяты из разбора в источнике, а не из исследования писательских привычек. Психологической точности здесь нет и не планируется: важна арифметика, которую легко перепроверить.
Матрица переходов: как задать и проверить стохастическую матрицу в NumPy
Элемент P[i][j] задаёт вероятность перейти из состояния i в состояние j за один день. Каждая строка матрицы задаёт распределение вероятностей: все значения неотрицательны, сумма равна единице. Строки соответствуют сегодняшнему состоянию, столбцы завтрашнему.
| Сегодня | Drafting завтра | Revising завтра | Distracted завтра | Сумма |
|---|---|---|---|---|
| Drafting | 0.6 | 0.3 | 0.1 | 1.0 |
| Revising | 0.3 | 0.5 | 0.2 | 1.0 |
| Distracted | 0.2 | 0.4 | 0.4 | 1.0 |
Числа в таблице те же, что в исходном примере: из Drafting писатель остаётся в Drafting с вероятностью 0.6, уходит в Revising с 0.3 и отвлекается с 0.1.
Один факт из таблицы полезно проговорить отдельно: если сегодня состояние Distracted, суммарная вероятность вернуться к работе завтра (Drafting или Revising) составляет 0.6. Провал в отвлечение не приговор, однако возвращение не гарантировано: 40% дней остаются в Distracted.
import numpy as np
states = ['Drafting', 'Revising', 'Distracted']
P = np.array([
[0.6, 0.3, 0.1], # из Drafting
[0.3, 0.5, 0.2], # из Revising
[0.2, 0.4, 0.4], # из Distracted
])
print(P.shape) # (3, 3)
print(P.sum(axis=1)) # [1. 1. 1.]
Порядок состояний фиксируйте один раз и явно, списком states. Половина ошибок в таких моделях возникает не из-за математики, а из-за того, что в коде строки означают одно, а в таблице из статьи другое.
В матрице 9 ячеек, независимы из них только 6: три ограничения на сумму строк убирают по одной степени свободы в каждой строке.
Проверка стохастичности: сумма строк, неотрицательность, типичные ошибки
Валидация занимает две строки и экономит часы отладки:
assert (P >= 0).all(), 'есть отрицательные вероятности'
assert np.allclose(P.sum(axis=1), 1.0), 'строки не нормированы'
Сравнение идёт через np.allclose, а не через ==: 0.1 + 0.2 + 0.7 в float64 не даст ровно 1.0. Разница обычно порядка 1e-16, но проверка на равенство её поймает и остановит расчёт.
Главная ошибка при переносе таблицы вероятностей в код: нормировка столбцов вместо строк. Если считать частоты вида «какая доля дней в Drafting пришла из Distracted», получится столбцово-стохастическая матрица, и все дальнейшие степени будут считать другую модель. Вторая по частоте ошибка: сумма строки 0.9 или 1.1 после ручного ввода чисел. 0.9 означает, что 10% случаев потерялись, и цепь будет тихо терять вероятность на каждом шаге. 1.1 означает, что распределение не нормировано и вероятности за n шагов разъедутся ещё сильнее.
Многошаговые вероятности: уравнение Чепмена-Колмогорова и возведение матрицы в степень
Уравнение Чепмена-Колмогорова в матричной форме выглядит скучно и работает безотказно: вероятности переходов за n шагов задаёт P^n. Интуиция простая. Чтобы попасть из i в j за два дня, нужно пройти через какое-то промежуточное состояние k, и вероятности по всем k складываются: (P^2)[i][j] = sum_k P[i][k] * P[k][j]. Ровно это делает обычное перемножение матриц.
В NumPy степень матрицы считается не поэлементно, а через np.linalg.matrix_power:
start = np.array([1.0, 0.0, 0.0]) # день 0: писатель в Drafting
for n in (1, 2, 5, 20):
print(n, start @ np.linalg.matrix_power(P, n))
Порядок умножения важен. Вектор начального распределения в NumPy удобно хранить строкой и умножать справа: start @ P. Если состояния лежат в столбце, формула меняется на P.T @ start. Путаница строк и столбцов даёт правдоподобные, но неверные числа, и заметить это по графику почти невозможно.
| День | Drafting | Revising | Distracted |
|---|---|---|---|
| 0 | 1.000 | 0.000 | 0.000 |
| 1 | 0.600 | 0.300 | 0.100 |
| 2 | 0.470 | 0.370 | 0.160 |
| 3 | 0.425 | 0.390 | 0.185 |
| 4 | 0.409 | 0.397 | 0.195 |
| 5 | 0.403 | 0.399 | 0.198 |
| 10 | 0.400 | 0.400 | 0.200 |
| 20 | 0.400 | 0.400 | 0.200 |
Расхождение со стационаром падает быстро: к пятому дню максимальное отклонение от предельного вектора около 0.003, к восьмому ниже 0.001. Числа получены умножением этой матрицы, их можно перепроверить тем же скриптом. Суммы строк местами дают 1.001 из-за округления до трёх знаков, в расчёте хранятся полные значения float64.
Стационарное распределение и визуализация сходимости за 20 дней
Стационарное распределение π задаётся условием π @ P = π при сумме компонент, равной единице. Смысл: попали в него, и дальше распределение по состояниям не меняется. Для сходящейся цепи строки P^n при больших n становятся одинаковыми и равны π, поэтому предел не зависит от стартового состояния.
Способ первый, итерации:
pi = np.array([1/3, 1/3, 1/3])
for _ in range(200):
pi = pi @ P
print(pi) # [0.4 0.4 0.2]
print(pi @ P) # [0.4 0.4 0.2]
Способ второй, собственный вектор. Ищем собственное значение 1 у транспонированной матрицы:
vals, vecs = np.linalg.eig(P.T)
idx = np.argmin(np.abs(vals - 1.0))
pi = np.real(vecs[:, idx])
pi = pi / pi.sum()
print(pi) # [0.4 0.4 0.2]
Два подводных камня в способе с eig. Собственный вектор определён с точностью до множителя и может прийти с отрицательным знаком, поэтому нужна нормировка на сумму. Для несимметричных матриц NumPy возвращает комплексные числа, отсюда np.real.
Ответ для нашего примера: 0.4 дня в Drafting, 0.4 в Revising, 0.2 в Distracted. Проверка np.allclose(pi @ P, pi) проходит. Трактовка: в долгом горизонте писатель тратит 40% дней на написание, 40% на правки и 20% на отвлечения, стартовое состояние на это не влияет.
Скорость сходимости задаёт второе по модулю собственное значение. Здесь они равны 1, 0.362 и 0.138. Субдоминанта 0.362 означает, что отклонение от стационара на каждом шаге уменьшается примерно в 2.8 раза, и за десяток дней цепь практически неотличима от предела.
График на Matplotlib:
import matplotlib.pyplot as plt
days = 21
dist = np.zeros((days, 3))
dist[0] = start
for d in range(1, days):
dist[d] = dist[d - 1] @ P
fig, ax = plt.subplots(figsize=(8, 4.5))
for i, name in enumerate(states):
ax.plot(range(days), dist[:, i], marker='o', label=name)
ax.axhline(0.4, linestyle='--', linewidth=0.8, color='gray')
ax.set_xlabel('День')
ax.set_ylabel('Вероятность состояния')
ax.set_title('Сходимость цепи Маркова за 20 дней')
ax.legend()
ax.grid(alpha=0.3)
plt.tight_layout()
plt.show()
Массив dist хранит распределение по каждому дню, поэтому один и тот же расчёт годится и для графика, и для таблицы выше. Пунктир на уровне 0.4 показывает, что две верхние линии упираются в одну и ту же асимптоту, а Distracted стабилизируется на 0.2.
Свойства цепи, от которых зависит сходимость
Сходимость к единственному стационарному распределению не бесплатна. Нужны условия, и каждое из них ломается на практике.
Однородность по времени. Матрица P одна и та же на всех шагах. У живого автора привычки дрейфуют: в дедлайн вероятность отвлечься падает, при выгорании растёт. Тогда нужна неоднородная цепь с отдельными матрицами по фазам проекта, и «стационарного» распределения в обычном смысле у неё уже нет.
Неприводимость. Из любого состояния достижимо любое другое за конечное число шагов. В нашем примере условие выполняется: из Distracted есть путь в Drafting с вероятностью 0.2. Замените 0.2 и 0.4 на нули, и Distracted станет ловушкой: цепь будет описывать автора, который отвлёкся один раз и больше не пишет.
Апериодичность. Цепь не ходит по жёсткому циклу. Проверка простая: если обнулить диагональ и получить строгое чередование, предела не будет. Матрица [[0,1],[1,0]] для двух состояний даёт распределения 1/0, затем 0/1, затем снова 1/0: средние по времени существуют, предела нет.
Поглощающие состояния. Строка с единицей на диагонали и нулями в остальных ячейках. Вероятность выйти из такого состояния равна нулю, цепь залипает. Если поглощающее состояние одно, стационарное распределение вырождается в точку. Если их несколько, предельный вектор зависит от старта, и единственного ответа не существует.
| Свойство | Как проверить | Что ломается при нарушении |
|---|---|---|
| Однородность по времени | одна матрица на все шаги | предел зависит от номера шага, стационарного распределения нет |
| Неприводимость | граф переходов сильно связен | часть состояний недостижима, предел зависит от старта |
| Апериодичность | нет цикла с жёстким периодом | распределение колеблется, предела не существует |
| Отсутствие поглощения | нет строки вида [0, 0, 1] | цепь залипает, стационарный вектор вырожден |
Где марковское свойство ломается: зависимость от предыдущего дня
Марковское свойство это допущение, а не свойство реальности. Проверяется оно просто: вероятность перейти в Revising завтра равна 0.3 при сегодняшнем Drafting, и число не должно меняться от того, чем был вчерашний день. Если после вчерашнего Distracted та же вероятность падает до 0.2, а после вчерашнего Revising растёт до 0.4, цепь первого порядка описывает процесс неверно, и никакая аккуратная матрица этого не исправит.
Выход первый: повысить порядок. Состоянием становится пара последовательных дней, тогда 3 состояния превращаются в 9 пар вида (вчера, сегодня), а матрица в 9 на 9. Плата: 81 ячейка вместо 9 и до 72 свободных параметров, которые по короткому ряду наблюдений надёжно не оценить. На практике большинство ячеек останется нулевыми, потому что из пары (D, R) можно перейти только в (R, D), (R, R) или (R, X).
Выход второй: переопределить состояния так, чтобы память встроилась в само состояние. Вместо одного Drafting появляются «Drafting сразу после перерыва» и «Drafting в потоке», и цепь снова становится первого порядка, только состояний уже четыре или пять. Это дешевле по числу параметров и обычно понятнее по смыслу, но требует явно решить, какие различия важны для задачи.
Третий вариант, скрытые состояния, когда наблюдаемая метка дня считается следствием ненаблюдаемого режима: скрытые марковские модели. Подход мощнее и заметно тяжелее в оценке, а для 20-30 дней наблюдений почти всегда избыточен.
Математическая корректность ≠ адекватность модели
Стохастическая матрица может быть безупречной и при этом описывать плохую модель. Проверки из раздела про валидацию отвечают только на вопрос «можно ли это считать»: суммы строк, неотрицательность, сходимость. На вопрос «стоит ли этому верить» они не отвечают.
Типичные способы испортить модель при корректной матрице:
- состояния пересекаются или слишком грубые: «работает» и «пишет» это разные вещи, и день легко попадает в обе категории;
- вероятности взяты из головы, а не из последовательности наблюдений;
- марковское свойство не проверено, хотя данные намекают на зависимость от вчерашнего дня;
- матрица меняется со временем, а модель считает её постоянной;
- результат никак не сопоставлен с реальностью: 0.4 и 0.2 выглядят красиво, но проверить их нечем.
Практический порядок действий обратный тому, как обычно пишут туториалы. Сначала набирается последовательность меток по дням, хотя бы несколько десятков. Затем по частотам переходов оценивается матрица, с поправкой на нулевые счётчики, чтобы редкие переходы не обнулялись. Потом проверяются условия сходимости и считается P^n. Код занимает двадцать строк, а основное время уходит на выбор состояний и сбор данных.
И последнее. Автор разбора замечает, что возможность описать процесс цепью Маркова ещё не означает, что описывать его так стоит. Матрица переходов удобна, когда состояний мало, переходы однородны и память действительно не нужна. Если процесс держится на истории, полезнее потратить время на переопределение состояний, чем на подгонку вероятностей под модель, которая их не описывает.