10.4 Applications of martingales

Martingale Properties

A martingale is a stochastic process where the conditional expectation of the next value, given all past observations, equals the current value. Formally, $\{X_n\}$ is a martingale if $E[X_{n+1} \mid X_1, \ldots, X_n] = X_n$ for all $n$. This captures the notion of a "fair game": knowing the entire history gives you no advantage in predicting whether the process will go up or down.

Submartingale vs Supermartingale

A submartingale satisfies $E[X_{n+1} \mid X_1, \ldots, X_n] \geq X_n$. The process tends to drift upward (or stay flat) over time. Think of a favorable game where the expected return is non-negative.

A supermartingale satisfies $E[X_{n+1} \mid X_1, \ldots, X_n] \leq X_n$. The process tends to drift downward (or stay flat). This models an unfavorable game where the expected return is non-positive.

A useful mnemonic: "super" means the process is pushed down (supermartingales decrease), which feels counterintuitive but is standard. If $X_n$ is a submartingale, then $-X_n$ is a supermartingale.

Martingale Stopping Theorem

The optional stopping theorem (also called the martingale stopping theorem) says that if $\{X_n\}$ is a martingale and $T$ is a stopping time, then $E[X_T] = E[X_0]$ provided certain regularity conditions hold. The most common sufficient conditions are:

• $T$ is almost surely bounded (i.e., $T \leq N$ for some constant $N$), or
• $E[T] < \infty$ and the increments $|X_{n+1} - X_n|$ are bounded, or
• The stopped process $X_{T \wedge n}$ is uniformly integrable

This theorem is extremely useful: it lets you compute expected values at random stopping times, which shows up in gambling problems, sequential testing, and optimal stopping.

Martingale Convergence Theorem

The martingale convergence theorem states that if $\{X_n\}$ is a martingale (or submartingale) that is bounded in $L^1$, meaning $\sup_n E[|X_n|] < \infty$, then $X_n$ converges almost surely to a finite limit $X_\infty$.

For $L^p$ convergence ($p > 1$), you need the stronger condition that $\sup_n E[|X_n|^p] < \infty$. Uniform integrability of $\{X_n\}$ guarantees both a.s. convergence and $L^1$ convergence, and also ensures $E[X_\infty] = E[X_0]$.

This result governs the long-term behavior of martingales and is the engine behind many of the applications below.

Martingales in Gambling

Gambling is the original setting for martingale theory. The connection is direct: if a game is fair, your cumulative fortune forms a martingale.

Fairness in Repeated Games

A repeated game is fair if the expected gain on each round is zero, regardless of past outcomes. If $S_n$ represents your cumulative winnings after $n$ rounds, fairness means $E[S_{n+1} \mid S_1, \ldots, S_n] = S_n$, which is exactly the martingale property.

This has a concrete consequence: in a fair game, no betting strategy can change the expected value of your fortune. You can bet more when you "feel lucky," but the optional stopping theorem tells you $E[S_T] = E[S_0] = 0$ (under appropriate conditions). The game doesn't care about your strategy.

Doubling Strategies

The classic martingale betting strategy (confusingly sharing the name) works like this: bet 1 unit, and after every loss, double your bet. The first win recovers all previous losses plus 1 unit of profit.

On paper, this seems foolproof. Martingale theory reveals why it fails:

• The strategy requires an unbounded bankroll. With a finite bankroll $B$, you can only double $\lfloor \log_2 B \rfloor$ times before going bust.
• The optional stopping theorem's conditions break down here because the stopped martingale is not bounded or uniformly integrable.
• In practice, the rare catastrophic loss (a long losing streak) exactly offsets the frequent small wins, keeping the expected gain at zero for a fair game.

Gambler's Ruin Problem

The gambler's ruin problem asks: starting with fortune $a$, playing a fair game against an opponent with fortune $b - a$, what is the probability of going broke?

Using the martingale $S_n$ (the gambler's fortune), the optional stopping theorem gives the ruin probability directly. For a fair game, the probability of ruin is $1 - a/b$, where $b$ is the total amount in play. For an unfair game (where $S_n$ is a supermartingale for the gambler), the ruin probability increases, and an exponential martingale $r^{S_n}$ (with $r$ chosen appropriately) can be used to compute it exactly.

Martingales in Finance

Financial mathematics relies heavily on martingale theory. The core idea: in an efficient market, properly discounted asset prices should be martingales under the right probability measure.

Stock Price Modeling

Under the efficient market hypothesis, the discounted stock price $e^{-rt}S_t$ is modeled as a martingale under a risk-neutral measure. This doesn't mean stock prices don't go up on average in the real world; it means that after adjusting for the risk-free rate, there's no predictable drift that could be exploited.

The Black-Scholes model assumes the stock price follows geometric Brownian motion: $dS_t = \mu S_t \, dt + \sigma S_t \, dW_t$. Under the risk-neutral measure $\mathbb{Q}$, the drift $\mu$ is replaced by the risk-free rate $r$, making the discounted price process a martingale.

Option Pricing

The price of a European option with payoff $h(S_T)$ at maturity $T$ is computed as:

$V_0 = e^{-rT} E^{\mathbb{Q}}[h(S_T)]$

where $\mathbb{Q}$ is the risk-neutral measure under which discounted prices are martingales. This is the martingale pricing formula.

Both the Black-Scholes model (continuous time) and the binomial option pricing model (discrete time) are built on this principle. In the binomial model, you construct the risk-neutral probabilities explicitly so that the discounted stock price is a martingale at each step, then price the option by taking expectations backward through the tree.

Arbitrage-Free Pricing

The Fundamental Theorem of Asset Pricing makes the connection precise:

• First FTAP: A market is arbitrage-free if and only if there exists an equivalent martingale measure (a probability measure under which discounted prices are martingales).
• Second FTAP: The market is complete (every contingent claim can be hedged) if and only if the equivalent martingale measure is unique.

This gives martingale theory a foundational role in finance: the absence of arbitrage is equivalent to the existence of a measure that turns prices into martingales.

Martingales in Statistics

Martingale methods provide tools for statistical procedures where data arrives sequentially and you need to make decisions before all data is collected.

Sequential Analysis

Sequential analysis deals with testing hypotheses as data accumulates, rather than waiting for a fixed sample size. The sequential probability ratio test (SPRT), developed by Wald, is the key procedure here.

The SPRT is built on the likelihood ratio $\Lambda_n = \prod_{i=1}^{n} \frac{f_1(X_i)}{f_0(X_i)}$, which forms a martingale under the null hypothesis $H_0$. You continue sampling until $\Lambda_n$ crosses an upper or lower boundary, then reject or accept accordingly.

Wald showed the SPRT is optimal: among all tests with the same error probabilities, it minimizes the expected sample size under both hypotheses. The optional stopping theorem is the tool that makes the error probability calculations work.

Confidence Intervals

In sequential settings, where the sample size is random (determined by a stopping rule), standard confidence interval formulas can break down. Martingale-based confidence intervals maintain their guaranteed coverage probability regardless of the stopping rule.

The construction typically uses martingale central limit theorems or martingale difference sequences. The key advantage: these intervals remain valid even when the decision to stop collecting data depends on the data itself.

Hypothesis Testing

Beyond the SPRT, martingale structure appears throughout sequential testing. Test statistics in many sequential procedures form martingales (or transforms of martingales) under the null hypothesis.

This structure lets you apply the convergence theorem and optional stopping theorem to:

• Control type I and type II error probabilities
• Compute expected sample sizes
• Derive power functions

The martingale central limit theorem also provides asymptotic normality results for test statistics, extending classical fixed-sample results to the sequential setting.

Martingales in Algorithms

Martingale methods are a standard tool in theoretical computer science for analyzing randomized algorithms and proving combinatorial existence results.

Randomized Algorithms

Randomized algorithms make random choices during execution. To prove that such an algorithm performs well with high probability (not just in expectation), you often model some quantity of interest as a martingale.

For example, consider an algorithm that processes $n$ items one at a time, making a random decision at each step. If $X_i$ represents the state after step $i$, and you can write $X_i$ as a martingale (or a function of a martingale), then concentration inequalities give you tail bounds on the final outcome.

Probabilistic Method

The probabilistic method proves that a combinatorial object with certain properties exists by showing a random construction works with positive probability. Martingales enter through the method of conditional expectations.

The idea: expose the random choices one at a time. After revealing choice $i$, compute the conditional expectation of the quantity of interest. This sequence of conditional expectations forms a Doob martingale. Applying concentration inequalities to this martingale shows the random variable is tightly concentrated around its mean, which can be enough to prove the desired object exists.

Concentration Inequalities

Several key concentration inequalities are derived using martingale arguments:

• Azuma-Hoeffding inequality: If $\{X_n\}$ is a martingale with bounded differences $|X_i - X_{i-1}| \leq c_i$, then $P(|X_n - X_0| \geq t) \leq 2\exp\left(\frac{-t^2}{2\sum c_i^2}\right)$
• McDiarmid's inequality: If $f(Z_1, \ldots, Z_n)$ satisfies a bounded differences condition, then $f$ is concentrated around $E[f]$. The proof constructs a Doob martingale and applies Azuma-Hoeffding.
• Freedman's inequality: A martingale version of Bernstein's inequality that accounts for the variance of the martingale increments, giving tighter bounds when the increments are small.

These inequalities are workhorses in algorithm analysis, machine learning theory, and high-dimensional statistics.

Martingales in Queueing Theory

Queueing theory studies systems where customers arrive, wait, and get served. Martingale methods help analyze waiting times, busy periods, and when queues remain stable.

Lindley's Equation

Lindley's recursion describes the waiting time $W_{n+1}$ of the $(n+1)$-th customer in a single-server (G/G/1) queue:

$W_{n+1} = \max(0, \, W_n + S_n - T_n)$

where $S_n$ is the service time and $T_n$ is the interarrival time. By constructing an appropriate exponential martingale from the sequence $S_n - T_n$, you can derive the steady-state waiting time distribution and its tail behavior. The optional stopping theorem applied to this martingale yields the Laplace-Stieltjes transform of the waiting time.

Busy Period Analysis

The busy period is the time interval from when a server starts working (queue becomes non-empty) until it first becomes idle again. In the M/G/1 queue, the busy period $B$ satisfies a distributional equation that can be analyzed via martingale techniques.

Specifically, you construct a martingale from the number of customers in the system and apply the optional stopping theorem at the end of the busy period. This yields the Laplace-Stieltjes transform $E[e^{-sB}]$ and moments of $B$ in closed form.

Stability Conditions

A queue is stable if the queue length and waiting time don't blow up to infinity over time. The classical condition is $\rho = \lambda / \mu < 1$ (arrival rate less than service rate), but martingale methods provide a rigorous framework for proving this.

For the G/G/1 queue, you can construct a martingale (or supermartingale) from the workload process. The martingale convergence theorem then establishes that the workload converges to a proper stationary distribution when the stability condition holds, and diverges otherwise.

Martingales in Branching Processes

Branching processes model populations where each individual independently produces a random number of offspring. Martingales are the primary analytical tool for understanding whether such populations survive or die out.

Extinction Probability

Let $Z_n$ be the population size at generation $n$, and let $\mu = E[\text{offspring per individual}]$. The process $W_n = Z_n / \mu^n$ is a martingale (since $E[Z_{n+1} \mid Z_n] = \mu Z_n$).

The extinction probability $q$ (the probability that $Z_n = 0$ for some $n$) is the smallest non-negative root of $s = G(s)$, where $G$ is the probability generating function of the offspring distribution. The three regimes are:

• Subcritical ($\mu < 1$): Extinction is certain ($q = 1$)
• Critical ($\mu = 1$): Extinction is certain ($q = 1$), but it takes longer on average
• Supercritical ($\mu > 1$): Extinction probability $q < 1$; the population survives with positive probability

The optional stopping theorem applied to $G(s)^{Z_n}$ (which is a martingale for appropriate $s$) provides the extinction probability formula.

Limit Theorems

The martingale $W_n = Z_n / \mu^n$ converges almost surely to a limit $W$ by the martingale convergence theorem (since $W_n \geq 0$).

Two classical results characterize this limit:

• Kesten-Stigum theorem: In the supercritical case, $W > 0$ a.s. on the survival event if and only if $E[Z_1 \log Z_1] < \infty$ (the so-called $X \log X$ condition). Without this condition, $W = 0$ a.s. even on survival.
• Seneta-Heyde theorem: When the $X \log X$ condition fails, there exist normalizing constants $c_n$ (growing slower than $\mu^n$) such that $Z_n / c_n$ converges to a non-degenerate limit.

Galton-Watson Process

The Galton-Watson process is the prototypical branching process. Starting from $Z_0 = 1$ ancestor, each individual in generation $n$ independently produces offspring according to a fixed distribution $\{p_k\}_{k \geq 0}$.

The key martingale is again $W_n = Z_n / \mu^n$. All the results above (extinction probability, Kesten-Stigum, convergence) apply directly. The Galton-Watson process also illustrates why martingale methods are so natural here: the branching structure creates conditional independence that makes the martingale property easy to verify, and the stopping/convergence theorems translate directly into biological and demographic conclusions about population survival.