Martingales §

Step 1 — Read the definition as a prediction rule. The conditional expectation $\mathbb{E}[X_{t+1} \mid \mathcal{F}_t]$ is the best (mean-square) prediction of the next value using everything you know so far. A martingale says: the best prediction of the future is exactly where you are now. There is no edge to exploit, no trend to ride. A submartingale says the future is, on average, at least as large as the present (a favorable game); a supermartingale says at most as large (an unfavorable game). The martingale is the knife-edge between the two.

Step 2 — The symmetric random walk is the prototype. Let $X_0 = 0$ and let $X_n = \sum_{i=1}^{n} \varepsilon_i$ where the $\varepsilon_i$ are i.i.d. with $\mathbb{P}(\varepsilon_i = +1) = \mathbb{P}(\varepsilon_i = -1) = \tfrac{1}{2}$. This is the gambler’s fortune after $n$ fair coin flips. Given the whole past, the next increment $\varepsilon_{n+1}$ is still a fair coin, so

The walk is a martingale. Notice the variance grows ($\mathrm{Var}(X_n) = n$), so the path wanders farther and farther from zero even though its mean stays pinned at zero: no trend, but plenty of spread.

Step 3 — A biased walk is a submartingale. If instead $\mathbb{P}(\varepsilon_i = +1) = p > \tfrac{1}{2}$, then $\mathbb{E}[\varepsilon_i] = 2p - 1 > 0$ and $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n + (2p-1) > X_n$: the walk is a submartingale with a genuine upward drift. The martingale is exactly the $p = \tfrac{1}{2}$ case.

Example. A gambler starts with a fortune of 100 and bets 1 unit on a fair coin each round. Their fortune $X_n$ is a martingale: after any history, the expected fortune one round later is exactly the current fortune. The expected fortune is always 100, no matter how long they play — yet the probability of eventually going broke is $1$ (a fact the convergence theorems below make precise).

Authoritative sources

• Martingale (Wikipedia)

Step 1 — Why stopping times are the right notion of “a rule.” A strategy that says “stop when your fortune first hits 150” is a stopping time: at each moment you can check whether the target has been reached using only the past. A rule like “stop at the time of the maximum” is not a stopping time, because you cannot know a time is the maximum until you see the future. The OST applies only to the honest kind.

Step 2 — The theorem in one line. For a martingale, the expected value is constant in time: $\mathbb{E}[X_t] = \mathbb{E}[X_0]$. If you freeze the process at a well-behaved stopping time $\tau$, the frozen value $X_{\tau}$ still has the same expectation. Fairness is preserved by any legitimate stopping rule.

Step 3 — The conditions are not decoration. The classic trap is a stopping time that is almost surely finite but whose stopped value is not integrable, or whose tail carries enough mass to break the equality. The next example is the canonical demonstration.

The gambler’s-ruin counterexample. A gambler plays a fair coin, gaining or losing 1 unit per round, starting at $X_0 = 0$. They adopt the rule: stop when the fortune first reaches $+100$ or $-50$. Let $\tau$ be that stopping time. The walk is a martingale and $\tau < \infty$ a.s. (a symmetric walk hits either boundary with probability $1$), so it is tempting to conclude $\mathbb{E}[X_{\tau}] = \mathbb{E}[X_0] = 0$.

But $X_{\tau} \in \{+100, -50\}$, so $\mathbb{E}[X_{\tau}] = 100\,p + (-50)(1-p)$ where $p = \mathbb{P}(X_{\tau} = +100)$. Setting this to $0$ gives $100p = 50(1-p)$, i.e. $p = \tfrac{1}{3}$. So the gambler reaches $+100$ with probability only $\tfrac{1}{3}$ and $-50$ with probability $\tfrac{2}{3}$. The OST does hold here (the stopped value is bounded, hence integrable), and it correctly predicts the $\tfrac{1}{3}$ win probability — the “counterexample” is to the naive reading that “I’ll stop as soon as I’m ahead, so I’m guaranteed to win.” The rule does not create an edge; it only reshapes the distribution.

The genuinely dangerous version: a gambler who stops at the first time the fortune is positive (rule $\tau = \inf\{n : X_n > 0\}$) has $X_{\tau} = +1$ always, so $\mathbb{E}[X_{\tau}] = 1 \ne 0 = \mathbb{E}[X_0]$. The OST’s hypotheses fail: although $\tau < \infty$ a.s., the stopped process is not uniformly integrable and $\mathbb{E}[\tau] = \infty$. This is the “you can’t beat a fair game, but you can make the expected stopping time infinite” paradox.

Authoritative sources

• Optional stopping theorem (Wikipedia)
• Gambler’s ruin (Wikipedia)

Step 1 — What the inequality controls. A martingale has constant mean, but its path can spike far above that mean before settling. Doob’s inequality bounds the probability of such a spike in terms of the terminal (or initial) size: the chance the running maximum ever exceeds $a$ is at most the mean divided by $a$. It is the maximal-function analogue of Markov’s inequality.

Step 2 — The idea of the proof (upcrossings). The proof counts how often the path upcrosses a level $[a, b]$ (goes from below $a$ to above $b$). For a submartingale, each upcrossing must be “paid for” by an increase in the process, and the total number of upcrossings is bounded by the total increase divided by the gap $b - a$. Letting $b \downarrow a$ converts the upcrossing count into a bound on the maximum. This is the same “energy accounting” that underlies the convergence theorems.

Step 3 — Why it is useful. Doob’s inequality is the workhorse that turns “the mean is controlled” into “the whole path is controlled with high probability.” It is the key step in proving the martingale convergence theorems and in establishing almost-sure versions of limit theorems.

Example. Let $X_t = S_t$ be a symmetric random walk (a martingale, hence a submartingale in absolute value via $|X_t|$). Doob’s inequality says the probability the walk ever reaches $+50$ before a fixed horizon is at most $\mathbb{E}[|X_T|]/50$, a quantity that grows only like $\sqrt{T}/50$ — so the chance of a huge spike stays small for moderate $T$.

Authoritative sources

• Doob’s inequalities (Wikipedia)

Step 1 — Bounded mean forces convergence. An $L^1$-bounded martingale cannot keep oscillating forever: the upcrossing argument of Doob’s inequality shows the expected number of upcrossings of any level $[a,b]$ is finite, which forces the path to settle down. Hence $X_t \to X_\infty$ a.s.

Step 2 — Uniform integrability upgrades the mode of convergence. Almost-sure convergence alone does not guarantee that expectations converge ($\mathbb{E}[X_t] \to \mathbb{E}[X_\infty]$). Uniform integrability rules out “mass escaping to the tail,” and then $X_t \to X_\infty$ in $L^1$, so $\mathbb{E}[X_\infty] = \mathbb{E}[X_0]$.

Step 3 — Connection to the strong law of large numbers. Let $X_1, X_2, \dots$ be i.i.d. with $\mathbb{E}[|X_1|] < \infty$ and $\mathbb{E}[X_1] = 0$, and set $S_n = X_1 + \dots + X_n$. Then $(S_n)$ is a martingale. The strong law of large numbers, $S_n/n \to 0$ a.s., is a direct corollary of the martingale convergence theorem applied to the normalized martingale (see Limit theorems). Martingale convergence is thus the general engine behind the almost-sure stabilization of averages.

Example. The gambler’s fortune $X_n$ in a fair game is an $L^1$-bounded martingale only if the fortune is bounded; an unbounded fair walk has $\mathbb{E}[|X_n|] \to \infty$, so the theorem’s hypothesis fails and the walk does not converge — it wanders off to $\pm\infty$ in the sense that it visits every level infinitely often.

Authoritative sources

• Martingale convergence theorem (Wikipedia)

Step 1 — One property, many families. The martingale condition only asks that the conditional mean of the increment vanish. It does not care whether the increments are Gaussian (Brownian), Poisson (compensated counting), or arbitrary (martingale-difference). That is why a single set of tools — optional stopping, Doob’s inequalities, convergence theorems — applies uniformly across all of stochastic processes.

Step 2 — Compensating a drift is the general recipe. Whenever a process has a predictable drift, subtracting the accumulated drift yields a martingale. The Poisson process $N_t$ drifts up at rate $\lambda$; $N_t - \lambda t$ does not. A biased random walk $X_n$ drifts at $2p-1$ per step; $X_n - n(2p-1)$ is a martingale. This “compensation” is the bridge between submartingales (drifting up) and martingales (drift-free).

Step 3 — Martingale-difference sequences are the atoms. Every discrete-time martingale is a sum of martingale-difference terms: $X_n - X_{n-1}$ has conditional mean zero. Conversely, summing any martingale-difference sequence gives a martingale. So the discrete theory reduces to understanding zero-conditional-mean increments, which is exactly the content of the fair-game definition.

Example. A Poisson process with rate $\lambda = 2$ has $\mathbb{E}[N_t] = 2t$. The compensated process $M_t = N_t - 2t$ satisfies $\mathbb{E}[M_t \mid \mathcal{F}_s] = \mathbb{E}[N_t] - 2t - (N_s - 2s) = (2t - 2s) - (N_s - 2s) = N_s - 2s = M_s$ for $t \ge s$: a martingale with mean zero and variance $\mathrm{Var}(M_t) = \mathrm{Var}(N_t) = 2t$.

Authoritative sources

• Martingale (Wikipedia)
• Compensator (Wikipedia)

A player starts with a fortune of 30 and plays a fair coin, winning or losing 1 unit per round. They stop as soon as their fortune reaches either 0 (broke) or 100.

(a) Identify the martingale and the stopping time, and justify that the optional stopping theorem applies.

(b) What is the probability the player reaches 100 before going broke?