Mathematics.

discrete time processes

Optional Stopping Theorem

Stochastic Processes55 minDifficulty7 out of 10

You should know: martingales, markov chains, random walks

Overview

The Optional Stopping Theorem (OST), also called Doob's optional sampling theorem, states that under suitable conditions, the expected value of a martingale at a stopping time T equals its initial value: E[M_T] = E[M_0]. This powerful result has applications to gambling (gambler's ruin), random walks (first passage times), and finance (pricing by risk-neutral expectations). The key subtlety is that naive application can fail for unbounded stopping times, so verifying the integrability conditions is essential.

Intuition

In a fair coin-flipping game, no matter how clever your stopping strategy, you cannot expect to come out ahead. If you decide to stop when your wealth first reaches +10 or -5, your expected wealth at stopping still equals your starting wealth (0). The OST formalizes this: for a fair game (martingale), any stopping rule that does not game the future cannot change the expected outcome. The conditions on T prevent pathological strategies like 'stop only when I am ahead' that exploit the infinite horizon.

Formal Definition

Definition

Let {M_n, F_n} be a martingale and T be a stopping time. The Optional Stopping Theorem gives conditions under which E[M_T] = E[M_0].

T is a stopping time: {T≤n}∈Fn for all n≥0T \text{ is a stopping time: } \{T \le n\} \in \mathcal{F}_n \text{ for all } n \ge 0
Stopping time definition
E[MT]=E[M0]\mathbb{E}[M_T] = \mathbb{E}[M_0]
Optional stopping conclusion
Condition A: T≤N a.s. for some finite N\text{Condition A: } T \le N \text{ a.s. for some finite } N
Bounded stopping time
Condition B: E[T]<∞ and ∣Mn+1−Mn∣≤C a.s.\text{Condition B: } \mathbb{E}[T] < \infty \text{ and } |M_{n+1}-M_n| \le C \text{ a.s.}
Bounded increments + finite mean
Condition C: {Mn∧T} is dominated by an integrable random variable\text{Condition C: } \{M_{n \wedge T}\} \text{ is dominated by an integrable random variable}
Dominated condition

Notation

NotationMeaning
TTStopping time: T is F-measurable and {T <= n} is in F_n
MTM_TMartingale value at the stopping time T
n∧Tn \wedge TMinimum of n and T; used for stopped process M_{n wedge T}

Theorems

Theorem 1: Doob's Optional Stopping Theorem
Let {Mn,Fn} be a martingale and T a stopping time. If any of Conditions A, B, or C holds, then E[MT]=E[M0].\text{Let } \{M_n, \mathcal{F}_n\} \text{ be a martingale and } T \text{ a stopping time. If any of Conditions A, B, or C holds, then } \mathbb{E}[M_T] = \mathbb{E}[M_0].
Theorem 2: Gambler's Ruin via OST
For a simple random walk Sn on {0,1,…,N} with absorbing barriers at 0 and N, starting at k:P(reach N before 0)=k/N.\text{For a simple random walk } S_n \text{ on } \{0,1,\ldots,N\} \text{ with absorbing barriers at 0 and N, starting at } k: \quad P(\text{reach } N \text{ before } 0) = k/N.
Theorem 3: Wald's Identity
If Sn=X1+⋯+Xn with i.i.d. Xi having mean μ and T is a stopping time with E[T]<∞, then E[ST]=μ E[T].\text{If } S_n = X_1+\cdots+X_n \text{ with i.i.d. } X_i \text{ having mean } \mu \text{ and } T \text{ is a stopping time with } \mathbb{E}[T]<\infty{,} \text{ then } \mathbb{E}[S_T] = \mu\,\mathbb{E}[T].

Worked Examples

  1. 1

    S_n is a martingale (fair game). The stopping time T = inf{n: S_n = 0 or S_n = 10} is bounded by the first exit from {0,...,10}.

    E[ST]=E[S0]=5(by OST)\mathbb{E}[S_T] = \mathbb{E}[S_0] = 5 \quad \text{(by OST)}
  2. 2

    Let p = P(reach 10). Then E[S_T] = 10p + 0(1-p) = 10p. Set equal to 5.

    10p=5  ⟹  p=1210p = 5 \implies p = \frac{1}{2}

✓ Answer

P(reach $10 before $0) = 1/2. By symmetry: starting at $5 with barriers at 0 and 10, the probability equals 5/10 = 1/2.

Practice Problems

Mediumapplication

A fair coin is flipped repeatedly. Let T be the first time the cumulative number of heads exceeds the number of tails by 3. Use OST to find E[T].

Mediumfree response

Explain why the OST can fail when E[T] = infinity, providing a concrete counterexample using the simple random walk.

Common Mistakes

Common Mistake

E[M_T] = M_0 holds for any stopping time

OST requires integrability conditions. For a simple random walk, T = first time hitting 1 has E[T] = infinity and E[M_T] = 1 does not equal M_0 = 0.

Common Mistake

Any clever stopping rule can beat a fair game

OST proves that no stopping rule satisfying the integrability conditions can change the expected value of a fair game from its starting value.

Quiz

The Optional Stopping Theorem concludes that E[M_T] = E[M_0] when which condition holds?
In the gambler's ruin problem, starting at position k with absorbing barriers at 0 and N, OST gives the ruin probability as:
Wald's identity states that for i.i.d. increments X_i with mean mu and stopping time T with E[T] < infinity:

Historical Background

The optional stopping theorem was formalized by Joseph Leo Doob in his foundational work on martingale theory in the 1940s and 1950s. The result captures the mathematical principle that you cannot beat a fair game by choosing a clever stopping rule. It generalizes earlier results on the gambler's ruin problem and provides a unified framework for first-passage analysis in Markov chains and Brownian motion.

  1. 1940s

    Doob formalizes the optional stopping theorem as part of martingale theory

    Joseph Leo Doob

  2. 1953

    Doob's monograph establishes OST as a central tool in probability

    Joseph Leo Doob

  3. 1970s

    OST applied to option pricing and mathematical finance

Summary

  • The Optional Stopping Theorem states E[M_T] = E[M_0] for a martingale stopped at T, under conditions ensuring T is not exploiting the infinite future.
  • Three sufficient conditions: T bounded a.s.; bounded increments with finite mean stopping time; dominated stopped process.
  • Gambler's ruin: starting at k with barriers 0 and N, ruin probability = k/N and expected duration = k(N-k), both derived via OST.
  • Wald's identity: E[S_T] = mu * E[T] for i.i.d. increments with mean mu and integrable stopping time T.

References

  1. BookDurrett, R. -- Probability: Theory and Examples, 4th ed., Chapter 4
  2. BookRoss, S. -- Introduction to Probability Models
  3. WebsiteWikipedia -- Optional stopping theorem