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

Формально — марковское свойство: P(Xₙ₊₁ = s | X₀, X₁, …, Xₙ) = P(Xₙ₊₁ = s | Xₙ).

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

Матрица переходов P: Pᵢⱼ = P(Xₙ₊₁ = j | Xₙ = i). Каждая строка суммируется в 1. Для погоды: солн→солн 0.8, солн→дождь 0.2, дождь→солн 0.4, дождь→дождь 0.6.

Стационарное распределение π2: π = πP, где π₁ + π₂ + … = 1. Распределение при котором цепь «успокаивается». Для погодной цепи: π = (0.667, 0.333). 67% времени солнечно — независимо от начального состояния.

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

PageRank3 — цепь Маркова на графе интернета. Страницы = состояния. Ссылки = переходы. Случайный пользователь кликает по ссылкам. PageRank = стационарное распределение этой цепи. Важная страница = страница где пользователь проводит больше всего времени в пределе.

MCMC (Markov Chain Monte Carlo)4: хочешь сэмплировать из сложного распределения π — построй цепь Маркова со стационарным распределением π. Запусти цепь достаточно долго. Состояния цепи = сэмплы из π. Это основа байесовского вывода и обучения нейросетей.

Случайное блуждание — простейшая цепь. На прямой: шаг вправо или влево с вероятностью 0.5. Теорема Пойа: в 1D и 2D блуждание возвращается в начало с вероятностью 1. В 3D и выше — не обязательно.