Случайные процессы
Цепи Маркова с дискретным временем
Каждый алгоритм reinforcement learning - от Q-learning до PPO - строится на одной аксиоме: **марковское свойство**. Среда отвечает только на текущее состояние, не на историю. Без этого нельзя написать уравнение Беллмана. Без Беллмана нет Q-learning. Без Q-learning нет DQN, PPO, SAC. Вся современная автономная навигация, AlphaGo, ChatGPT с RLHF - всё это цепи Маркова.
- **PageRank Google:** веб-граф как цепь Маркова, стационарное распределение - рейтинг страницы; теорема Перрона-Фробениуса гарантирует существование и единственность
- **Reinforcement learning:** среда - марковский процесс принятия решений (MDP); $\mathbb{P}(s_{t+1} \mid s_t, a_t)$ - переходное ядро; Q-learning, PPO, SAC - разные способы найти оптимальную политику
- **MCMC:** Metropolis-Hastings, HMC, NUTS - специально сконструированные эргодические цепи, чья стационарное распределение есть нужный posterior; без эргодичности нет сходимости
Матрица переходов
1913 год. Андрей Марков берёт роман Пушкина «Евгений Онегин» и считает, с какой вероятностью за гласной следует согласная - и наоборот. Результат: первая в истории цепь Маркова. За следующие 110 лет эта идея переросла в PageRank, языковые модели и основу всего reinforcement learning.
**Марковское свойство:** будущее зависит только от настоящего, не от прошлого. $\mathbb{P}(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots) = \mathbb{P}(X_{n+1} = j \mid X_n = i)$. Всё, что нужно знать о системе - её текущее состояние. **Матрица переходов** $P$ собирает эти вероятности: $P_{ij}$ - вероятность перейти из состояния $i$ в $j$ за один шаг.
**Стохастическая матрица:** каждая строка $P$ суммируется в 1 (из каждого состояния система куда-то переходит). Все элементы неотрицательны. Это правая стохастическая матрица. Левая стохастическая - столбцы суммируются в 1.
Возведение $P$ в степень $n$ - это $n$ шагов цепи. $P^n_{ij}$ - вероятность оказаться в $j$ через $n$ шагов из $i$. Для эргодических цепей все строки $P^n$ сходятся к одному вектору. Этот вектор называется стационарным распределением - и он лежит в основе PageRank.
Что означает $P_{ij} = 0.3$ в матрице переходов?
Стационарное распределение
1996 год. Брин и Пейдж в Стэнфорде придумывают алгоритм ранжирования веб-страниц. Идея: представить веб как цепь Маркова - страницы как состояния, ссылки как переходы. Рейтинг страницы - это её вероятность в **стационарном распределении** этой цепи. Google запущен. Алгоритм называется PageRank.
Стационарное распределение $\pi$ - вектор, который матрица переходов не меняет: $\pi P = \pi$. Запустите цепь достаточно долго - и частоты посещения состояний стабилизируются именно в $\pi$. Это левый собственный вектор $P$ с собственным значением 1. Дополнительно: $\sum_i \pi_i = 1$ и $\pi_i \geq 0$.
Интуиция: стационарное распределение описывает **баланс потоков**. В каждое состояние втекает ровно столько вероятности, сколько вытекает. Если $\pi_i \cdot P_{ij}$ - поток из $i$ в $j$, то сумма всех потоков в $j$ равна $\pi_j$.
| Состояние | pi_i | Среднее время возврата |
|---|---|---|
| Солнце | 0.465 | 1/0.465 ~= 2.15 дней |
| Облачно | 0.279 | 1/0.279 ~= 3.58 дней |
| Дождь | 0.256 | 1/0.256 ~= 3.91 дней |
**Теорема Перрона-Фробениуса** гарантирует: для неотрицательной неприводимой матрицы существует единственное стационарное распределение, и собственное значение 1 строго доминирует. Именно поэтому PageRank сходится: цепь эргодична (неприводима + апериодична) благодаря «телепортации» - прыжку на случайную страницу с вероятностью 0.15.
Стационарное распределение $\pi$ удовлетворяет $\pi P = \pi$. Это означает:
Эргодическая цепь
Не каждая цепь сходится к единственному стационарному распределению. Нужно два свойства. **Неприводимость**: из любого состояния можно попасть в любое (граф сильно связен). **Апериодичность**: нет циклов фиксированной длины (система не осциллирует). Цепь с обоими свойствами называется **эргодической** - и тогда $P^n$ гарантированно сходится к $\pi$ при $n \to \infty$.
**Неприводимость:** для любых $i, j$ существует $n$ такое, что $P^n_{ij} > 0$. **Апериодичность:** НОД всех длин путей из $i$ в $i$ равен 1. **Теорема:** неприводимая + апериодическая цепь имеет единственное $\pi$, и $P^n \to \pi$ при $n \to \infty$.
Andrey Markov и «Евгений Онегин»
Андрей Марков применил теорию цепей в 1913 году для анализа чередования гласных и согласных в «Евгении Онегине». Это был первый пример статистического анализа текста - прямой предтеча языковых моделей. Сто лет спустя GPT предсказывает токены через ту же идею, только цепь стала нейронной и $n$-грамм заменился трансформером.
Практически все реальные цепи Маркова эргодичны. Достаточно одной петли ($P_{ii} > 0$), чтобы сломать периодичность. PageRank добавляет «телепортацию» - переход на случайную страницу с вероятностью $\alpha = 0.15$ - именно для гарантии неприводимости. Модифицированная матрица: $P' = (1-\alpha)P + \alpha \frac{\mathbf{1}\mathbf{1}^T}{n}$. Эргодичность = сходимость = рейтинг существует.
| Свойство | Определение | Последствие |
|---|---|---|
| Неприводимость | Из любого состояния можно достичь любого | Единственный коммуникационный класс |
| Апериодичность | НОД длин циклов = 1 | P^n сходится (не осциллирует) |
| Эргодичность | Неприводимость + апериодичность | Единственное pi, P^n -> pi |
Цепь с двумя состояниями и матрицей $P = [[0, 1], [1, 0]]$ не является эргодической, потому что:
Поглощающие состояния
Состояние $a$ называется **поглощающим**, если $P_{aa} = 1$ - войдя в него, система никогда не выходит. Цепь с поглощающими состояниями не эргодична (она приводима), но у неё есть своя элегантная теория. Два ключевых вопроса: с какой вероятностью система попадёт в каждое поглощающее состояние? Сколько шагов займёт поглощение?
Классический пример - **задача разорения игрока**. Игрок начинает с $k$ монет, цель - накопить $N$, банкротство при 0. За каждый ход - плюс или минус монета с вероятностью 0.5. Состояния 0 (банкрот) и $N$ (победа) - поглощающие. Интуиция подсказывает: монета честная - должно быть 50/50. Математика отвечает иначе.
**Каноническая форма** поглощающей цепи: перенумеруем состояния так, чтобы поглощающие шли последними. Тогда $P = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}$, где $Q$ - переходы между непоглощающими состояниями, $R$ - переходы в поглощающие, $I$ - единичная (остаёмся навсегда).
Результат контринтуитивен: вероятность банкротства при честной монете равна $(N-k)/N$ - линейна по начальному капиталу. Начиная с 1 из 5 монет: 80% шанс банкрота, 20% победы. Казино это давно знает: у «дома» начальный капитал $N \gg k$ - поэтому казино всегда побеждает, даже при честной монете. Именно этот расчёт остановил Паскаля от азартных игр в 1654.
| Начальный капитал | P(банкрот) | P(победа) | Среднее шагов |
|---|---|---|---|
| 1 из 5 | 0.80 | 0.20 | 4.0 |
| 2 из 5 | 0.60 | 0.40 | 6.0 |
| 3 из 5 | 0.40 | 0.60 | 6.0 |
| 4 из 5 | 0.20 | 0.80 | 4.0 |
Цепь Маркова = без памяти = полностью случайное блуждание
Марковское свойство означает: будущее зависит только от ТЕКУЩЕГО состояния, а не от всей истории. Это не случайное блуждание - переходы могут быть сложными и разными из разных состояний
PageRank, HMM в распознавании речи, MCMC в байесовском выводе - все используют цепи Маркова со сложной структурой. Марковское свойство - не «случайность», а «текущее состояние достаточно для предсказания будущего». Именно это делает Q-learning возможным: $Q(s, a)$ зависит только от $(s, a)$, а не от всей истории.
В задаче разорения игрока с честной монетой, начальным капиталом 2 монеты и целью 5, вероятность банкротства равна:
Ключевые идеи
- **Матрица переходов** $P$ - стохастическая матрица, $P_{ij} = \mathbb{P}(X_{n+1}=j \mid X_n=i)$; строки суммируются в 1
- **Стационарное распределение** $\pi P = \pi$ - неподвижная точка; PageRank - стационарное распределение на веб-графе
- **Эргодичность** = неприводимость + апериодичность $\Rightarrow$ единственное $\pi$, $P^n \to \pi$; именно поэтому MCMC сходится
- **Поглощающие состояния:** фундаментальная матрица $N = (I-Q)^{-1}$ даёт среднее время и вероятности поглощения; задача разорения игрока - классический пример
Связанные темы
Цепи Маркова - мост между случайными процессами и приложениями:
- Случайные процессы: определения — Цепь Маркова - важнейший класс стохастических процессов с марковским свойством
- Цепи Маркова с непрерывным временем — CTMC расширяет DTMC на непрерывное время - модели очередей и химических реакций
- MCMC и сэмплирование — Metropolis-Hastings и HMC - эргодические цепи Маркова для байесовского вывода
Вопросы для размышления
- Является ли процесс набора текста марковским? Достаточно ли одного предыдущего слова для предсказания следующего - и почему трансформеры работают лучше n-грамм?
- Если в PageRank убрать «телепортацию» (случайный переход на любую страницу), какое свойство цепи нарушится? Что случится с рейтингом страниц-«ловушек»?
- MCMC строит эргодическую цепь Маркова с нужным стационарным распределением. Что произойдёт с алгоритмом, если цепь окажется периодической?