Цепи Маркова с дискретным временем

Цепь Маркова — стохастический процесс без памяти: будущее зависит только от настоящего, не от прошлого. Это мощная модель для систем с «состояниями»: очереди, рынки, геномные последовательности, PageRank.

Определение и свойства Маркова

Определение: Последовательность X₀, X₁, X₂,... со значениями в конечном/счётном множестве S удовлетворяет марковскому свойству: P(Xₙ₊₁ = j | X₀,...,Xₙ) = P(Xₙ₊₁ = j | Xₙ) для всех n и j.

Матрица переходов: Pᵢⱼ = P(Xₙ₊₁ = j | Xₙ = i). Стохастическая: Pᵢⱼ ≥ 0, ΣⱼPᵢⱼ = 1 для всех i.

n-шаговые переходы: P(Xₙ = j | X₀ = i) = (Pⁿ)ᵢⱼ — (i,j)-й элемент матрицы Pⁿ.

Классификация состояний

Возвратное состояние: i — возвратное, если P(вернуться в i) = 1. Нулевое-возвратное: E[время возврата] = ∞. Положительно-возвратное: E[время возврата] < ∞.

Переходное состояние: i — переходное, если P(вернуться в i) < 1. Посетить конечное число раз.

Периодичность: Период d(i) = НОД{n ≥ 1: (Pⁿ)ᵢᵢ > 0}. При d=1 — апериодическое.

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

Стационарное распределение π: Вектор π ≥ 0, Σπᵢ = 1: π = πP. Для конечной неприводимой апериодической цепи: единственное π, и Pⁿ → 1·πᵀ.

Теорема эргодическая: Для неприводимой положительно-возвратной цепи: доля времени в состоянии i → πᵢ при n→∞ (П.Н.). Πᵢ = 1/E[τᵢ] (обратная среднему времени возврата).

Задание: (а) Цепь погоды: P(солнце|солнце)=0.8, P(дождь|дождь)=0.6. Матрица P. Найдите π и средние времена возврата. (б) PageRank: граф из 4 страниц, каждая ссылается на другие равновероятно. Найдите π методом π=πP. (в) Случайное блуждание на {0,1,...,N} с поглощением в 0 и N. P(поглощение в N | старт i) = i/N — докажите.

Эргодичность и предельные теоремы для цепей Маркова

Эргодическая цепь — неразложимая, непериодическая, положительно рекуррентная. Для эргодической цепи: μₙ → π (геометрически быстро при конечном S). Скорость смешения: gap спектра Lₛ = 1 − λ₂ (λ₂ — второе наибольшее собственное значение P). Время смешения: τ_mix ≈ 1/gap. Для «мешалки» (полный граф с равными весами): gap = 1 → мгновенное смешение.

Теорема об эргодическом среднем: (1/n)Σᵢ₌₀^{n-1} f(Xᵢ) →_{п.н.} Σⱼ f(j)πⱼ для любой функции f с Σ|f(j)|πⱼ < ∞. Это ЗБЧ для цепей Маркова — основа MCMC (Markov Chain Monte Carlo).

MCMC: Метрополис-Гастингс и сэмплирование Гиббса

Проблема: Как сэмплировать из сложного распределения π(x) (нормировочная константа Z неизвестна)? MCMC решение: построить цепь с инвариантным распределением π.

Алгоритм Метрополиса-Гастингса: Предложить x' из q(x'|x). Принять с вероятностью α = min(1, π(x')q(x|x')/(π(x)q(x'|x))). Детальный баланс: π(x)P(x→x') = π(x')P(x'→x) ⟹ π — инвариантно. Работает даже без нормировки Z!

Сэмплирование Гиббса: Последовательно обновляем каждую координату из условного распределения: Xᵢ ~ π(Xᵢ|X_{-ᵢ}). Специальный случай MH с коэффициентом принятия 1. Применяется в байесовских моделях, LDA (латентное размещение Дирихле), HMM.

Скрытые марковские модели (HMM)

HMM: скрытая цепь Маркова Z₁,Z₂,...,Zₙ (K состояний) + наблюдаемые X₁,...,Xₙ с P(Xₜ|Zₜ). Три задачи: (1) Декодирование (Viterbi): найти наиболее вероятную скрытую последовательность Z* — алгоритм Витерби (DP, O(nK²)). (2) Фильтрация (forward-backward): P(Zₜ|X₁,...,Xₙ) — алгоритм прямой-обратной (O(nK²)). (3) Оценка параметров (Baum-Welch = EM): итеративный алгоритм.

Применения: распознавание речи (состояния = фонемы), геномика (CpG-islands), финансы (режимы рынка).

Теорема о сходимости MCMC

Для эргодической цепи Маркова: ||Pⁿ(x,·) − π||_TV ≤ r·ρⁿ, где r > 0, ρ < 1 — скорость смешения. Спектральный gap: λ₂ — второе собственное значение (для обратимых цепей). Скорость смешения определяется 1−λ₂. Пространственный gap и log-Sobolev неравенство дают более точные оценки.

Практика: длина «разогрева» (burn-in) должна быть достаточной для достижения стационарного режима. Диагностика сходимости: критерий Гельмана-Рубина (R̂ < 1.1), автокорреляция цепи, тест Гевеке.

Вариационные методы и нормализующие потоки

Нормализующие потоки: трансформировать простое распределение (стандартное нормальное) через обратимые дифференцируемые функции f: z ~ p_z, x = f(z), p_x(x) = p_z(f⁻¹(x))·|det(∂f⁻¹/∂x)|. Точное вычисление лог-правдоподобия! RealNVP: разбить z = (z_a, z_b), x_a = z_a, x_b = z_b·exp(s(z_a)) + t(z_a). Якобиан треугольный → det вычисляется за O(d). Применение: генеративные модели, плотностная оценка, вариационный вывод.

Спектральные методы в кластеризации

Спектральная кластеризация: построить граф близости, нормализованный лапласиан L = I − D^{-1/2}AD^{-1/2}. Первые k собственных векторов L образуют новое представление → k-means в новом пространстве. Теорема о связи с многообразиями: спектральная кластеризация выявляет геометрические кластеры, которые k-means пропускает. Применение: сегментация изображений, выявление сообществ в социальных сетях.

Численный пример: стационарное распределение цепи Маркова

Задача: Двухсостоятельная ЦМ (солнце/дождь): P(солнце|дождь)=0.4, P(дождь|солнце)=0.3. Матрица: P=[[0.7,0.3],[0.4,0.6]]. Найти π и время первого возврата.

Шаг 1: Система π·P=π: π₁=0.7π₁+0.4π₂, π₂=0.3π₁+0.6π₂, π₁+π₂=1.

Шаг 2: Из первого уравнения: 0.3π₁=0.4π₂ → π₁=4π₂/3. Нормировка: 4π₂/3+π₂=1 → 7π₂/3=1 → π₂=3/7≈0.429.

Шаг 3: π₁=4/7≈0.571, π₂=3/7≈0.429. Долгосрочно: 57.1% дней — солнечные.

Шаг 4: E[T_солн]→солн=1/π₁=7/4=1.75 шага. Скорость сходимости: λ₂=tr(P)−det(P)... нет, второе СЗ = 0.7+0.6−1=0.3. P^n сходится к [[π₁,π₂],[π₁,π₂]] как 0.3ⁿ. При n=10: 0.3¹⁰≈0.000006 — практически мгновенное перемешивание.