BrevFeed
Sign in

54. Martingales

🎬 Video · 16 min
💡 Every code box below is live — edit it and hit Run.

A martingale is the mathematical formalisation of a fair game: a process whose expected future value, given everything you know now, equals its present value.

It's the last idea in this section, and it turns out to be the one that explains why several plausible-sounding gambling and investment strategies cannot work.

The definition

A process X_0, X_1, X_2, \dots is a martingale with respect to an information sequence \mathcal{F}_n if:

E[|X_n|] < \infty \qquad \text{and} \qquad E[X_{n+1} \mid \mathcal{F}_n] = X_n

Read the second condition carefully: given everything known up to time n, the best prediction of tomorrow is today's value. No trend, no drift, no edge.

\mathcal{F}_n is the filtration — formally the \sigma-algebra (§9) generated by the history, informally "everything observable by time n".

Two relatives:

  • Submartingale: E[X_{n+1} \mid \mathcal F_n] \ge X_n — favourable, drifts up.
  • Supermartingale: E[X_{n+1} \mid \mathcal F_n] \le X_n — unfavourable, drifts down.

(The naming is backwards from intuition. A supermartingale is the one that's bad for you.)

Iterating the definition gives E[X_n] = E[X_0] for all n: the expectation never changes.

Examples

A fair random walk. S_n = \sum X_i with E[X_i] = 0:

E[S_{n+1} \mid \mathcal F_n] = S_n + E[X_{n+1}] = S_n \quad\checkmark

Brownian motion. W(t) is a continuous-time martingale, for the same reason.

A gambler's wealth in a fair game. Whatever the betting strategy, so long as each individual bet is fair.

Likelihood ratios. \prod \frac{q(X_i)}{p(X_i)} is a martingale when the data really comes from p — which is the engine behind sequential testing.

Not martingales: a walk with drift (sub- or supermartingale), and a casino game with a house edge (supermartingale — hence the terminology).

The optional stopping theorem

This is the result that does the work.

Let \tau be a stopping time — a rule for when to stop that uses only information available at the time, never the future. ("Stop when I'm up ₹100" is valid; "stop at the peak" is not.)

Then, under mild conditions (bounded \tau, or bounded X, or bounded increments with E[\tau] < \infty):

E[X_\tau] = E[X_0]

You cannot beat a fair game by choosing when to quit. No stopping rule creates an edge, because the expectation was already constant and stopping doesn't change it.

That's a genuinely strong statement, and it's the formal refutation of a whole family of systems.

The martingale betting strategy

The classic: bet ₹1; if you lose, bet ₹2; then ₹4, ₹8, and so on. The first win recovers everything plus ₹1.

It seems to guarantee profit — you win eventually with probability 1.

Here's why it fails, and the failure is instructive because the strategy is not actually wrong about the probability. You do win with probability 1. But:

  • Unbounded capital is required. After k losses you've staked 2^k - 1 and must now stake 2^k. Twenty losses in a row — probability about 1 in a million, and it will happen if you play long enough — requires over ₹1,000,000 to continue.
  • The expected loss when you fail is exactly the expected gain when you succeed. With any finite bankroll, optional stopping applies and E[\text{final wealth}] = E[\text{initial wealth}].
  • Table limits make the required doubling impossible in practice.

The pattern is the same as gambler's ruin (§8, lesson 3): you win a small amount with high probability and lose a catastrophic amount with small probability, and the two balance exactly.

This shape recurs constantly — selling deep out-of-the-money options, over-leveraged carry trades, any strategy with a "steady returns, rare disaster" profile. A long run of small wins is not evidence of an edge.

Convergence

The martingale convergence theorem: if X_n is a martingale bounded in L^1 (i.e. \sup_n E[|X_n|] < \infty), then X_n converges almost surely to some limit X_\infty.

Note this is not true of the unbounded fair random walk, which oscillates forever without converging — its E[|S_n|] grows like \sqrt n. Boundedness is essential.

The theorem is the workhorse behind Bayesian consistency results, branching process extinction, and stochastic approximation.

Worked example

A gambler has ₹100 and bets ₹1 per fair coin flip, stopping at ₹0 or ₹200. What's the probability of reaching ₹200?

Wealth W_n is a martingale (each bet is fair), the stopping time \tau is valid, and wealth is bounded in [0, 200] — so optional stopping applies:

E[W_\tau] = E[W_0] = 100

At stopping, wealth is either 0 or 200. Writing p for the probability of reaching 200:

200p + 0(1-p) = 100 \implies p = 0.5

Exactly one half — which is k/N = 100/200, the gambler's ruin formula from two lessons ago. Optional stopping derives it in one line.

Now the same question with a house edge, p_{\text{win}} = 0.49 per flip. Wealth is now a supermartingale: E[W_{n+1} \mid \mathcal F_n] < W_n. Optional stopping gives an inequality instead:

E[W_\tau] \le E[W_0] = 100

so the probability of reaching 200 is at most 0.5 — and in fact it collapses to about 1.8 \times 10^{-2}. Working it out with the gambler's-ruin formula, where r = q/p = 0.51/0.49:

P = \frac{1 - r^{100}}{1 - r^{200}} = \frac{1 - 54.63}{1 - 2984.1} = 0.0180

Under 2%, against 50% for the fair game. A 1% edge over the ~10,000 flips this game takes is utterly decisive.

And the martingale doubling strategy on the fair game? Still exactly 0.5 — by optional stopping, because no strategy changes E[W_\tau]. It changes the shape of the outcome distribution (many small wins, rare total loss) but not its mean.

Doing it in Python

Confirming the defining property:

import numpy as np

rng = np.random.default_rng(0)
trials, n = 200_000, 50

# Fair random walk
steps = rng.choice([-1, 1], size=(trials, n))
S = np.cumsum(steps, axis=1)

print(f"{'n':>6} {'E[S_n]':>10}   (a martingale keeps this at 0)")
for i in (0, 9, 24, 49):
    print(f"{i+1:>6} {S[:, i].mean():>10.4f}")

# The conditional property: given S_n = s, what is E[S_{n+1}]?
print("\nE[S_31 | S_30 = s] for various s:")
for s in (-6, -2, 0, 2, 6):
    mask = S[:, 29] == s
    if mask.sum() > 100:
        print(f"  s = {s:>3}: {S[mask, 30].mean():>8.4f}   (should equal {s})")

Optional stopping — no rule creates an edge:

import numpy as np

rng = np.random.default_rng(1)

def play(strategy, trials, rng, max_steps=5_000):
    finals = []
    for _ in range(trials):
        w, n = 100.0, 0
        while strategy(w, n) and n < max_steps:
            w += 1 if rng.random() < 0.5 else -1
            n += 1
        finals.append(w)
    return np.array(finals)

strategies = {
    "stop at 0 or 200":     lambda w, n: 0 < w < 200,
    "stop when up 10":      lambda w, n: w < 110 and w > 0,
    "stop after 500 flips": lambda w, n: n < 500 and w > 0,
    "stop when up 1":       lambda w, n: w < 101 and w > 0,
}
for name, s in strategies.items():
    finals = play(s, 2_000, rng)
    print(f"{name:>22}: mean final wealth {finals.mean():>8.2f}  "
          f"(started at 100)")

print("\nEvery stopping rule gives the same expected wealth. That is the theorem.")

The doubling strategy — why it looks like it works:

import numpy as np

rng = np.random.default_rng(2)

def martingale_strategy(bankroll, target_profit, rng, max_rounds=1000):
    wealth, bet = bankroll, 1
    for _ in range(max_rounds):
        if wealth >= bankroll + target_profit:
            return wealth
        if bet > wealth:                      # cannot cover the next double
            return wealth
        if rng.random() < 0.5:
            wealth += bet
            bet = 1
        else:
            wealth -= bet
            bet *= 2
    return wealth

for bankroll in (100, 1_000, 10_000):
    finals = np.array([martingale_strategy(bankroll, 10, rng) for _ in range(3_000)])
    won = (finals >= bankroll + 10).mean()
    print(f"bankroll {bankroll:>6}: reached target {won:>7.2%} of the time, "
          f"mean final {finals.mean():>9.2f} (started {bankroll})")

print("\nIt wins almost every time -- and the rare catastrophic loss exactly")
print("cancels all those wins. The mean never moves off the starting wealth.")

Fair versus a house edge, through the same lens:

import numpy as np

rng = np.random.default_rng(3)

def ruin_prob(start, target, p_win, trials, rng):
    wins = 0
    for _ in range(trials):
        w = start
        while 0 < w < target:
            w += 1 if rng.random() < p_win else -1
        wins += (w == target)
    return wins / trials

start, target = 20, 40           # smaller numbers so it runs quickly
for p in (0.50, 0.48, 0.45):
    sim = ruin_prob(start, target, p, 4_000, rng)
    if p == 0.5:
        theory = start / target
    else:
        r = (1 - p) / p
        theory = (1 - r**start) / (1 - r**target)
    kind = "martingale" if p == 0.5 else "supermartingale"
    print(f"p={p}: P(reach {target}) sim {sim:.4f}  theory {theory:.4f}   ({kind})")

print("\nFair game -> equality (E[W_tau] = W_0). Edge against you -> inequality.")

Your turn

1. Is a random walk with drift \mu = 0.1 per step a martingale?

2. Why can't the doubling strategy beat a fair game?

3. X_n is a martingale with X_0 = 5. What is E[X_{100}]?

Solutions

1. No — it's a submartingale.

E[S_{n+1} \mid \mathcal F_n] = S_n + 0.1 > S_n

The expected value strictly increases, so the fair-game condition fails in the favourable direction.

S_n - 0.1n is a martingale, though — subtracting the drift restores the property. That's the standard technique: compensate a process by its drift and what remains is a martingale, which is exactly how the Doob decomposition works.

2. By the optional stopping theorem. Wealth in a fair game is a martingale, so for any valid stopping rule \tau:

E[W_\tau] = E[W_0]

The doubling strategy is a stopping rule — stop at the first win — so it cannot change the expected final wealth. Full stop.

What it does change is the shape of the distribution. With a bankroll of ₹1,000 you win ₹10 about 99.9% of the time and lose ₹1,000 about 0.1% of the time:

0.999(+10) + 0.001(-1000) \approx +9.99 - 1.00 \approx 0

Those balance exactly, and the appeal of the strategy is entirely that you rarely see the losing branch. A hundred consecutive wins feels like proof the system works; it's simply the high-probability branch showing up.

The general lesson: a high win rate is not an edge. Any strategy can trade win frequency against loss severity while leaving the expectation untouched.

3. E[X_{100}] = 5.

By the martingale property and the tower rule, the expectation is constant:

E[X_{n+1}] = E\big[E[X_{n+1} \mid \mathcal F_n]\big] = E[X_n]

so E[X_{100}] = E[X_0] = 5.

Note what this does not say. X_{100} itself could be anywhere — the distribution may have spread out enormously — and the process need not converge. The fair random walk has E[S_n] = 0 forever while its spread grows like \sqrt n, wandering ever further from its unchanging mean.

Check yourself in code

Confirm the martingale property holds for a fair random walk and that optional stopping gives the gambler's ruin answer.

Print exactly this:

E[S_50] 0.0225
martingale: True
P(reach 200) 0.5
optional stopping predicts 0.5

Use default_rng(0) with 200000 walks of 50 steps for the first part, and default_rng(1) with 4000 gambler's-ruin runs from 100 with barriers at 0 and 200. Round E[S_{50}] to 4 decimal places and the probability to 4. Report martingale: True if |E[S_{50}]| < 0.05.

import numpy as np

rng = np.random.default_rng(0)
S = np.cumsum(rng.choice([-1, 1], size=(200_000, 50)), axis=1)

mean_50 = S[:, 49].mean()
print("E[S_50]", round(mean_50, 4))
print("martingale:", bool(abs(mean_50) < 0.05))

# With default_rng(1), run 4000 gambler's-ruin simulations starting at 100
# with barriers at 0 and 200, and report the fraction reaching 200.

import numpy as np

rng = np.random.default_rng(0)
S = np.cumsum(rng.choice([-1, 1], size=(200_000, 50)), axis=1)

mean_50 = S[:, 49].mean()
print("E[S_50]", round(mean_50, 4))
print("martingale:", bool(abs(mean_50) < 0.05))

rng2 = np.random.default_rng(1)
wins = 0
for _ in range(4_000):
    w = 100
    while 0 < w < 200:
        w += 1 if rng2.random() < 0.5 else -1
    wins += (w == 200)

print("P(reach 200)", round(wins / 4_000, 4))
print("optional stopping predicts 0.5")

A martingale is a fair game: the expected next value equals the current one, given everything known. Its expectation never changes, and the optional stopping theorem says no valid stopping rule can change it either — which is why the doubling strategy, and every relative of it, trades win frequency for loss severity without creating an edge.

That closes §8. Next: the measure-theoretic foundations that make all of this rigorous.

← Previous Next →