Martingales and the Theory of Optimal Stopping

A martingale is a stochastic process without “systematic drift”: the expected future value is equal to the current value. It is the mathematical embodiment of a “fair game” and the foundation of financial mathematics.

Martingales

Definition: The sequence {Mₙ, Fₙ} is a martingale relative to the filtration {Fₙ} if: (1) Mₙ is Fₙ-measurable; (2) E[|Mₙ|] < ∞; (3) E[Mₙ₊₁|Fₙ] = Mₙ.

Examples: Symmetric random walk: Sₙ = X₁ + ... + Xₙ, Xᵢ = ±1. E[Sₙ₊₁|Fₙ] = Sₙ. Mₙ = Sₙ² - n is also a martingale (suitable for calculating E[τ]).

Martingale Theorems

Optional Stopping Theorem (Doob): Under sufficient conditions for the martingale Mₙ and stopping time τ: E[M_τ] = E[M₀]. “In a fair game the expected gain is zero.”

Conditions: τ is bounded, or |Mₙ| ≤ C, or E[τ] < ∞ and E[|Mₙ₊₁ - Mₙ||Fₙ] ≤ C.

Application — Ruin Problem: A player with initial capital k wins/loses 1 ruble with probability 1/2. Stops at 0 (ruin) or N. E[τ] = k(N - k). P(ruin) = (N - k)/N. This follows from martingale properties of S_n and Sₙ² - n.

Optimal Stopping

Problem: We observe X₁, X₂,... and want to stop at time τ, maximizing E[X_τ].

Secretary Problem: n candidates. A rejected candidate is unavailable. Optimal strategy: reject the first [n/e] ≈ n/e candidates, then accept the first better than all previous ones. P(success) → 1/e ≈ 0.368.

Optimal Stopping Equation: V(x) = max(x, E[V(X')]). Continue while E[V(X')] > x. Stop when x ≥ E[V(X')].

Exercise: (a) Prove that Sₙ² - n is a martingale for the simple symmetric random walk. Apply Doob's theorem to compute E[τ], where τ = min{n: Sₙ ∈ {-a, b}}. (b) In the secretary problem with n=10: simulate the optimal strategy 10000 times. How close is P(success) to 1/e? (c) Finance: call option. Binomial price tree. Find price via risk-neutral measure.

Optimal Stopping Theory: General Approach

Problem: Given sequence X₁, X₂,... Choose τ (stopping rule) to maximize E[X_τ]. Bellman's Principle: V_n(x) = max(x, E[V_{n+1}(X_{n+1})|X_n=x]). Stop at x ≥ V_{n+1}^* (Neiman threshold).

Secretary Problem (Stopping Problem): n candidates in random order. After each — accept or reject forever. Optimal strategy: skip first ⌊n/e⌋ candidates, then accept the first better than all previous. P(success) → 1/e ≈ 0.368.

Inequalities for Martingales

Doob’s Maximum Inequality: P(max_{k≤n} Mₖ ≥ λ) ≤ E[|Mₙ|]/λ for submartingale |Mₙ|. This is the martingale analog of Markov’s inequality. In L² version: E[(max_{k≤n} Mₙ)²] ≤ 4E[Mₙ²].

Martingale Convergence Theorem (Doob): If supₙ E[|Mₙ|] < ∞, then Mₙ → M∞ almost surely. A submartingale bounded in L¹ converges almost surely. Application: convergence of posterior probabilities in Bayesian updating (Doob martingale P(θ|X₁,...,Xₙ) converges to P(θ|X∞)).

Theory of Optimal Stopping

Problem: We observe X₁, X₂,... Choose a stopping moment τ (adapted to filtration) to maximize E[Xτ]. Snell Principle: The smallest supermartingale dominating the payoff G(Xₙ). Optimal to stop when Zₙ = Gₙ (Snell envelope is reached).

Secretary Problem: n candidates, we observe relative ranks, can accept or reject. Optimal strategy: skip first n/e candidates, then accept the first who is better than all seen previously. Probability of choosing the best → 1/e ≈ 0.368. Classic optimal stopping problem.

Optional Sampling Theorem (Doob's OST)

For a martingale Mₙ and stopping moment τ: under regularity conditions E[Mτ] = E[M₀]. This allows computing expected hitting times for random walks. For example, for RW S₀=a: E[τ(0 or b)] = a(b−a), E[S_{τ}] = a. Application in gambling: any stopping strategy does not change the expected gain in a fair game.

Stochastic Dominance and Comparison of Distributions

First Order: F dominates G (F ≻₁ G), if F(x) ≤ G(x) for all x. Equivalent: E[u(X)] ≥ E[u(Y)] for all non-decreasing u. Second Order: F ≻₂ G, if ∫{-∞}^x F(t)dt ≤ ∫{-∞}^x G(t)dt. Equivalent: E[u(X)] ≥ E[u(Y)] for all non-decreasing concave u. Applied in portfolio theory: an optimizing investor will not choose an F-dominated asset.

Martingale Theory in Discrete Optimization

Martingale Approximation of Algorithms: MCTS (Monte Carlo Tree Search) uses the sequence of position estimates as a martingale. With sufficient simulation number — converges to the real value (Lajerne’s theorem). Random walks and minimum covering tree: expected time of first visiting all vertices in a connected graph — via Kirchhoff’s resistive distance (C(u,v) = R_eff(u,v)·2|E|). Applied in approximate counting algorithms.

Doob-Meyer Theorem and Compensator

Any submartingale Xₙ = Mₙ + Aₙ, where Mₙ is a martingale, Aₙ is an increasing predictable process (compensator). Doob-Meyer decomposition: unique. For quadratic martingale: Aₙ = Σ E[(Mₖ − Mₖ₋₁)²|Fₖ₋₁] = predictable quadratic variation. Applied in stochastic integration and finance for P&L calculation.

Numerical Example: Doob's Stopping Theorem

Problem: Symmetric random walk, P(+1) = P(−1) = 0.5, starting S₀ = 3. Τ = min{n: Sₙ = 0 or Sₙ = 5}. Find P(S_τ = 5).

Step 1: Sₙ is a martingale: E[Sₙ₊₁|Sₙ] = Sₙ (fair game, no systematic drift).

Step 2: By stopping theorem (with Doob’s conditions): E[S_τ] = S₀ = 3.

Step 3: S_τ takes values {0,5}. Let p = P(S_τ = 5). Then E[S_τ] = p·5 + (1−p)·0 = 5p.

Step 4: From 5p = 3: p = 3/5 = 0.6. Probability of ruin: 1−p = 0.4. Doob-Meyer decomposition: predictable compensator <S>ₙ = n (quadratic variation = step counter). P&L of a trader following a martingale strategy does not have systematic growth.