Цепи Маркова

PageRank Google - это стационарное распределение цепи Маркова на графе Web. Алгоритм ранжирует 130 триллионов страниц, решая одно матричное уравнение. MCMC-методы, используемые в Bayesian ML для выборки из сложных распределений, тоже основаны на цепях Маркова.

• PageRank Google: стационарное распределение на графе Web - ранжирует 130T страниц
• MCMC (Байесовский ML): Metropolis-Hastings и HMC для выборки из апостериорных распределений
• Hidden Markov Models: распознавание речи в Siri и Google Assistant
• Генеративные LLM: следующий токен - марковская модель высокого порядка
• A/B тесты: sequential testing через цепи Маркова для раннего останова
• Финансы: модели процентных ставок Vasicek и Hull-White как марковские процессы

Марковское свойство и матрица переходов

PageRank - алгоритм, по которому Google ранжирует миллиарды страниц - это стационарное распределение цепи Маркова. Каждый поисковый запрос в мире неявно решает уравнение **pi = piP**. Андрей Марков придумал эту структуру в 1906 году, анализируя чередование гласных и согласных в «Евгении Онегине». Сейчас она встроена в каждую рекомендательную систему, языковую модель и движок Reinforcement Learning.

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

Цепь Маркова - последовательность случайных величин X₀, X₁, X₂, ... со свойством: будущее зависит только от настоящего, не от прошлого.

Пример: погода. Состояния - солнечно (S) и дождь (R). Завтрашняя погода зависит только от сегодняшней, не от всей недели. Матрица переходов:

В матричном виде P - это переходная (stochastic) матрица: каждый элемент Pᵢⱼ >= 0 и сумма по строке равна 1.

n-шаговые переходы: Chapman-Kolmogorov

Вероятность попасть из состояния i в состояние j за n шагов - это элемент матрицы P^n (матричная степень). Уравнение Chapman-Kolmogorov:

Для погодного примера: P^2 показывает вероятности за два дня. При n -> inf матрица P^n сходится - каждая строка становится одним и тем же вектором. Это и есть стационарное распределение.

P^n сходится независимо от начальной строки - при n=50 все строки матрицы одинаковы. Начальное состояние забывается.

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

Стационарное распределение pi - вероятностный вектор, который цепь «не двигает». Если начать с распределения pi, через один шаг снова получается pi. Это **левый собственный вектор** P для собственного значения 1.

Для погодного примера: решаем pi*P = pi.

pi = [pi_S, pi_R] pi_S = 0.8*pi_S + 0.4*pi_R pi_R = 0.2*pi_S + 0.6*pi_R pi_S + pi_R = 1 Из первого уравнения: 0.2*pi_S = 0.4*pi_R => pi_S = 2*pi_R Подставляем: 2*pi_R + pi_R = 1 => pi_R = 1/3, pi_S = 2/3 pi = [2/3, 1/3] ~= [0.667, 0.333]

Стационарное распределение не зависит от начального состояния - только от структуры P. Независимо от того, начинаем с солнца или дождя, через много шагов распределение одно.

Условие существования и детальный баланс

Теорема Перрона-Фробениуса: каждая **неприводимая** (irreducible) и **апериодическая** (aperiodic) конечная цепь имеет единственное стационарное распределение, и P^n сходится к нему.

• Неприводимая: из любого состояния можно добраться до любого другого
• Апериодическая: нет «циклических ловушек» (gcd длин всех циклов = 1)

Условие детального баланса (reversibility) - более сильное свойство, гарантирующее стационарность:

Цепь с детальным балансом называется обратимой (reversible). Metropolis-Hastings специально конструирует обратимые цепи.

PageRank: pi = стационарное распределение веб-графа

Случайный серфер переходит по ссылкам с вероятностью d=0.85 (damping factor), и с вероятностью 0.15 прыгает на случайную страницу. PageRank - стационарное распределение этой цепи:

Power iteration - самый быстрый способ найти pi для больших разреженных графов. Google изначально применял именно его для веб-графа из миллиардов страниц.

Эргодичность и MCMC

Байесовский вывод с 10 000 параметрами: аналитически невозможно, напрямую сэмплировать тоже - пространство слишком велико. MCMC (Markov Chain Monte Carlo) строит цепь Маркова, стационарное распределение которой совпадает с нужным posterior. Затем просто «гуляем» по цепи и собираем сэмплы.

Эргодическая теорема

Для эргодической цепи (неприводимой и апериодической) временное среднее по траектории равно пространственному среднему по стационарному распределению:

Это мощный факт: не нужно знать pi явно. Достаточно запустить цепь и усреднить функцию по траектории.

Время смешивания (mixing time)

Mixing time - сколько шагов нужно, чтобы цепь «забыла» начальное состояние. Формально: минимальное n, при котором распределение цепи epsilon-близко к pi по вариационному расстоянию.

Mixing time определяет, сколько сэмплов MCMC нужно «выбросить» в начале (burn-in). Плохо спроектированная цепь может смешиваться экспоненциально долго.

Metropolis-Hastings: конструкция нужной цепи

Metropolis-Hastings строит обратимую цепь с заданным стационарным распределением p(x). На каждом шаге: предлагаем переход x -> y из proposal q(y|x), принимаем с вероятностью:

Детальный баланс выполняется по построению: p(x) alpha(x,y) = p(y) alpha(y,x). Это гарантирует, что p - стационарное распределение цепи.

Stan, PyMC и NumPyro - популярные Bayesian inference фреймворки - используют MCMC под капотом. PyMC3 строит цепи NUTS (No-U-Turn Sampler), улучшенную версию Hamiltonian Monte Carlo.

Hidden Markov Models и алгоритм Витерби

Речь, текст, белки - в них скрытые состояния порождают наблюдения. Hidden Markov Model (HMM) разделяет скрытый марковский процесс X и видимые наблюдения Y: POS-тег (скрытый) порождает слово (видимое). Google Assistant, Apple Siri и ранние системы Dragon NaturallySpeaking работали именно на HMM.

Структура HMM

HMM задаётся тройкой (A, B, pi0):

• A = матрица переходов скрытых состояний: A[i,j] = P(Xₙ₊₁=j | Xₙ=i)
• B = матрица эмиссий: B[i,k] = P(Yₙ=k | Xₙ=i)
• pi0 = начальное распределение скрытых состояний

Алгоритм Витерби

Viterbi находит наиболее вероятный путь скрытых состояний X* = argmax P(X|Y) за O(N*T) динамическим программированием. Ключевая рекурсия:

Состояния: S1 (солнечно), S2 (дождь) Наблюдения: ходьба (W), покупки (S), чистка (C) A = [[0.7, 0.3], [0.4, 0.6]] B = [[0.5, 0.4, 0.1], [0.1, 0.3, 0.6]] pi0 = [0.6, 0.4] Y = [W, S, C] t=1 (W): delta[S1]=0.6*0.5=0.30, delta[S2]=0.4*0.1=0.04 t=2 (S): delta[S1]=max(0.30*0.7, 0.04*0.4)*0.4 = 0.084 delta[S2]=max(0.30*0.3, 0.04*0.6)*0.3 = 0.027 t=3 (C): delta[S1]=max(0.084*0.7, 0.027*0.4)*0.1 = 0.00588 delta[S2]=max(0.084*0.3, 0.027*0.6)*0.6 = 0.01512 X* = [S1, S1, S2], вероятность = 0.01512

HMM -> трансформеры: эволюция

Attention в трансформерах можно рассматривать как «мягкий» Viterbi: вместо argmax по скрытому пути - взвешенная сумма по всем позициям. BERT и GPT заменили HMM в NLP именно потому, что attention не ограничен марковским свойством - он смотрит на всю последовательность сразу.

HMM до сих пор используются в биоинформатике (предсказание генов, выравнивание белков через profile HMM в HMMER) и в low-resource задачах, где мало данных для трансформера.

Ключевые идеи

• Марковское свойство: P(Xₙ₊₁|X₀..Xₙ) = P(Xₙ₊₁|Xₙ) - только настоящее важно для будущего
• Матрица переходов P: строко-стохастическая (Pᵢⱼ >= 0, сумма по строке = 1)
• n-шаговые переходы: (P^n)ᵢⱼ - Chapman-Kolmogorov
• Стационарное распределение: piP = pi, уникально для неприводимых апериодических цепей
• PageRank = стационарное распределение веб-графа с damping d=0.85
• MCMC (Metropolis-Hastings): строим цепь с нужным стационарным распределением для Bayesian inference
• HMM + Viterbi: скрытые состояния + наблюдения, O(N^2*T) поиск оптимального пути

Связанные темы

Цепи Маркова - основа большой части современного ML и статистики.

• Reinforcement Learning (MDP) — Markov Decision Process - цепь Маркова с действиями и наградами, основа Q-learning и Policy Gradient
• Пуассоновские процессы — Цепи Маркова с непрерывным временем - arrivals, queueing theory
• Собственные векторы и PageRank — pi - левый собственный вектор P для lambda=1; связь с spectral graph theory
• Байесовский вывод — MCMC делает posterior inference вычислимым для сложных моделей

Связанные уроки

• aie-03-llm-fundamentals
• ml-48-rl-intro
• ml-49-q-learning