Случайные процессы
Мартингалы
Мартингал - математическая формализация честной игры. Любая стратегия ставок (мартингальная, фибоначчи, d'Alembert) не меняет ожидаемый выигрыш - это следствие одного уравнения: $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n$. Теорема Дуба об остановке доказывает: нельзя победить честную игру умной стратегией выхода. Казино знает это. SGD-инженеры тоже: та же теорема объясняет, почему Adam с weight decay строго лучше простого Adam для гарантий сходимости. Мартингал - универсальный язык «честности» в математике.
- **Black-Scholes:** цены дериватив в модели без арбитража - мартингалы при нейтральной к риску мере. Весь рынок опционов, USD 1+ квадриллион условного объёма в год, построен на этом факте.
- **SGD convergence:** SGD с постоянным lr - не мартингал (дрейфует). SGD с убывающим lr ~ 1/t - супермартингал (сходится). Это доказывается через теорему сходимости супермартингалов Дуба. Adam с weight decay - строго лучше для теоретических гарантий.
- **Online learning regret bounds:** Azuma-Hoeffding неравенство для мартингальных разностей даёт O(sqrt(T)) regret в adversarial bandits. Каждый алгоритм типа EXP3 или AdaGrad использует эту математику.
Предварительные знания
Мартингал
Мартингал - это честная игра. Математически: $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n$. Следствие немедленное и разрушительное: любая стратегия ставок (мартингальная, фибоначчи, d'Alembert) не изменяет ожидаемый выигрыш. Казино это знает. Gamblers - нет. И на этом же факте строится Black-Scholes, доказывается сходимость SGD и выводятся regret bounds в online learning.
**Определение мартингала.** Последовательность $(X_n, \mathcal{F}_n)$ является мартингалом, если: 1. $X_n$ адаптирован к фильтрации $\mathcal{F}_n$ ($X_n$ измерим относительно $\mathcal{F}_n$) 2. $\mathbb{E}[|X_n|] < \infty$ для всех n 3. $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n$ (условное ожидание следующего значения равно текущему) Если $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] \geq X_n$ - субмартингал (нижний дрейф). Если $\leq X_n$ - супермартингал (верхний дрейф).
| Пример | Процесс X_n | Тип | Пояснение |
|---|---|---|---|
| Случайное блуждание | S_n = X_1+...+X_n, E[X_i]=0 | Мартингал | Симметричные ходы ±1 |
| Честная игра | Капитал игрока | Мартингал | E[выигрыш] = 0 каждый раунд |
| Геометрическое блуждание | S_n = prod(1+X_i), E[X_i]=0 | Мартингал | Логарифм - симм. блуждание |
| Условное матожидание | E[Z | F_n] | Мартингал | Ключевой пример для теории |
| Несправедливая игра (казино) | Капитал игрока | Супермартингал | E[завтра] < сегодня |
Происхождение термина
Слово «мартингал» - из французского жаргона, стратегия удвоения ставок. Математическую теорию создал Жозеф Вилле (Ville, 1939), фундаментальные результаты доказал Жозеф Лео Дуб (Doob) в 1950-х. В модели Блэка-Шоулза цены активов, дисконтированные по безрисковой ставке, являются мартингалами при нейтральной к риску мере. Та же концепция живет в доказательстве сходимости SGD при убывающем learning rate.
Мартингал - процесс без тренда, то есть E[X_n] = const
Мартингал - это $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n$ для всех n. Из этого следует E[X_n] = E[X_0], но важнее условное ожидание, а не безусловное
Процесс может иметь E[X_n] = 0 для всех n, но не быть мартингалом (например, независимые X_n с нулевым средним). Мартингал автоматически имеет постоянное безусловное среднее - но через условную структуру, не через маргинальные распределения
Процесс X_n - это капитал игрока в игре, где каждый раунд выигрывают +2 с вероятностью 1/3 и проигрывают -1 с вероятностью 2/3. Является ли X_n мартингалом?
Время остановки
Стратегия «остановись, когда выиграешь 10 монет или разоришься» - это случайный момент остановки. Но вот ключевое ограничение: решение принимается только на основе доступной информации, без взгляда в будущее. Это и есть **время остановки** - случайная величина, для которой событие $\{\tau = n\}$ определяется только по $\mathcal{F}_n$. Именно это условие измеримости делает теорему Дуба содержательной.
**Время остановки (марковский момент):** случайная величина $\tau: \Omega \to \{0, 1, \ldots, \infty\}$ такая, что $\{\tau = n\} \in \mathcal{F}_n$ для всех $n \geq 0$. Интуиция: наблюдатель может определить, что «время пришло» ($\tau = n$) в момент n, используя только $\mathcal{F}_n$, не зная будущего. Эквивалентно: $\{\tau \leq n\} \in \mathcal{F}_n$ для всех n.
Алгебра событий $\mathcal{F}_\tau$ в момент остановки содержит всю информацию, накопленную до $\tau$ включительно: $\mathcal{F}_\tau = \{A : A \cap \{\tau = n\} \in \mathcal{F}_n \text{ для всех } n\}$. Это «всё, что известно к моменту остановки» - концепция, без которой теорема об опциональной остановке не формулируется.
| Тип | Пример τ | Время остановки? | Пояснение |
|---|---|---|---|
| Первое попадание | min{n : S_n >= a} | Да | {τ=n} = {S_0<a,...,S_{n-1}<a,S_n>=a} ∈ F_n |
| Фиксированный момент | τ = 100 | Да | Детерминированный - базовый случай |
| Максимум на отрезке | argmax_{n<=N} S_n | Нет (с оговоркой) | После фиксации N - да, до - нет |
| Последнее посещение | max{n : S_n = 0} | Нет | Требует знания будущего |
Любое ограниченное случайное время является временем остановки
Время остановки - это условие измеримости: $\{\tau \leq n\} \in \mathcal{F}_n$. Решение об остановке принимается, зная только прошлое и настоящее
Рассмотрим $\tau = \max S_n$ на [0, 100]: ограничено, но чтобы знать, является ли момент n максимумом, нужно видеть $n+1, \ldots, 100$. Это нарушает измеримость
Является ли $\tau = \max\{n \leq 100 : S_n = 0\}$ временем остановки относительно естественной фильтрации $S_n$?
Теорема Дуба об опциональной остановке
Главный вопрос: можно ли «обхитрить» честную игру умной стратегией остановки? Остановиться на пике. Выйти перед падением. Интуиция подсказывает - да. Теорема Дуба говорит нет. При разумных условиях $\mathbb{E}[X_\tau] = \mathbb{E}[X_0]$ - ожидаемый выигрыш не меняется, сколько бы изощрённой ни была стратегия остановки.
**Теорема Дуба (Optional Stopping Theorem).** Пусть $(X_n, \mathcal{F}_n)$ - мартингал и $\tau$ - время остановки. Тогда $\mathbb{E}[X_\tau] = \mathbb{E}[X_0]$, если выполнено хотя бы одно из условий: 1. $\tau$ ограничено: $\tau \leq N$ (для некоторого конечного N) 2. $\mathbb{E}[\tau] < \infty$ и $|X_{n+1} - X_n| \leq C$ (ограниченные приращения) 3. $\mathbb{E}[\sup_n |X_{n \wedge \tau}|] < \infty$ (равномерно интегрируемый stopped process)
Почему стратегия мартингала (удвоения ставок) не работает? Потому что она нарушает условие ограниченных приращений: каждый следующий проигрыш требует вдвое больше. При конечном бюджете $\mathbb{E}[\tau] = \infty$ с ненулевой вероятностью - а значит, условия теоремы Дуба не выполнены. Казино ограничивает ставки не из жадности, а именно чтобы заблокировать этот граничный случай.
| Задача | Мартингал X_n | E[X_τ] | Следствие |
|---|---|---|---|
| Задача о разорении (симм.) | Блуждание S_n | = S_0 = k | P(достичь N) = k/N |
| Ожидаемое время разорения | S_n² - n (мартингал) | = k² - E[τ] | E[τ] = k(N-k) |
| Опцион в финансах | Дисконт. цена актива | = текущая цена | Нет арбитража при риск-нейтр. мере |
С правильной стратегией остановки можно превратить честную игру в выигрышную
Теорема об опциональной остановке гарантирует $\mathbb{E}[X_\tau] = \mathbb{E}[X_0]$ при разумных условиях. Никакая стратегия остановки не даёт положительного ожидаемого выигрыша
Стратегии типа «остановись на первом выигрыше» создают иллюзию: остановки всегда на выигрыше, но проигрышные исходы накапливают потери. При расчёте $\mathbb{E}[X_\tau]$ каждый исход взвешивается своей вероятностью - и мартингал не обманешь
Игрок начинает с 4 монет в симметричном блуждании, цель - 10 монет или разорение. По теореме об опциональной остановке, какова P(достичь 10)?
Неравенства и декомпозиция Дуба
Жозеф Лео Дуб (1910-2004) построил фундамент теории мартингалов. Его результаты выходят за пределы азартных игр: **разложение Дуба-Мейера** позволяет представить любой субмартингал как сумму мартингала и неубывающего предсказуемого процесса. Это аналог разделения «шума» и «тренда» - и именно на нём держится стохастическое интегрирование Ито, теорема сходимости для SGD при убывающем lr, и Azuma-Hoeffding bounds в online learning.
**Неравенство максимума Дуба:** Для субмартингала $X_n \geq 0$: $$\mathbb{P}\left(\max_{k \leq n} X_k \geq \lambda\right) \leq \frac{\mathbb{E}[X_n]}{\lambda}$$ **Неравенство Дуба в $L^2$:** Для мартингала $X_n$: $$\mathbb{E}\left[\max_{k \leq n} X_k^2\right] \leq 4 \cdot \mathbb{E}[X_n^2]$$ **Разложение Дуба:** Любой субмартингал $X_n = M_n + A_n$, где $M_n$ - мартингал, $A_n$ - неубывающий предсказуемый процесс (компенсатор).
Разложение Дуба-Мейера в непрерывном времени привело к стохастическому интегрированию Ито. Компенсатор $A_t$ для квадратичного мартингала $M_t^2$ - это квадратичная вариация $\langle M \rangle_t$. Эта структура лежит в основе формулы Ито и уравнений Блэка-Шоулза. В ML: SGD с постоянным learning rate - не мартингал (не сходится). SGD с убывающим $\text{lr} \sim 1/t$ - супермартингал (сходится). Это не деталь реализации - это теорема.
Жозеф Лео Дуб
Дуб (Joseph Leo Doob, 1910-2004) - американский математик, создавший строгую теорию вероятностных процессов. Его книга «Stochastic Processes» (1953) определила язык и методы теории вероятностей на десятилетия вперёд. Дуб первым доказал теоремы о сходимости мартингалов, неравенство максимума и теорему об опциональной остановке - результаты, которые сегодня живут в каждом доказательстве сходимости оптимизаторов и в каждом regret bound online learning.
Разложение Дуба применимо только к дискретным процессам
Разложение Дуба-Мейера обобщается на непрерывное время и является основой стохастического анализа Ито. Компенсатор в непрерывном времени - квадратичная вариация
Дискретный случай интуитивен: $A_n = \sum \mathbb{E}[X_{k+1}-X_k \mid \mathcal{F}_k]$. В непрерывном времени это обобщается в интеграл - процесс квадратичной вариации $\langle M \rangle_t$, который и является предсказуемым компенсатором
Что утверждает неравенство максимума Дуба для неотрицательного субмартингала $X_n$?
Ключевые идеи
- **Мартингал** - формализация честной игры: $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n$, ожидаемый «завтрашний» капитал равен сегодняшнему
- **Время остановки** $\tau$ - момент, решение о котором принимается без знания будущего: $\{\tau \leq n\} \in \mathcal{F}_n$
- **Теорема Дуба (OST)** - $\mathbb{E}[X_\tau] = \mathbb{E}[X_0]$ при разумных условиях: никакая стратегия остановки не «обыгрывает» мартингал
- **Неравенство максимума** - аналог Маркова для максимума процесса; разложение Дуба разделяет мартингальную и трендовую компоненты
- **В ML:** SGD с lr~1/t - супермартингал (сходится); Azuma-Hoeffding - мартингальные regret bounds в online learning
Связанные темы
Мартингалы - центральная концепция, связывающая дискретную и непрерывную теорию:
- Мартингальные неравенства и сходимость — Теорема сходимости, равномерная интегрируемость - следующий шаг
- Броуновское движение — Непрерывный мартингал - фундамент стохастического анализа Ито
- Финансовая математика — Мартингальная мера - основа ценообразования опционов без арбитража
Вопросы для размышления
- Стратегия удвоения ставки гарантирует выигрыш при неограниченном капитале. Почему казино не разоряется - и какое из условий теоремы Дуба нарушается в реальной игре?
- Если $X_n$ и $Y_n$ - мартингалы, является ли $X_n \cdot Y_n$ мартингалом? При каких условиях?
- SGD с постоянным learning rate не сходится в строгом смысле. Как это связано с тем, что такой процесс - не мартингал и не супермартингал?
- Дисконтированная цена актива в модели без арбитража - мартингал. Что это означает практически для трейдера, пытающегося строить прогнозы?