Martingales and Stopping

A martingale is not a kind of randomness. It is a kind of promise about randomness — the promise that, whatever has already happened, the next increment is worth nothing in conditional expectation. Stopping asks how far that promise extends when the time of reckoning is itself random.

The fair game

Work in discrete time on a probability space with a filtration: an increasing family ${\mathcal{ℱ}}_0\subseteq {\mathcal{ℱ}}_1\subseteq \cdots$ of σ-algebras, where ${\mathcal{ℱ}}_n$ records the information available at time $n$. A real-valued process $X_n$ adapted to this filtration, with for every $n$, is a martingale when [1]

almost surely. The conditional expectation is the whole content of the definition. Given the available information, the conditional mean of tomorrow’s value is today’s value. Replace the equality with $\ge$ and the process is a submartingale; with $\le$, a supermartingale. These are statements about conditional means, not about the direction of every realised step.1

Iterating (1) and using the tower property of conditional expectation gives

and this is where the trouble starts. Equation (2) holds for every fixed time. The gambler, however, does not play until a fixed time. The gambler plays until something happens — until the money doubles, until the money is gone, until the mood turns. May a random time be substituted into (2), and what has to be true for the substitution to survive?

Stopping without foresight

A rule for quitting has to be executable with the information then available. “Sell at the highest price of the year” is easy to write after December. It is generally not a rule one can carry out in March.

At time $n$ the observer must be able to answer “have I stopped?” using ${\mathcal{ℱ}}_n$ alone. The first time an adapted price process crosses a level is a stopping time. The last crossing before a fixed horizon generally is not: identifying it may require later observations. [1]2

Given a stopping time, the natural object is the process frozen at the moment of stopping. Write $n\wedge \tau$ for the smaller of the two and define the stopped process

The stopped process has increments ${\mathbb{𝟙}}_{\{k\le \tau \}}(X_k-X_{k-1})$. The event $\{k\le \tau \}$ is the complement of $\{\tau \le k-1\}$, so the indicator is known at time $k-1$: a stake placed before the coin lands. It is bounded, and the martingale increment is integrable with conditional mean zero. Thus $X_{n\wedge \tau }$ is again an integrable martingale at every finite $n$, even when $\tau$ can be infinite. [1]

That looks like victory, and it is the reason the theorem in the next section is so often misquoted. Equation (4) gives $E[X_{n\wedge \tau }]=E[X_0]$ for each finite $n$. What we want is the same statement with $X_{\tau }$ in place of $X_{n\wedge \tau }$. Between the two lies a limit, and limits and expectations do not commute for free.

The optional stopping theorem

There are several ways to justify that limit. Keeping them separate makes the theorem easier to use. [1] [2]

1. (i) There is a deterministic finite $N$ with $\tau \le N$ almost surely.
2. (ii) The family $\{X_{n\wedge \tau }:n\ge 0\}$ is uniformly integrable. In particular, this holds if $|X_{n\wedge \tau }|\le Y$ for all $n$ almost surely, for some integrable $Y\ge 0$.
3. (iii) and there is a deterministic such that $|X_k-X_{k-1}|\le c$ almost surely for every $k\ge 1$.

Play independent fair coin tosses, doubling the stake after every loss, and stop at the first win. Start with net gain zero. Each finite-time stopped gain is integrable and is a martingale, but $X_{\tau }=1$ almost surely. Here $P(\tau >n)=2^{-n}$ and $E[\tau ]=2$: finite mean duration alone does not rescue (5). The stakes are unbounded, the stopping time is not bounded by a deterministic horizon, and the stopped gains are not uniformly integrable. [1]4

Ruin, and what it costs

Let $S_n$ be a simple symmetric random walk started at zero, and let $\tau$ be the first time it reaches $-a$ or $b$, where $a,b$ are positive integers. To check finiteness, group the independent tosses into stretches of $a+b$ steps. From any interior site, a stretch of all upward steps forces exit; its probability is $2^{-(a+b)}$. Hence $\tau$ has a geometric tail bound over these stretches and . The stopped walk lies between $-a$ and $b$, so condition (ii) applies. If $p=P(S_{\tau }=b)$, (5) reads $pb-(1-p)a=0$. [2]

The first half of (6) is one line of algebra. For the second, independence, mean zero and unit second moment of the increments make $S_n^2-n$ a martingale. Apply bounded optional stopping to $\tau \wedge n\le n$: $E[\tau \wedge n]=E[S_{\tau \wedge n}^2]$. The left side tends to $E[\tau ]$ by monotone convergence; the right side tends to $E[S_{\tau }^2]$ by bounded convergence. Substituting the exit probabilities gives $E[\tau ]=p{b}^2+(1-p)a^2=ab$. We have not assumed the formula for the mean duration in order to prove it.

The table makes the tradeoff visible. Here $a$ is the initial bankroll and $b$ the desired net gain, not the final bankroll. With $a=b$, reaching the upper barrier doubles the initial money. Increasing the target reduces the chance of success and increases the mean duration.

Checking it by simulation

Simulation can check the scale of both quantities in (6); it does not prove them. This example uses a fixed seed so that its output can be reproduced.

from random import Random

def ruin(a, b, trials=20_000, seed=2026):
    """Estimate P(hit +b before -a) and the mean exit time."""
    if any(type(v) is not int or v <= 0 for v in (a, b, trials)):
        raise ValueError("a, b and trials must be positive integers")
    rng = Random(seed)
    wins = steps = 0
    for _ in range(trials):
        x = t = 0
        while -a < x < b:
            x += rng.choice((-1, 1))
            t += 1
        wins += x == b
        steps += t
    return wins / trials, steps / trials

print(ruin(10, 40))    # compare with the exact values (0.2, 400)

A cousin of the same argument gives Wald’s identity. Let ${\xi }_k$ be independent, identically distributed real random variables with , set $S_0=0$ and $S_n=\sum _{k=1}^n{\xi }_k$, and take ${\mathcal{ℱ}}_n=\sigma ({\xi }_1,\dots ,{\xi }_n)$. If $\tau$ is a stopping time for this filtration and , then [2]5

The assumptions in (7) do more than make $S_n-nE[{\xi }_1]$ a martingale. Since $\{\tau \ge k\}\in {\mathcal{ℱ}}_{k-1}$ is independent of ${\xi }_k$, Tonelli’s theorem gives . This random sum dominates every $|S_{\tau \wedge n}|$. Bounded optional stopping applied to $S_n-nE[{\xi }_1]$ at $\tau \wedge n\le n$, followed by dominated and monotone convergence, proves the identity. No bound on individual increments is required; the integrable domination has been proved instead. [2]

How far a fair game wanders

Optional stopping controls the value at a moment. The next result controls the whole trajectory, and it does so by the same device: choose the right stopping time and let the theorem do the work.

The terminal expectation controls the chance of a large excursion. To obtain the $L^2$ bound, one needs a stronger estimate, not the square of (8). For a real square-integrable martingale $M_k$, write $M_n^{\ast }=\underset{0\le k\le n}{max}|M_k|$. Apply bounded conditional optional sampling to the submartingale $|M_k|$ at its first crossing of $\lambda$, capped at $n$. The crossing event belongs to the information at that time, so [2]

Almost-sure convergence under the weaker assumption is a separate theorem. Doob’s upcrossing inequality bounds the expected number of crossings of each interval with rational endpoints. There are almost surely only finitely many crossings of each such interval, which rules out distinct lower and upper limits; Fatou’s lemma makes the resulting limit finite and integrable. This is the martingale convergence theorem, not a consequence of an $L^2$ estimate. [2]

If , Cauchy–Schwarz first gives the $L^1$ bound, hence $M_n\to M_{\infty }$ almost surely by that theorem. Now (10) makes $\underset{n}{sup}|M_n{|}^2$ integrable. Since $|M_n-M_{\infty }{|}^2\le 4\underset{k}{sup}|M_k{|}^2$, dominated convergence gives $E[|M_n-M_{\infty }{|}^2]\to 0$: convergence in $L^2$. [2]6

The Snell envelope

Until now stopping has been something done to a process. Reverse the question. Given an adapted reward $Z_n$ with for $n=0,\dots ,N$, which stopping time $\tau \le N$ maximises $E[Z_{\tau }]$? The finite horizon matters: it guarantees that the following recursion reaches an attainable terminal reward. [6] [7]

The recursion in (11) is a dialogue with two lines. Take what is on the table, or hold and inherit the value of holding; take whichever is larger. Set ${\tau }^{\ast }=min\{0\le n\le N:V_n=Z_n\}$. This is a stopping time and ${\tau }^{\ast }\le N$ because $V_N=Z_N$. On the continuation value equals $V_n$, so the stopped process $V_{n\wedge {\tau }^{\ast }}$ is a martingale. Bounded optional stopping gives $E[Z_{{\tau }^{\ast }}]=E[V_0]$. For any stopping time $\tau \le N$, domination and bounded optional sampling give $E[Z_{\tau }]\le E[V_{\tau }]\le E[V_0]$. Thus ${\tau }^{\ast }$ is optimal. [8]

The scope is broad, but specific: choose a stopping time for a given reward process and information flow. Sequential testing can lead to such a problem after specifying losses and observation costs. A bandit problem also chooses which observation to make next; that extra control is not supplied by (11). Shiryaev treats statistical stopping problems, and Peskir and Shiryaev develop the connection with free-boundary problems. [7] [8]

The market's martingale

A concrete financial example is a finite-horizon binomial market with a non-dividend-paying stock, a bank account $B_n=(1+r{)}^n$, and constant stock multipliers $d,u$ satisfying . Assume frictionless trading, unrestricted borrowing and short selling, and positive physical probabilities for both branches at every node. The market is complete and has a unique equivalent risk-neutral measure $Q$, with up probability $q=(1+r-d)/(u-d)$. Discounted stock prices are $Q$-martingales: [9]

In this complete model an American payoff $H_n\ge 0$ is priced by the Snell envelope of $Z_n=H_n/B_n$ under $Q$; multiply the envelope by $B_n$ to recover the price at time $n$. All variables are integrable on the finite tree, and exercise times satisfy $\tau \le N$. Replication connects this stopping value to the no-arbitrage price. See Shreve, Chapter 4, “American Derivative Securities,” pp. 89–117. [9]7

For a backtest, the useful question is which model and information set justify the calculation. The martingale property under a pricing measure does not assert zero expected returns under the physical measure. A claimed riskless gain also calls for checking trading costs, financing, position limits and whether decisions use information actually available at the time. Optional stopping addresses a stated stochastic model; it does not validate the data or the execution assumptions.

Coda

What makes the martingale useful is that drift can be separated from fluctuation. In discrete time, an adapted integrable process $Y_n$ has a Doob decomposition $Y_n=M_n+A_n$, where $A_0=0$ and $A_n-A_{n-1}=E[Y_n-Y_{n-1}\mid {\mathcal{ℱ}}_{n-1}]$. Then $M$ is a martingale and $A$ is predictable; for a submartingale, $A$ is nondecreasing. Each inequality still needs its own integrability assumptions. [3] [2]

A stopping rule can react to what has happened. That is its purpose. Repeatedly inspecting a trial and stopping at a boundary may be a valid stopping time; it does not thereby preserve a test calibrated for a fixed sample size. Wald’s procedure builds the sequential decision into the design. Choosing the best historical window afterwards is a different operation. The useful discipline is to state the information, the rule and the result whose conditions it satisfies. [4]