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

Мартингал — стохастический процесс без «систематического дрейфа»: ожидаемое будущее значение равно текущему. Это математическое воплощение «честной игры» и основа финансовой математики.

Мартингалы

Определение: Последовательность {Mₙ, Fₙ} — мартингал относительно фильтрации {Fₙ}, если: (1) Mₙ Fₙ-измерима; (2) E[|Mₙ|] < ∞; (3) E[Mₙ₊₁|Fₙ] = Mₙ.

Примеры: Симметричное случайное блуждание: Sₙ = X₁+...+Xₙ, Xᵢ = ±1. E[Sₙ₊₁|Fₙ] = Sₙ. Mₙ = Sₙ² - n — тоже мартингал (подходит для вычисления E[τ]).

Теоремы о мартингалах

Теорема об опциональной остановке (Дуб): При достаточных условиях для мартингала Mₙ и времени остановки τ: E[M_τ] = E[M₀]. «В честной игре ожидаемый выигрыш = 0».

Условия: τ — ограничено, или |Mₙ| ≤ C, или E[τ] < ∞ и E[|Mₙ₊₁-Mₙ||Fₙ] ≤ C.

Применение — задача разорения: Игрок с начальным капиталом k, выигрывает/проигрывает 1 руб с вероятностью 1/2. Остановится при 0 (разорение) или N. E[τ] = k(N-k). P(разорение) = (N-k)/N. Это следует из мартингальных свойств S_n и Sₙ² - n.

Оптимальная остановка

Задача: Наблюдаем X₁, X₂,... и хотим остановиться в момент τ, максимизируя E[X_τ].

Задача секретарши: n кандидатов. Отвергнутый кандидат недоступен. Оптимальная стратегия: отвергнуть первые [n/e] ≈ n/e кандидатов, затем принять первого лучше всех предыдущих. P(успеха) → 1/e ≈ 0.368.

Уравнение оптимальной остановки: V(x) = max(x, E[V(X')]). Продолжать, пока E[V(X')] > x. Остановиться, когда x ≥ E[V(X')].

Задание: (а) Докажите, что Sₙ² - n — мартингал для простого симметричного блуждания. Примените теорему Дуба для вычисления E[τ], где τ = min{n: Sₙ ∈ {-a, b}}. (б) В задаче секретарши с n=10: симулируйте оптимальную стратегию 10000 раз. Насколько близко P(успеха) к 1/e? (в) Финансы: опцион на покупку. Дерево биномиальных цен. Найдите цену через нейтральную к риску меру.

Теория оптимальной остановки: общий подход

Задача: Дана последовательность X₁, X₂,... Выбрать τ (правило остановки) для максимизации E[X_τ]. Принцип Беллмана: V_n(x) = max(x, E[V_{n+1}(X_{n+1})|X_n=x]). Остановиться при x ≥ V_{n+1}^* (порог Неймана).

Задача секретарши (проблема остановки): n кандидатов в случайном порядке. После каждого — принять или отклонить навсегда. Оптимальная стратегия: пропустить первые ⌊n/e⌋ кандидатов, затем принять первого лучше предыдущих. P(успеха) → 1/e ≈ 0.368.

Неравенства для мартингалей

Неравенство максимума Дуба: P(max_{k≤n} Mₖ ≥ λ) ≤ E[|Mₙ|]/λ для субмартингала |Mₙ|. Это мартингальный аналог неравенства Маркова. В L² версии: E[(max_{k≤n} Mₙ)²] ≤ 4E[Mₙ²].

Теорема сходимости мартингалей (Дуб): Если supₙ E[|Mₙ|] < ∞, то Mₙ → M∞ п.н. Субмартингал ограниченный в L¹ сходится п.н. Применение: сходимость апостериорных вероятностей в байесовском обновлении (мартингал Дуба P(θ|X₁,...,Xₙ) сходится к P(θ|X∞)).

Теория оптимальной остановки

Задача: Наблюдаем X₁,X₂,... Выбрать момент остановки τ (адаптированный к фильтрации) для максимизации E[Xτ]. Принцип Снелла: Наименьший супермартингал, мажорирующий выплату G(Xₙ). Оптимально останавливаться, когда Zₙ = Gₙ (оболочка Снелла достигается).

Задача секретаря: n кандидатов, наблюдаем относительные ранги, можем принять или отклонить. Оптимальная стратегия: пропустить первых n/e кандидатов, затем принять первого, который лучше всех ранее виденных. Вероятность выбора лучшего → 1/e ≈ 0.368. Классическая задача оптимальной остановки.

Опциональная теорема о выборке (Doob's OST)

Для мартингала Mₙ и момента остановки τ: при условиях регулярности E[Mτ] = E[M₀]. Это позволяет вычислять ожидаемое время достижения для случайных блужданий. Например, для СБ S₀=a: E[τ(0 или b)] = a(b−a), E[S_{τ}] = a. Применение в азартных играх: любая стратегия остановки не изменяет ожидаемый выигрыш в честной игре.

Stochastic dominance и сравнение распределений

Первый порядок: F доминирует G (F ≻₁ G), если F(x) ≤ G(x) для всех x. Эквивалентно: E[u(X)] ≥ E[u(Y)] для всех неубывающих u. Второй порядок: F ≻₂ G, если ∫{-∞}^x F(t)dt ≤ ∫{-∞}^x G(t)dt. Эквивалентно: E[u(X)] ≥ E[u(Y)] для всех неубывающих вогнутых u. Применяется в теории портфеля: инвестор-оптимизатор не выберет F-доминируемый актив.

Теория мартингалов в дискретной оптимизации

Мартингальная аппроксимация алгоритмов: MCTS (Monte Carlo Tree Search) использует последовательность оценок позиции как мартингал. При достаточном числе симуляций — сходится к истинному значению (теорема Лажерне). Случайные блуждания и минимальное покрывающее дерево: ожидаемое время первого визита всех вершин в связном графе — через резистивное расстояние Кирхгофа (C(u,v) = R_eff(u,v)·2|E|). Применяется в алгоритмах приближённого подсчёта.

Теорема Дуба-Мейера и компенсатор

Любой субмартингал Xₙ = Mₙ + Aₙ, где Mₙ — мартингал, Aₙ — возрастающий предсказуемый процесс (компенсатор). Разложение Дуба-Мейера: единственное. Для квадратичного мартингала: Aₙ = Σ E[(Mₖ−Mₖ₋₁)²|Fₖ₋₁] = предсказуемая квадратическая вариация. Применяется в стохастическом интегрировании и финансах для вычисления P&L.

Численный пример: теорема Дуба об остановке

Задача: Симметричное случайное блуждание, P(+1)=P(−1)=0.5, начало S₀=3. Τ=min{n: Sₙ=0 или Sₙ=5}. Найти P(S_τ=5).

Шаг 1: Sₙ — мартингал: E[Sₙ₊₁|Sₙ]=Sₙ (честная игра, нет систематического сноса).

Шаг 2: По теореме об остановке (при выполнении условий Дуба): E[S_τ]=S₀=3.

Шаг 3: S_τ принимает значения {0,5}. Пусть p=P(S_τ=5). Тогда E[S_τ]=p·5+(1−p)·0=5p.

Шаг 4: Из 5p=3: p=3/5=0.6. Вероятность разорения: 1−p=0.4. Разложение Дуба-Мейера: предсказуемый компенсатор ₙ = n (квадратическая вариация = счётчик шагов). P&L трейдера, следующего мартингальной стратегии, не имеет систематического роста.