Martingales & Optional Stopping

Hard4–5 hrsMartingalesOptional StoppingFair Games

Overview

A martingale is a formal model of a fair game: the conditional expected value never changes. The Optional Stopping Theorem says: if you stop at a bounded time T, the expected value at stopping equals the starting value. This sounds obvious, but it's a powerful computation tool — it converts probability questions into algebra without solving the full path distribution.

How to Recognize

→Fair game — 'no house edge', E[future value | present] = present value
→Need expected stopping time or exit value without full analysis
→Problem asks you to prove something is unbiased or find a probability
→Key phrase: 'on average unchanged' or 'balanced'

Step-by-Step Approach

1.Martingale: E[Xₙ₊₁ | X₀,…,Xₙ] = Xₙ — no expected change
2.Optional Stopping Theorem (OST): E[M_T] = E[M₀] if T is bounded
3.Step 1: Identify what martingale is relevant (Sₙ, Sₙ²−n, or e^(θSₙ))
4.Step 2: Apply OST at the stopping time to get equations
5.Step 3: Use P(hit a) + P(hit −b) = 1 to solve the system

Key Formulas

01OST:

E[M_T] = E[M_0] = M_0

T

is a.s. bounded

02Fair walk

S_n

E[S_T] = S_0

→ absorption probability equation

S_n^2 - n

is a martingale:

E[S_T^2 - T] = 0

→ expected time equation

04Wald's identity:

E[S_T] = E[T] \cdot E[X_1]

for i.i.d. steps, any stopping time

Worked Examples

0Quick Example

Fair walk from 0, stop at +a or −b. OST on Sₙ: 0 = a·P(hit +a) − b·P(hit −b). With total prob = 1: P(hit +a) = b/(a+b).

Problem

Fair walk from 0, absorbing barriers at +a and −b. Find P(absorbed at +a) using the OST.

Solution

Define Sₙ = position at time n. Sₙ is a martingale (fair walk).

Stopping time T = first time we hit +a or −b.

OST: E[S_T] = S₀ = 0. But E[S_T] = a·P(hit a) + (−b)·P(hit −b).

Also P(hit a) + P(hit −b) = 1, so P(hit −b) = 1 − P(hit a).

Substituting: 0 = a·P(hit a) − b·(1−P(hit a)). Solve: b = (a+b)·P(hit a).

P(hit +a) = b/(a+b). E.g., a=3, b=2: P(hit +3) = 2/5 = 40%.

Answer

$P(\text{hit} +a) = b/(a+b)$ . OST on the position martingale gives the absorption probabilities directly.

Common Mistakes

!
Applying OST without checking that T is bounded. If T can be infinite, OST may fail (gambler's ruin with p≠1/2 has E[T]=∞ in some cases).
!
Confusing Sₙ martingale (gives absorption probs) with Sₙ²−n martingale (gives expected time).
!
Forgetting the '−n' term in Sₙ²−n. The process Sₙ² alone is NOT a martingale.

Practice Problems

Click "Show Answer" to reveal

Fair walk from 0, stop at +5 or −2. Find P(hit +5) and E[T].

Hint: OST on Sₙ for P(hit +5). OST on Sₙ²−n for E[T].

Is the process Xₙ = (−1)ⁿ a martingale?

Hint: Check if E[Xₙ₊₁|Xₙ] = Xₙ.

Back to Study Plan

Brownian Motion & Hitting Times First-Step Analysis