Будущее зависит только от настоящего.

Большая часть процессов в мире зависит от истории. Представь пьяного человека на улице. На каждом шагу он случайно идёт вперёд или назад. Куда он попадёт через час? Это случайное блуждание — простейшая цепь Маркова.

Цепь Маркова — последовательность состояний, где вероятность следующего состояния зависит только от текущего, но не от предыдущих. Это называется марковским свойством. Андрей Марков сформулировал его в 1906 году, изучая чередование гласных и согласных в «Евгении Онегине». Он хотел показать, что закон больших чисел применим к зависимым событиям — не только к независимым1.

Простой пример — погода. Если сегодня солнечно — завтра солнечно с вероятностью 0.8, дождь с вероятностью 0.2. Если сегодня дождь — завтра солнечно с вероятностью 0.4, дождь с вероятностью 0.6.

	солн	дождь
солн	0.8	0.2
дождь	0.4	0.6

Через много шагов цепь достигает стационарного распределения — состояния, где вероятности перестают меняться. Для этой погоды: солнечно 67%, дождь 33% — независимо от того, с чего начали.

Случайное блуждание в двумерном пространстве — это прогулка пьяного. Он всегда вернётся домой. В трёх измерениях — это полёт пьяной птицы. Она потеряется навсегда. — Шизуо Какутани, вариация теоремы Пойа

PageRank — алгоритм, который сделал Google. Интернет как граф: страницы — состояния, ссылки — переходы. Случайный пользователь случайно кликает по ссылкам. PageRank страницы — вероятность оказаться на ней в стационарном распределении этой цепи Маркова. Страница важна, если на неё ссылаются важные страницы. Рекурсивное определение решается через собственные векторы матрицы2.

Цепи Маркова с непрерывным временем описывают радиоактивный распад, очереди в банке, распространение болезней. Скрытые марковские модели — основа распознавания речи в 1990-х. Метод Монте-Карло с марковскими цепями (MCMC) — как обучаются современные байесовские модели и нейросети4.

Самое удивительное свойство — эргодичность. Если из любого состояния можно попасть в любое другое — цепь эргодична. Она «забывает» начальное состояние. Долгосрочное поведение не зависит от того, с чего начали. Только структура переходов определяет судьбу системы.

Пьяный человек на прямой улице рано или поздно вернётся к началу — с вероятностью 1. На двумерной плоскости — тоже. В трёхмерном пространстве — уже нет. Вероятность возврата меньше единицы. Это теорема Пойа (1921)3.

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