Martingale Theory

A martingale is a sequence of random variables where the conditional expectation of the next value given all the past information comes out equal to the present value. This conservation property $\mathbb{E}[X_{n+1} | \mathcal{F}_n] = X_n$ hands you strong convergence results and sits at the foundation of a few big areas.

1. Mathematical finance and things like the Efficient Market Hypothesis and option pricing.
2. Sequential analysis like deciding when to stop a clinical trial or an A/B test with Wald’s Identity.
3. Modern statistics and especially concentration bounds for randomized algorithms with Azuma-Hoeffding.

What follows is a measure-theoretic walk through discrete-time martingales and covers convergence theorems and applications in finance and computer science.

1. Definitions and Measure-Theoretic Setup

Let $(\Omega, \mathcal{F}, P)$ be a probability space.

1.1 Information and Filtrations

We model how information piles up over time with a filtration. Definition (Filtration). A filtration is an increasing sequence of sub-$\sigma$-algebras $\{\mathcal{F}_n\}_{n \ge 0}$ with

and here $\mathcal{F}_n$ stands in for the information you have at time $n$.

• Natural filtration. $\mathcal{F}_n = \sigma(X_0, \dots, X_n)$ and it is the $\sigma$-algebra spun up by the history of the process itself.
• Dyadic filtration. On $\Omega = [0, 1)$ let $\mathcal{F}_n$ come from the intervals $[k 2^{-n}, (k+1) 2^{-n})$, and as $n \to \infty$ the point $x$ gets nailed down with infinite precision through its binary expansion.

Definition (Adapted Process). A sequence $X = (X_n)_{n \ge 0}$ is adapted to $\mathcal{F}_n$ when $X_n$ is $\mathcal{F}_n$-measurable for every $n$, and this means the value of $X_n$ is set by the information you have at time $n$.

1.2 Martingales, Submartingales, Supermartingales

Definition. An adapted and integrable sequence $X_n$ is a martingale with respect to $\{\mathcal{F}_n\}$ when

1. Integrability. $\mathbb{E}[|X_n|] < \infty$ for all $n$.
2. Martingale property. $\mathbb{E}[X_{n+1} | \mathcal{F}_n] = X_n$ almost surely.

Swapping the equality for an inequality gives two cousins.

• Submartingale ($\ge$). $\mathbb{E}[X_{n+1} | \mathcal{F}_n] \ge X_n$ and the process tends to drift up, and this also covers convex functions of martingales by Jensen’s inequality.
• Supermartingale ($\le$). $\mathbb{E}[X_{n+1} | \mathcal{F}_n] \le X_n$ and the process tends to drift down, and this is the standard model of an unfavorable game.

1.3 Canonical Examples

1. Simple Symmetric Random Walk. $S_n = \sum_{i=1}^n \xi_i$ where $\xi_i = \pm 1$ with probability $1/2$ each. $\mathbb{E}[S_{n+1} | \mathcal{F}_n] = S_n + \mathbb{E}[\xi_{n+1}] = S_n$ and this is a martingale.
2. Biased Random Walk. When $P(\xi_i = 1) = p > 1/2$ you get $\mathbb{E}[S_{n+1} | \mathcal{F}_n] = S_n + (2p-1) > S_n$ and this is a submartingale. But the geometric process $M_n = ((1-p)/p)^{S_n}$ is a martingale and this is De Moivre’s martingale.
3. Polya’s Urn. An urn holds $r$ red and $g$ green balls and you pick one and return it along with another of the same color. Let $X_n$ be the fraction of red balls at time $n$ and then $X_n$ is a martingale. Because $X_n$ is bounded in $[0, 1]$ it converges almost surely, and the limit $X_\infty$ follows a Beta distribution and does not pile up at a point.
4. Likelihood Ratios. Let $P$ and $Q$ be probability measures and let $L_n = \frac{dQ|_{\mathcal{F}_n}}{dP|_{\mathcal{F}_n}}$ be the Radon-Nikodym derivative cut down to the first $n$ observations. Under measure $P$ the $L_n$ is a nonnegative martingale.

2. Doob’s Decomposition

Every submartingale splits uniquely into a martingale piece that holds the fluctuations and a predictable increasing piece that holds the drift. This is the discrete-time version of the Doob-Meyer Decomposition.

Proof. Set $\Delta A_n = \mathbb{E}[X_n - X_{n-1} | \mathcal{F}_{n-1}]$ and because $X$ is a submartingale you have $\Delta A_n \ge 0$. Let $A_n = \sum_{k=1}^n \Delta A_k$ and then $A_n$ is predictable and increasing. Set $M_n = X_n - A_n$ and then $\mathbb{E}[M_n - M_{n-1} | \mathcal{F}_{n-1}] = 0$.

2.5 Doob’s Maximal Inequalities

The next inequality bounds the fluctuations of a submartingale by its endpoint. Let $M_n^* = \max_{0 \le k \le n} |X_k|$. Theorem (Doob’s Submartingale Inequality). When $X$ is a non-negative submartingale then for any $\lambda > 0$

Proof (Sketch). Let $E = \{M_n^* \ge \lambda\}$ and split $E$ by the first time the process crosses $\lambda$ so $E_k = \{X_k \ge \lambda, \forall j < k, X_j < \lambda\}$. Because $X$ is a submartingale you get $\mathbb{E}[X_n \mathbb{1}_{E_k}] \ge \mathbb{E}[X_k \mathbb{1}_{E_k}] \ge \lambda P(E_k)$, and summing over $k$ hands you the result.

Corollary ($L^p$ Inequality). When $X_n$ is a martingale and $X_n \in L^p$ for $p > 1$ then

And so the maximum of the process is bounded by the endpoint in $L^p$, and $L^p$ convergence of the endpoint steps up to uniform convergence of the whole path.

3. Stopping Times and Optional Stopping

A random variable $T: \Omega \to \mathbb{N} \cup \{\infty\}$ is a stopping time when $\{T \le n\} \in \mathcal{F}_n$ for all $n$. The decision to stop can only lean on the present and past information.

• Example. “Stop when $S_n \ge 10$” is a stopping time.
• Non-example. “Stop at the time the process hits its maximum” needs knowledge of the future and is not a stopping time.

The stopped process $X_n^T = X_{T \land n}$ hangs onto the martingale property and so when $X$ is a martingale so is $X^T$. The deeper question is whether $\mathbb{E}[X_T] = \mathbb{E}[X_0]$.

Counter-example (Doubling Strategy). Let $S_n$ be a symmetric random walk starting at 0 and let $T = \inf \{n : S_n = 1\}$, and then $T < \infty$ almost surely and $S_T = 1$ and so $\mathbb{E}[S_T] = 1 \ne \mathbb{E}[S_0] = 0$. The equality breaks because $S_n$ can drop arbitrarily negative before hitting 1 and this breaks the integrability conditions for optional stopping.

3.5 Uniform Integrability (UI)

Uniform integrability is the condition that makes expectations converge so that $\mathbb{E}[X_n] \to \mathbb{E}[X]$. Definition. A family $\{X_i\}_{i \in I}$ is uniformly integrable when

Uniform integrability stops probability mass from running off to infinity. In the doubling strategy the mass does run off, and at any finite time there is a small probability of a big loss and these contributions do not fade out in a uniform way.

Theorem. $X_n \to X$ in $L^1$ exactly when $X_n \to X$ in probability and $\{X_n\}$ is UI.

Because conditional expectation is an $L^1$ contraction the uniform integrability is the natural regularity condition for martingale convergence.

Doob’s UI Theorem. When $X_n$ is a martingale the following are equivalent.

1. $\{X_n\}$ is UI.
2. $X_n$ converges in $L^1$ to a limit $X_\infty$.
3. $X_n = \mathbb{E}[X_\infty | \mathcal{F}_n]$ and the martingale is “closed”.

4. Martingale Convergence Theorems

The basic question is figuring out when a martingale runs toward a limit.

The Upcrossing Inequality. The upcrossing inequality sits at the heart of the convergence proof. Let $U_N[a, b]$ count how many times the process crosses upward from below $a$ to above $b$ by time $N$. The crossing times are set recursively.

• $T_1 = \min \{n : X_n \le a\}$
• $T_2 = \min \{n > T_1 : X_n \ge b\}$
• $T_3 = \min \{n > T_2 : X_n \le a\}$

and so on and $U_N$ counts the completed upcrossings.

Doob’s Upcrossing Inequality.

Proof Idea. Think of a gambling strategy that buys at level $a$ and sells at level $b$. Each completed upcrossing hands you a profit of $b-a$ and the upcrossing intervals do not overlap. Because the underlying process is a supermartingale and so an unfavorable game the total expected profit is bounded above, and the right-hand side holds the worst-case loss at the final time.

Because $\mathbb{E}|X_N| < \infty$ the expected number of upcrossings is finite. And so $X_n$ cannot swing between any two rationals $a < b$ infinitely often and convergence follows.

4.5 Application: The Secretary Problem (Optimal Stopping)

A classic application of martingale theory through Snell Envelopes is the Secretary Problem. Setup. You interview $N$ candidates one after another and you can rank them against the ones you have already seen. After each interview you have to hire or reject and a rejection is final. Goal. Push up the probability of picking the absolute best candidate. Strategy. Reject the first $k-1$ candidates and then hire the first one better than everyone before. Let $M_n = P(\text{Win} | \text{Stop at } n)$. We build the Snell Envelope which is the smallest supermartingale sitting above the payoff process. By backward induction you can show the optimal stopping rule is to skip $N/e$ candidates. The success probability runs toward $1/e \approx 37\%$.

5. Concentration Inequalities

One of the biggest modern uses of martingales is pinning down sharp concentration of random variables around their means.

5.1 Proof of Azuma-Hoeffding

The proof runs through the Chernoff bound trick.

1. Exponential Markov. For any $\lambda > 0$ $P(X_n - X_0 \ge t) = P(e^{\lambda(X_n - X_0)} \ge e^{\lambda t}) \le e^{-\lambda t} \mathbb{E}[e^{\lambda(X_n - X_0)}]$
2. Telescoping. Write $X_n - X_0 = \sum_{k=1}^n D_k$ where $D_k = X_k - X_{k-1}$. $\mathbb{E}[e^{\lambda \sum D_k}] = \mathbb{E} [ e^{\lambda \sum_{k=1}^{n-1} D_k} \mathbb{E}[e^{\lambda D_n} | \mathcal{F}_{n-1}] ]$
3. Hoeffding’s Lemma. Because $\mathbb{E}[D_n | \mathcal{F}_{n-1}] = 0$ and $D_n \in [-c_n, c_n]$ which is an interval of length $2c_n$ you get $\mathbb{E}[e^{\lambda D_n} | \mathcal{F}_{n-1}] \le e^{\frac{\lambda^2 c_n^2}{2}}$
4. Iteration. Apply this $n$ times to get $\mathbb{E}[e^{\lambda(X_n - X_0)}] \le \prod_{k=1}^n e^{\frac{\lambda^2 c_k^2}{2}} = e^{\frac{\lambda^2}{2} \sum c_k^2}$
5. Optimization. Pick $\lambda = \frac{t}{\sum c_k^2}$ to make the bound as small as possible. $P \le \exp \left( - \lambda t + \frac{\lambda^2}{2} \sum c_k^2 \right) = \exp \left( - \frac{t^2}{2\sum c_k^2} \right)$

5.2 The Doob Martingale and McDiarmid’s Inequality

To push Azuma-Hoeffding onto a general function of independent random variables we use the Doob martingale construction. Let $Z_1, \dots, Z_n$ be independent random variables and let $f(Z)$ be a function you care about. The Doob martingale is

• $M_0 = \mathbb{E}[f(Z)]$ is the unconditional mean.
• $M_n = f(Z)$ is the realized value. The difference $D_k = M_k - M_{k-1}$ captures the information that $Z_k$ kicks in. When changing any one input $z_i$ shifts $f$ by at most $c_i$ which is the bounded difference property then $|D_k| \le c_k$.

Theorem (McDiarmid’s Inequality). For any function $f$ that has the bounded difference property with constants $c_1, \dots, c_n$

Application.

• Chromatic Number of Random Graphs. Changing one edge shifts the chromatic number by at most 1 and so $\chi(G_{n,p})$ packs tightly around its mean.
• Machine Learning. The generalization error of a classifier concentrates because changing one training example has a bounded effect on the output and this is where stability-based bounds come from.

6. Applications in Finance

The main use of martingale theory in mathematical finance is option pricing. A market holds risky assets like stocks and a risk-free asset like a bond. First Fundamental Theorem of Asset Pricing. The market has no arbitrage exactly when there is a risk-neutral measure $\mathbb{Q}$ equivalent to the physical measure $\mathbb{P}$ where the discounted stock price is a $\mathbb{Q}$-martingale.

Under $\mathbb{Q}$ the expected return of the stock comes out to the risk-free rate $r$ and the real-world drift $\mu$ drops out.

6.1 Girsanov Theorem (Change of Measure)

The move from $\mathbb{P}$ to $\mathbb{Q}$ happens by re-weighting probabilities. Let $Z_n = \frac{d\mathbb{Q}}{d\mathbb{P}}|_{\mathcal{F}_n}$ be the Radon-Nikodym derivative process. $Z_n$ is a positive martingale with $\mathbb{E}[Z_n] = 1$. Girsanov Theorem. When $M_n$ is a martingale under $\mathbb{P}$ then $\tilde{M}_n = M_n - \sum \frac{1}{Z_{k-1}} \mathbb{E}[\Delta M_k \Delta Z_k | \mathcal{F}_{k-1}]$ is a martingale under $\mathbb{Q}$. This lets you strip the drift out and a biased random walk for a stock with drift turns into a martingale under the new measure when you tweak the probabilities of up and down moves. Drift removal through a change of measure sits under the Black-Scholes formula.

6.2 Deriving Black-Scholes (Heuristic)

In the continuous-time limit of the binomial model as $\Delta t \to 0$ the stock price runs as

where $W_t$ is a Brownian Motion and it is the scaling limit of a random walk. Under the physical measure $\mathbb{P}$ the drift is $\mu$. Picking the risk-neutral measure $\mathbb{Q}$ swaps $\mu$ for the risk-free rate $r$.

The option price $V(S, t)$ is the discounted expected payoff under $\mathbb{Q}$.

Working this expectation out gives the Black-Scholes PDE.

The stock’s expected return $\mu$ does not show up in this equation and this falls out of the fact that the option’s risk can be hedged away completely.

7. Randomized Algorithms and Simulation

Martingales give you a natural setup for working out the runtime of randomized algorithms. Take a random walk on a graph $G=(V, E)$ and let $T$ be the hitting time of a vertex set. We build martingales $M_n = \phi(X_n) - n$ to estimate $\mathbb{E}[T]$.

7.1 Simulation: Wald’s Identity

Let $X_i$ be i.i.d. with mean $\mu$ and let $S_n = \sum X_i$ and let $T$ be a stopping time with $\mathbb{E}[T] < \infty$. Wald’s Identity. $\mathbb{E}[S_T] = \mu \mathbb{E}[T]$.

The simulation below runs a biased random walk stopped at thresholds $-A$ and $+B$ and checks that $M_n = S_n - n\mu$ is a martingale and that Wald’s identity holds.

import numpy as np
 
def simulate_wald(p=0.55, A=10, B=10, trials=1000):
    """
    Biased random walk X_i = +/- 1.
    P(X=1) = p. Drift mu = 2p - 1.
    Stop when S_n reaches -A or +B.
    """
    mu = 2*p - 1
    
    stopping_times = []
    final_values = []
    
    for _ in range(trials):
        S = 0
        t = 0
        while -A < S < B:
            step = 1 if np.random.rand() < p else -1
            S += step
            t += 1
        stopping_times.append(t)
        final_values.append(S)
        
    E_T = np.mean(stopping_times)
    E_S_T = np.mean(final_values)
    
    print(f"p={p}, Drift mu={mu:.2f}")
    print(f"Simulated E[T]: {E_T:.2f}")
    print(f"Simulated E[S_T]: {E_S_T:.2f}")
    print(f"Wald Check (mu * E[T]): {mu * E_T:.2f}")
    
    # Analytical Formula for Gambler's Ruin
    # P(Reach B) = (1 - (q/p)^A) / (1 - (q/p)^(A+B))
    q = 1-p
    if p != 0.5:
        ratio = q/p
        prob_B = (1 - ratio**A) / (1 - ratio**(A+B))
        analytical_E_S = B * prob_B + (-A) * (1 - prob_B)
        print(f"Analytical E[S_T]: {analytical_E_S:.2f}")
 
# simulate_wald(p=0.55, A=10, B=10)

The simulation backs up $\mathbb{E}[S_T] = \mathbb{E}[T] \cdot \mu$ as long as the stopping time has finite expectation.

8. Conclusion

The power of martingales comes from how universal they are.

1. Convergence. An $L^1$-bounded supermartingale converges almost surely.
2. Concentration. Under bounded differences the sums show sub-Gaussian concentration.
3. Pricing. No arbitrage is the same as having a martingale measure.

Whether you are looking at QuickSort runtime or barrier option pricing the martingale property gives a single framework for pulling precise quantitative information out of stochastic processes.

9. Polya’s Urn Scheme

Polya’s Urn gives a nice picture of martingale convergence. Setup. Start with 1 red and 1 green ball. At each step $n$ you pull a ball at random and then return it to the urn along with one more ball of the same color. Let $X_n$ be the fraction of red balls at time $n$. At the start $X_0 = 1/2$. Claim. $X_n$ is a martingale. Let $R_n$ and $G_n$ be the number of red and green balls and the total is $T_n = n+2$.

Convergence. Because $X_n$ is bounded in $[0, 1]$ the Martingale Convergence Theorem says $X_n \to X_\infty$ almost surely. Limit Distribution. The limit $X_\infty$ is not a constant and by induction you can check that $R_n$ is uniform on $\{1, \dots, n+1\}$. And so $X_\infty$ is uniform on $[0, 1]$ which is Beta(1, 1). More generally starting with $a$ red and $b$ green balls hands you a Beta($a$, $b$) limit. The Polya urn is a standard model for path dependence in economics and reinforcement learning.

The Radon-Nikodym Derivative

Conditional expectation $\mathbb{E}[X | \mathcal{G}]$ is set as the unique $\mathcal{G}$-measurable random variable $Z$ where

and the Radon-Nikodym theorem guarantees that such a $Z$ exists. Let $\mu$ and $\nu$ be two measures on $(\Omega, \mathcal{F})$. $\nu$ is absolutely continuous with respect to $\mu$ and written $\nu \ll \mu$ when $\mu(A) = 0$ forces $\nu(A) = 0$. Theorem. When $\nu \ll \mu$ and both are $\sigma$-finite there is a unique measurable function $f = \frac{d\nu}{d\mu}$ with

Martingale connection. Let $(\Omega, \mathcal{F}, \mathbb{Q})$ and $(\Omega, \mathcal{F}, \mathbb{P})$ be probability measures. The likelihood ratio process $L_n = \frac{d\mathbb{Q}|_{\mathcal{F}_n}}{d\mathbb{P}|_{\mathcal{F}_n}}$ is always a non-negative $\mathbb{P}$-martingale. When $L_n \to L_\infty$ with $\mathbb{E}[L_\infty] = 1$ you get $\mathbb{Q} \ll \mathbb{P}$ on $\mathcal{F}_\infty$. When $L_n \to 0$ the measures $\mathbb{Q}$ and $\mathbb{P}$ are mutually singular in the limit and this is Kakutani’s Dichotomy.

Backward Martingales

Take a decreasing sequence of $\sigma$-algebras $\{\mathcal{G}_{-n}\}_{n \ge 0}$ where $\mathcal{G}_0 \supseteq \mathcal{G}_{-1} \supseteq \dots \supseteq \mathcal{G}_{-\infty} = \cap \mathcal{G}_{-n}$. A sequence $X_{-n}$ is a backward martingale when $\mathbb{E}[X_{-n} | \mathcal{G}_{-n-1}] = X_{-n-1}$. Theorem. Every backward martingale converges almost surely and in $L^1$.

This hooks into the strong law of large numbers. Let $S_n = X_1 + \dots + X_n$ where the $X_i$ are i.i.d. Let $\mathcal{G}_{-n} = \sigma(S_n, S_{n+1}, \dots)$ which is the symmetric $\sigma$-algebra. You can check that $\mathbb{E}[X_1 | \mathcal{G}_{-n}] = S_n / n$. Because this is a backward martingale $S_n/n$ converges almost surely to $\mathbb{E}[X_1 | \text{Tail}]$, and by Kolmogorov’s 0-1 Law the tail $\sigma$-algebra is trivial and so the limit is the constant $\mu$.

Proof of the Optional Stopping Theorem

We prove the Optional Stopping Theorem in the bounded case. Theorem. When $M_n$ is a martingale and $T \le K$ is a bounded stopping time then $\mathbb{E}[M_T] = \mathbb{E}[M_0]$. Proof. You can write the stopped value as a sum of increments.

The event $\{n \le T\}$ is the complement of $\{T < n\} = \{T \le n-1\}$. Because $\{T \le n-1\} \in \mathcal{F}_{n-1}$ the complement $\{n \le T\}$ also sits in $\mathcal{F}_{n-1}$. And this means the process $H_n = \mathbb{1}_{n \le T}$ is predictable. Now look at the expectation.

By linearity of expectation because the sum is finite you get

Use the tower property of conditional expectation.

Because $H_n$ is $\mathcal{F}_{n-1}$-measurable

and by the martingale property $\mathbb{E} [ M_n - M_{n-1} | \mathcal{F}_{n-1} ] = 0$. And so every term in the sum dies and you get $\mathbb{E}[M_T] = \mathbb{E}[M_0]$.

Origins

Paul Levy brought in the main ideas behind martingales in 1934 while working on sums of dependent random variables and he did not use the name. Jean Ville coined the term “martingale” in 1939 as a reference to a class of gambling strategies and proved the first supermartingale inequality. Joseph Doob’s 1953 book “Stochastic Processes” set up the modern theory and covered the decomposition theorem and the convergence theorem and optional stopping. Azuma and Hoeffding each proved the bounded-difference concentration inequality in 1965 and it turned into a workhorse in combinatorics and computer science. The link to finance came together with Black and Scholes in 1973 when risk-neutral pricing recast option valuation as a martingale expectation. McDiarmid pushed concentration out to general functions of independent variables in the 1990s and made it a standard tool in learning theory and algorithm analysis.