Martingales + Optional Stopping: one line replaces the linear system

If a process is fair on every step, its expected value at any reasonable stopping time equals its starting value. One line replaces solving a linear system.

Method · Martingale Optional Stopping

Prereqs: Markov Chain

Intro

Animated Wiener process showing the self-similar zoom-and-rescale property of Brownian motion paths — Cyp — https://commons.wikimedia.org/wiki/File:Wiener_process_animated.gif · CC BY-SA 3.0 / GFDL · Wikimedia Commons

A martingale is a fair-game process: $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n$. The Optional Stopping Theorem says that under mild regularity, $\mathbb{E}[X_\tau] = \mathbb{E}[X_0]$ for any stopping time $\tau$. The skill is choosing the right martingale: $X_n$ itself for hitting probabilities of a fair walk, $X_n^2 - n$ for expected hitting times. Where first-step analysis solves a linear system over every interior state, OST gives the answer in two lines.

Used in practice

Pricing under Q: the discounted price of every tradable asset is a martingale under the risk-neutral measure — this is the fundamental theorem of asset pricing. Optional stopping gives the fair price at any stopping time.
Gambler's ruin and exotic option pricing: the optional stopping theorem gives the probability of hitting the upper barrier before the lower barrier in a Brownian motion — closed-form barrier option prices.
Interview context: 'If X_t is a martingale and τ is a stopping time, what is E[X_τ]?' — by optional stopping (under regularity), E[X_τ] = X_0. Crucial tool for pricing path-dependent derivatives.

✓ Intro · expand

More examples

A handful of harder problems on the same theme. Click any prompt to reveal the solution sketch.

A drunk pedestrian stands on the 17th metre of a 100-metre-long bridge. On each step he staggers either forward or backward by exactly 1 metre, each with probability $1/2$. (a) What is the probability he reaches the far end (metre 100) before the near end (metre 0)? (b) What is the expected number of steps before he reaches one of the ends?

(a) $17/100 = 0.17$ by the gambler's-ruin formula for a symmetric random walk on $\{0, 1, \dots, N\}$: $P(\text{hit }N \text{ first} \mid X_0 = k) = k/N$. (b) $E[\tau] = k(N - k) = 17 \times 83 = 1411$ steps, from $E[\tau \mid X_0 = k] = k(N - k)$ for symmetric walks via the martingale $S_n^2 - n$ + optional stopping.

Dice-with-reroll game. You roll a standard fair die. The face value is paid out to you. If you roll a 4, 5 or 6 you may choose to roll again (replacing your current payout with the new face value); if you roll 1, 2 or 3 the game stops and you keep that payout. What is the expected payoff of this game played optimally?

$E[\text{payoff}] = \tfrac{14}{3} \approx 4.67$. By Wald's equality, if $N$ is the (stopping) number of rolls until the first $\{1, 2, 3\}$ then $E[N] = 2$ (geometric with $p = 1/2$), and the final payoff is the face value of that stopping roll. Conditional on the stopping roll being in $\{1, 2, 3\}$ uniformly, $E[\text{stop face}] = 2$ — but the optimal policy is to keep an early 4/5/6 if its face value already beats the post-rollover expectation; full DP gives $14/3$.

+ More examples · expand

Martingales + Optional Stopping: one line replaces the linear system

Goals

New Goal

Weekly Missions