Мартингалы

Цели урока

• Понять мартингал как формализацию честной игры через условное ожидание
• Освоить теорему об остановке Дуба и её условия
• Решить задачу о разорении игрока двумя мартингалами
• Применять неравенства Дуба для оценки хвостов
• Видеть мартингалы в SGD, Azuma-Hoeffding и Black-Scholes

Предварительные знания

• Условное математическое ожидание E[X|F]
• Tower Property
• Симметричное случайное блуждание
• Sigma-алгебры и фильтрации

• Условное математическое ожидание

Казино никогда не проигрывает системе удвоения ставок. После каждого проигрыша ставка удваивается - при первой победе отыгрывается всё плюс начальная ставка. Кажется, схема беспроигрышна. Ожидаемое богатство после любого числа ходов равно начальному капиталу. Теория мартингалов - строгое доказательство этого для любой стратегии в любой честной игре.

• Black-Scholes: цена акции под риск-нейтральной мерой - мартингал
• SGD: градиент с шумом - мартингальная разностная последовательность
• Azuma-Hoeffding: мартингальные концентрационные неравенства в онлайн-обучении
• Задача о разорении: P(достичь N до 0) = k/N вычисляется через мартингал
• Optional Stopping: почему нельзя обыграть казино умной стратегией выхода

От азартной игры к стохастическому анализу

Слово martingale - французский термин для стратегии удвоения ставок, известной с XVIII века. Жозеф Дуб в 1953 году формализовал это понятие через условное ожидание относительно фильтрации. Его книга Stochastic Processes заложила фундамент современной вероятностной теории. Мартингалы стали ключевым инструментом в стохастическом исчислении Ито и финансовой математике - формула Black-Scholes опирается на представление цены опциона как мартингального ожидания.

Что такое мартингал

Формальное определение

SGD сходится потому, что градиентный шум формирует мартингал: $\mathbb{E}[\nabla L(w_t) | w_0,...,w_{t-1}] = $ истинный градиент. Black-Scholes цена опциона - это мартингал относительно риск-нейтральной меры. Фильтрация $\mathcal{F}_0 \subseteq \mathcal{F}_1 \subseteq \ldots$ кодирует накопленную информацию, и $\{M_n\}$ - мартингал, если:

1. Адаптированность: M_n измерима относительно F_n 2. Интегрируемость: E[|M_n|] < ∞ для всех n 3. Честная игра: E[M_{n+1} | F_n] = M_n Следствие (Tower Property): E[M_n] = E[E[M_n | F_{n-1}]] = E[M_{n-1}] = ... = E[M_0] Ожидание мартингала постоянно во времени.

Суб- и супермартингалы

Если неравенство меняется: $E[M_{n+1} \mid \mathcal{F}_n] \geq M_n$ - это **субмартингал** (ожидаемый рост, например богатство в выгодной игре). Если $\leq$ - **супермартингал** (ожидаемый спад). Богатство в казино с комиссией - супермартингал.

Ключевые примеры

S_{n+1} = S_n + xi_{n+1}, поэтому: S_{n+1}^2 = S_n^2 + 2*S_n*xi_{n+1} + xi_{n+1}^2 E[S_{n+1}^2 | F_n] = S_n^2 + 2*S_n*E[xi] + E[xi^2] = S_n^2 + 0 + 1 = S_n^2 + 1 E[S_{n+1}^2 - (n+1) | F_n] = S_n^2 + 1 - n - 1 = S_n^2 - n ✓ Важное следствие: E[S_n^2] = E[M_n] + n = M_0 + n = n Дисперсия симметричного блуждания за n шагов = n.

Numpy: симуляция мартингального свойства

Запуск даёт ~0.0000 в обоих случаях - мартингальное свойство подтверждается численно.

Теорема об остановке

Стратегия: «буду играть, пока не выиграю 1000 рублей, а потом выйду». Звучит разумно. Теорема об остановке говорит: в честной игре это не поможет - ожидаемое состояние в момент выхода равно начальному капиталу.

Условия теоремы

1. T ограничен: T <= N для некоторой константы N (самое простое) 2. E[T] < ∞ и |M_{n+1} - M_n| <= C (ограниченные приращения) 3. E[sup_n |M_{n ∧ T}|] < ∞ (доминированная сходимость) Без условий - теорема НЕВЕРНА. Пример нарушения: удвоение ставок дает T < ∞ п.н., но E[T] = ∞ - теорема неприменима.

Задача о разорении игрока

Классическое применение. Игрок начинает с $k$ долларов, в каждом раунде выигрывает или проигрывает по 1 доллару с вероятностью 1/2. Игра заканчивается при достижении $N$ (победа) или $0$ (разорение). Найти $P(\text{победа})$.

**Ожидаемое время игры** вычисляется через второй мартингал $M_n = S_n^2 - n$: $E[S_T^2 - T] = E[S_0^2] = k^2$ $E[T] = E[S_T^2] - k^2 = Nk - k^2 = k(N-k)$ При k=50, N=100: $E[T] = 50 \cdot 50 = 2500$ ходов.

Нечестная игра: другой мартингал

Если монета нечестная ($p \neq 1/2$), процесс $S_n$ - не мартингал. Но существует функция $f(S_n)$, которая им является.

При P(шаг +1) = p, P(шаг -1) = q = 1-p, p ≠ 1/2: M_n = (q/p)^{S_n} - это мартингал: E[M_{n+1} | F_n] = M_n * (p*(q/p) + q*(p/q)) = M_n * (q + p) = M_n ✓ По OST: (q/p)^N * p_k + 1 * (1-p_k) = (q/p)^k p_k = ((q/p)^k - 1) / ((q/p)^N - 1) При p=0.4, k=40, N=100: q/p = 1.5 p_k = (1.5^40 - 1) / (1.5^100 - 1) ≈ 0.0025 (четверть процента!)

Даже небольшое невыгодное смещение монеты (p=0.4 вместо 0.5) превращает 10%-ные шансы в 0.25% при тех же начальных деньгах. Казино использует именно это.

Неравенства Дуба

Неравенства Дуба отвечают на вопрос: насколько далеко может уйти мартингал за $n$ шагов? Это инструмент, без которого невозможно доказать сходимость SGD или обосновать generalization bounds в ML.

Три формы неравенств

Максимальное неравенство: P(max_{k<=n} M_k >= lambda) <= E[M_n^+] / lambda L^p-неравенство (p > 1): E[(max_{k<=n} M_k)^p] <= (p/(p-1))^p * E[M_n^p] L^2-случай (p=2, самый практичный): E[max_{k<=n} M_k^2] <= 4 * E[M_n^2] Константа (p/(p-1))^p называется константой Дуба. Для p=2: (2/1)^2 = 4. Для p=4: (4/3)^4 ≈ 3.16.

Неравенство часто неточно (bound в 2-3 раза больше реального значения). Это нормально: оно дает **гарантированную** верхнюю оценку для любого мартингала без знания конкретного распределения.

Azuma-Hoeffding: концентрация для ограниченных мартингалов

Если шаги мартингала ограничены: $|M_k - M_{k-1}| \leq c_k$ почти наверное, то отклонение от начального значения концентрируется экспоненциально быстро:

P(|M_n - M_0| >= t) <= 2 * exp(-t^2 / (2 * sum(c_k^2))) Сравнение с Хёфдингом для n i.i.d. переменных с |X_i| <= c: Хёфдинг: P(|S_n/n - mu| >= t) <= 2*exp(-2*n*t^2/c^2) Азума: применим к ЗАВИСИМЫМ переменным! Пример - онлайн-обучение: Регрет после T раундов: R_T = sum(loss_t - loss*) R_T образует субмартингал с |R_t - R_{t-1}| <= 1 => P(R_T >= t*sqrt(T)) <= 2*exp(-t^2/2)

Numpy: проверка максимального неравенства

Мартингалы в ML и финансах

Мартингалы - не абстрактная конструкция. Три конкретных применения: SGD, онлайн-обучение, Black-Scholes.

SGD: мартингальная структура шума

Стохастический градиентный спуск: $w_{t+1} = w_t - \eta g_t$, где $g_t$ - градиент на случайном мини-батче. Шум $\varepsilon_t = g_t - \nabla L(w_t)$ несмещён по условию:

E[g_t - nabla L(w_t) | w_0, ..., w_t] = 0 (несмещённость мини-батча) Накопленное отклонение: D_n = sum_{t=0}^{n-1} epsilon_t D_n - мартингал! По неравенству Азумы-Хёфдинга: P(|D_n| >= lambda * sqrt(n)) <= 2*exp(-lambda^2/2) Именно это используется в доказательствах сходимости SGD: шум в среднем компенсируется, спуск идёт в правильном направлении.

Black-Scholes: цена опциона как мартингальное ожидание

Формула Black-Scholes для call-опциона с ценой исполнения $K$:

Реальная мера P: S_t = S_0 * exp(mu*t + sigma*W_t) dS_t = mu*S_t*dt + sigma*S_t*dW_t (тренд mu!) Смена меры (теорема Гирсанова): mu -> r (безрисковая ставка) При риск-нейтральной мере Q: e^{-rt}*S_t - мартингал dS_t = r*S_t*dt + sigma*S_t*dW_t^Q Цена опциона с выплатой H = max(S_T - K, 0): V_t = e^{-r(T-t)} * E^Q[max(S_T - K, 0) | F_t] Это и есть формула Black-Scholes! Отсутствие арбитража <=> существование меры Q.

Interview: классические вопросы

Классические вопросы на интервью

**Q: Является ли сумма i.i.d. случайных величин с нулевым средним мартингалом?**

Да. $E[S_{n+1} \mid \mathcal{F}_n] = S_n + E[X_{n+1}] = S_n + 0 = S_n$. Независимость $X_{n+1}$ от $\mathcal{F}_n$ - ключевой шаг. Это простейший мартингал в ML-контексте (шум SGD).

**Q: Почему стратегия удвоения ставок не гарантирует выигрыш?**

Для стратегии удвоения $E[T] = \infty$ - условие OST нарушено. При ограниченном капитале $E[M_T] < E[M_0]$. OST: в честной игре без ограничений $E[M_T] = E[M_0]$ - прибыли нет.

**Q: Как связаны мартингалы и отсутствие арбитража в финансах?**

Fundamental Theorem of Asset Pricing: нет арбитража тогда и только тогда, когда существует риск-нейтральная мера Q. При Q дисконтированные цены активов - мартингалы. Цена любого дериватива = $E^Q$[дисконтированная выплата].

Мартингалы - мост между вероятностью и ML

Мартингалы соединяют классическую вероятность, финансовую математику и современный ML.

• Броуновское движение — Следующий урок: W(t) и W(t)^2 - t - непрерывные мартингалы; основа стохастического исчисления
• Цепи Маркова — Гармонические функции - мартингалы; Optional Stopping применяется к hitting times
• Условное ожидание — Предыдущий урок: E[X|F_n] - ключевой инструмент в определении мартингала
• Стохастическое исчисление — Стохастический интеграл Ито - мартингал; теорема Гирсанова меняет меру

Итоги

• **Мартингал:** $E[M_{n+1} \mid \mathcal{F}_n] = M_n$ - ожидаемое значение завтра равно сегодняшнему
• **Следствие:** $E[M_n] = E[M_0]$ - среднее не меняется никогда
• **Примеры:** $S_n$ (блуждание), $S_n^2 - n$, экспоненциальный мартингал
• **OST:** $E[M_T] = E[M_0]$ при подходящих условиях на $T$
• **Разорение:** $P(\text{победа} \mid S_0 = k) = k/N$ - прямое следствие OST
• **Дуб:** $E[\max_k M_k^2] \leq 4 E[M_n^2]$ - контроль максимума
• **ML:** SGD-шум образует MDS; Azuma-Hoeffding; риск-нейтральная мера в Black-Scholes

Вопросы для размышления

• Почему теорема об остановке не позволяет выиграть в казино даже с неограниченным капиталом?
• Для какой функции f процесс M_n = f(S_n) является мартингалом при нечестной монете?
• Как связаны мартингалы и понятие отсутствия арбитража в финансовой математике?
• Почему условие E[T] < ∞ важно в теореме Дуба, а не просто P(T < ∞) = 1?

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

• sp-01