Introduction to Martingales

Suppose you play a sequence of fair bets. You can double down or hedge however cleverly you like. You may only use information available so far. Can you expect, on average, to come out ahead? The theory of martingales says no. Under remarkably general conditions, no strategy based on past information can create an expected edge from a fair game. This single insight is formalized through conditional expectation and filtrations. It turns out to organize an enormous swath of probability theory. This ranges from the fluctuations of Random Walks to option pricing in mathematical finance. Martingales matter because they isolate the essential structure behind "fairness" and "information." This structure is stripped of any assumption of independence or identical distributions. A martingale need not have independent increments. It only needs one property. Its best predicted future value, given everything known now, is its current value. This is a weaker and far more flexible hypothesis than independence. It turns out to be exactly the right hypothesis for a battery of powerful theorems. These include convergence theorems, maximal inequalities, and especially the optional stopping theorem. This theorem tells us when we may substitute a random time for a fixed one. It shows when this substitution won't upset the fair-game property. The big picture is this: filtrations formalize the flow of information through time. Martingales formalize "no expected drift given the past." Stopping times formalize "decisions made using only present and past information." The optional stopping theorem is the central engine connecting these three ideas. It lets us compute expectations at random, strategy-dependent times. This calculation uses only the martingale's initial value. This is how one proves gambler's-ruin formulas and Wald's identity. It ultimately builds the bridge to continuous-time objects like Introduction to Brownian Motion. Brownian motion is itself the archetypal continuous martingale. This article gives the rigorous discrete-time definition of a martingale via conditional expectation. It develops filtrations and stopping times carefully. It states and completely proves the optional stopping theorem under two different sufficient-condition regimes. It works through fully quantitative examples, including a biased random walk and an urn-based martingale. Finally, it shows exactly what goes wrong when the theorem's hypotheses are dropped.

Key takeaways
  • A martingale is a stochastic process whose conditional expected future value, given the past, equals its present value.
  • Filtrations (Fn)(\mathcal{F}_n) formalize "information available by time nn"; a martingale must be adapted to its filtration.
  • Sub/supermartingales relax equality to ≥\geq / ≤\leq, modeling favorable/unfavorable games.
  • Stopping times are random times whose occurrence is determined without peeking into the future.
  • The optional stopping theorem gives conditions under which E[XT]=E[X0]\mathbb{E}[X_T] = \mathbb{E}[X_0] for a random time TT.
  • Key idea: you cannot manufacture expected profit from a fair game using only past information, and the optional stopping theorem is the precise statement of why.

Where this lives today

Martingale theory underlies the martingale approach to option pricing in mathematical finance: the discounted price of a tradable asset under a risk-neutral measure is required to be a martingale, and the optional stopping theorem justifies pricing American-style options via optimal stopping. In statistics, martingale central limit theorems extend classical CLTs to dependent data (e.g., in sequential analysis and stochastic approximation). In computer science, martingale concentration inequalities (Azuma–Hoeffding, built on the martingale transform technique used in this article's Lemma) bound the fluctuations of randomized algorithms and are staples in the probabilistic analysis of algorithms and in differential privacy proofs. In branching processes and population genetics, martingales like the one in the Pólya urn example track the evolution of type frequencies. The theory is also the direct discrete-time precursor to Introduction to Brownian Motion, whose defining property (independent, stationary, Gaussian increments) makes it the canonical continuous-time martingale, and whose stopping-time theory (e.g. the reflection principle, hitting-time distributions) is proved using continuous analogues of exactly the optional stopping machinery developed here.

:::quiz[In the Pólya urn example, why does case (a) of the optional stopping theorem apply for computing E[X5]\mathbb E[X_5]?]

  • Because XnX_n has independent increments
  • Because N=5N=5 is a fixed, deterministic, hence trivially bounded stopping time ✓
  • Because the urn has infinitely many balls
  • Because RnR_n is Gaussian

:::faq[Can a submartingale ever have E[XT]<E[X0]\mathbb E[X_T] < \mathbb E[X_0] for a bounded stopping time TT?] No. If (Xn)(X_n) is a submartingale and T≤NT\le N is a bounded stopping time, the same martingale-transform argument used to prove the Lemma shows E[Xn∧T]\mathbb E[X_{n\wedge T}] is nondecreasing in nn (since Hn(Xn−Xn−1)H_n(X_n-X_{n-1}) has nonnegative conditional expectation), giving E[XT]=E[XN∧T]≥E[X0]\mathbb E[X_T]=\mathbb E[X_{N\wedge T}]\ge \mathbb E[X_0]. So for bounded stopping times, submartingales can only gain value in expectation, never lose it — the natural asymmetric analogue of the martingale case proven in this article.

:::faq[Does the optional stopping theorem also apply to two different stopping times S≤TS\le T, giving E[XT∣FS]=XS\mathbb E[X_T\mid \mathcal F_S]=X_S?] Yes, this is the strengthened "optional sampling" form, proved by the same stopped-martingale technique applied to the process restricted to [S,T][S,T], under analogous integrability hypotheses (e.g. TT bounded, or the analogues of conditions (b)/(c)). It reduces to the stated theorem when S≡0S\equiv 0. The proof follows the identical stopped-martingale construction, replacing X0X_0 throughout by the FS\mathcal F_S-measurable random variable XSX_S, and is the form most directly used to prove the strong Markov property connections exploited later in Introduction to Brownian Motion.

Ask the tutor: Can you show me how the optional stopping theorem is used to derive the expected duration of gambler's ruin, not just the ruin probability?

DefinitionFiltration, adapted process, martingale

Let (Ω,F,P)(\Omega, \mathcal{F}, \mathbb{P}) be a probability space. A filtration is a nondecreasing sequence of sub-σ\sigma-algebras

F0⊆F1⊆F2⊆⋯⊆F,\mathcal{F}_0 \subseteq \mathcal{F}_1 \subseteq \mathcal{F}_2 \subseteq \cdots \subseteq \mathcal{F},

interpreted as the information available by time nn. A stochastic process (Xn)n≥0(X_n)_{n\geq 0} is adapted to (Fn)(\mathcal{F}_n) if XnX_n is Fn\mathcal{F}_n-measurable for every nn. A sequence (Xn)n≥0(X_n)_{n \geq 0} is a martingale with respect to (Fn)(\mathcal{F}_n) if: 1. (Xn)(X_n) is adapted to (Fn)(\mathcal{F}_n); 2. E[∣Xn∣]<∞\mathbb{E}[|X_n|] < \infty for all nn (integrability); 3. E[Xn+1∣Fn]=Xn\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n almost surely, for all n≥0n \geq 0. If instead E[Xn+1∣Fn]≥Xn\mathbb{E}[X_{n+1}\mid \mathcal{F}_n] \geq X_n a.s. for all nn, (Xn)(X_n) is a submartingale; if E[Xn+1∣Fn]≤Xn\mathbb{E}[X_{n+1}\mid \mathcal{F}_n] \leq X_n a.s. for all nn, it is a supermartingale. A random variable T:Ω→{0,1,2,… }∪{∞}T : \Omega \to \{0, 1, 2, \dots\} \cup \{\infty\} is a stopping time with respect to (Fn)(\mathcal{F}_n) if {T≤n}∈Fn\{T \leq n\} \in \mathcal{F}_n for every n≥0n \geq 0 — equivalently {T=n}∈Fn\{T = n\} \in \mathcal{F}_n for every nn.

Intuition

Think of Fn\mathcal{F}_n as the sealed folder of everything observable through time nn: past coin flips, stock prices, urn draws. Adaptedness says XnX_n's value is already determined once the folder is opened — no clairvoyance. The martingale property says that averaging over what happens next, using only what's in the folder, reproduces today's value exactly: the process has no built-in drift, up or down, conditional on the present. A stopping time is a rule for "when to quit" that only consults the folder as it is filled — you cannot decide to stop today because you know tomorrow's value will be high. The classic illegal move is "stop right before the price crashes"; that requires future information and is not a stopping time. The picture below shows one sample path of a symmetric random walk martingale, with a stopping time TT marked as the first time the path exits the strip [−3,4][-3,4]. Because TT is defined by a condition checkable at each step using only the path so far, it is a genuine stopping time — unlike "the time of the last visit to 0 before step 20," which requires knowing the whole future path.

Figure
A martingale sample path and a stopping time defined by first exit from a strip
n Xₙ upper bound b = 4 lower bound a = -3 T (first exit, X_T = 4) 0 T n

The central theorem

TheoremOptional Stopping Theorem

Let (Xn)n≥0(X_n)_{n \geq 0} be a martingale with respect to a filtration (Fn)(\mathcal{F}_n), and let TT be a stopping time with respect to (Fn)(\mathcal{F}_n). Suppose any one of the following conditions holds:

(a) Bounded stopping time. T≤NT \leq N almost surely for some fixed constant N<∞N < \infty.

(b) Almost sure finiteness with bounded increments. P(T<∞)=1\mathbb{P}(T < \infty) = 1, and there is a constant c<∞c < \infty such that ∣Xn+1−Xn∣≤c|X_{n+1} - X_n| \leq c for all nn, and E[T]<∞\mathbb{E}[T] < \infty.

(c) Uniform integrability / boundedness. P(T<∞)=1\mathbb{P}(T < \infty) = 1, and there exists M<∞M < \infty such that ∣Xn∧T∣≤M|X_{n \wedge T}| \leq M almost surely for all nn. Then XTX_T is integrable and

E[XT]=E[X0].\mathbb{E}[X_T] = \mathbb{E}[X_0].
LemmaStopped process is a martingale

If (Xn)(X_n) is a martingale with respect to (Fn)(\mathcal{F}_n) and TT is a stopping time, then the stopped process (Xn∧T)n≥0(X_{n \wedge T})_{n \geq 0} is also a martingale with respect to (Fn)(\mathcal{F}_n). In particular E[Xn∧T]=E[X0]\mathbb{E}[X_{n \wedge T}] = \mathbb{E}[X_0] for every nn.

Proof

We use the martingale transform technique: write the stopped process as an initial value plus a discrete stochastic integral against a predictable, bounded strategy. Define the predictable process Hn=1{T≥n}H_n = \mathbf{1}_{\{T \geq n\}} for n≥1n \geq 1. Since {T≥n}={T≤n−1}c∈Fn−1\{T \geq n\} = \{T \leq n-1\}^c \in \mathcal{F}_{n-1} (as TT is a stopping time), HnH_n is Fn−1\mathcal{F}_{n-1}-measurable: it is predictable, meaning its value is known one step before it is used. Note Hn∈{0,1}H_n \in \{0,1\}. Observe the algebraic identity

Xn∧T=X0+∑k=1nHk(Xk−Xk−1).X_{n \wedge T} = X_0 + \sum_{k=1}^{n} H_k (X_k - X_{k-1}).

Indeed, if T≥nT \geq n then every term Hk=1H_k = 1 for k≤nk \leq n and the sum telescopes to Xn−X0X_n - X_0, giving Xn∧T=XnX_{n\wedge T} = X_n, correct. If T=m<nT = m < n, then Hk=1H_k = 1 for k≤mk \leq m and Hk=0H_k = 0 for k>mk > m, so the sum telescopes to Xm−X0X_m - X_0, giving Xn∧T=Xm=XTX_{n \wedge T} = X_m = X_T, again correct. Now check the martingale property for Yn:=Xn∧TY_n := X_{n \wedge T}. We have

Yn−Yn−1=Hn(Xn−Xn−1).Y_n - Y_{n-1} = H_n(X_n - X_{n-1}).

Since HnH_n is Fn−1\mathcal{F}_{n-1}-measurable and bounded (by 11), and Xn−Xn−1X_n - X_{n-1} is integrable,

E[Yn−Yn−1∣Fn−1]=Hn E[Xn−Xn−1∣Fn−1]=Hn⋅0=0,\mathbb{E}[Y_n - Y_{n-1} \mid \mathcal{F}_{n-1}] = H_n \,\mathbb{E}[X_n - X_{n-1} \mid \mathcal{F}_{n-1}] = H_n \cdot 0 = 0,

using the "pull-out" property of conditional expectation (since HnH_n is Fn−1\mathcal{F}_{n-1}-measurable and bounded) together with the martingale property E[Xn∣Fn−1]=Xn−1\mathbb{E}[X_n \mid \mathcal{F}_{n-1}] = X_{n-1}. Hence E[Yn∣Fn−1]=Yn−1\mathbb{E}[Y_n \mid \mathcal{F}_{n-1}] = Y_{n-1}. Also YnY_n is Fn\mathcal{F}_n-measurable (a finite sum/composition of Fn\mathcal{F}_n-measurable pieces, since T∧nT \wedge n and hence the identity of which XkX_k, k≤nk\le n, appears is Fn\mathcal{F}_n-measurable), and E∣Yn∣≤∑k=0nE∣Xk∣<∞\mathbb{E}|Y_n| \le \sum_{k=0}^n \mathbb{E}|X_k| <\infty. So (Yn)(Y_n) is a martingale. Taking expectations, E[Yn]=E[Y0]=E[X0]\mathbb{E}[Y_n] = \mathbb{E}[Y_0] = \mathbb{E}[X_0] for all nn. ■\blacksquare

∎
Proof

Proof of the Optional Stopping Theorem. By the Lemma, E[Xn∧T]=E[X0]\mathbb{E}[X_{n \wedge T}] = \mathbb{E}[X_0] for every n≥0n \geq 0. The strategy in every case is to pass to the limit n→∞n \to \infty and show E[Xn∧T]→E[XT]\mathbb{E}[X_{n\wedge T}] \to \mathbb{E}[X_T].

Case (a): T≤NT \leq N a.s. Take n=Nn = N directly: T∧N=TT \wedge N = T almost surely, so XN∧T=XTX_{N \wedge T} = X_T a.s., and

E[XT]=E[XN∧T]=E[X0].\mathbb{E}[X_T] = \mathbb{E}[X_{N \wedge T}] = \mathbb{E}[X_0].

Integrability of XTX_T follows since XT=XN∧TX_T = X_{N\wedge T} takes finitely many possible "time-indices" 0,…,N0,\dots,N, and E∣XT∣≤∑k=0NE∣Xk1T=k∣≤∑k=0NE∣Xk∣<∞\mathbb{E}|X_T| \le \sum_{k=0}^N \mathbb{E}|X_k \mathbf 1_{T=k}|\le \sum_{k=0}^N \mathbb E|X_k|<\infty.

Case (b): T<∞T < \infty a.s., increments bounded by cc, E[T]<∞\mathbb{E}[T] < \infty. Since T<∞T < \infty a.s., Xn∧T→XTX_{n \wedge T} \to X_T almost surely as n→∞n \to \infty (the sequence is eventually constant, equal to XTX_T, on the a.s. event {T<∞}\{T<\infty\}). We justify passing the limit inside the expectation via dominated convergence. Write

∣Xn∧T∣≤∣X0∣+∑k=1n∧T∣Xk−Xk−1∣≤∣X0∣+c T,|X_{n \wedge T}| \leq |X_0| + \sum_{k=1}^{n\wedge T} |X_k - X_{k-1}| \leq |X_0| + c \, T,

using the telescoping bound and the increment bound ∣Xk−Xk−1∣≤c|X_k - X_{k-1}|\le c; the right side does not depend on nn and dominates ∣Xn∧T∣|X_{n\wedge T}| for all nn. Its expectation is E∣X0∣+c E[T]<∞\mathbb{E}|X_0| + c\,\mathbb{E}[T] < \infty by hypothesis, so it is an integrable dominating random variable. By the Dominated Convergence Theorem,

E[XT]=lim⁡n→∞E[Xn∧T]=E[X0].\mathbb{E}[X_T] = \lim_{n\to\infty} \mathbb{E}[X_{n \wedge T}] = \mathbb{E}[X_0].

XTX_T is integrable because it is dominated by the integrable variable ∣X0∣+cT|X_0| + cT.

Case (c): T<∞T < \infty a.s., ∣Xn∧T∣≤M|X_{n\wedge T}| \le M a.s. for all nn. Again Xn∧T→XTX_{n\wedge T} \to X_T a.s. since T<∞T<\infty a.s. The constant MM is itself an integrable dominating random variable (it dominates ∣Xn∧T∣|X_{n\wedge T}| for every nn, uniformly), so Dominated Convergence again gives

E[XT]=lim⁡n→∞E[Xn∧T]=E[X0],\mathbb{E}[X_T] = \lim_{n \to \infty} \mathbb{E}[X_{n \wedge T}] = \mathbb{E}[X_0],

and XTX_T is integrable since ∣XT∣≤M|X_T|\le M. ■\blacksquare

∎
CorollaryWald's identity for random walks

Let ξ1,ξ2,…\xi_1, \xi_2, \dots be i.i.d. with E[ξ1]=μ\mathbb{E}[\xi_1] = \mu and E∣ξ1∣<∞\mathbb{E}|\xi_1| < \infty, let Sn=ξ1+⋯+ξnS_n = \xi_1 + \cdots + \xi_n (with S0=0S_0=0), and let TT be a stopping time (w.r.t. Fn=σ(ξ1,…,ξn)\mathcal{F}_n = \sigma(\xi_1,\dots,\xi_n)) with E[T]<∞\mathbb{E}[T] < \infty. Then

E[ST]=μ E[T].\mathbb{E}[S_T] = \mu \, \mathbb{E}[T].
Proof

The process Xn:=Sn−nμX_n := S_n - n\mu is a martingale: it is adapted, integrable since E∣Sn−nμ∣≤n(E∣ξ1∣+∣μ∣)<∞\mathbb{E}|S_n - n\mu| \le n(\mathbb E|\xi_1|+|\mu|) <\infty, and

E[Xn+1∣Fn]=Xn+E[ξn+1−μ∣Fn]=Xn+E[ξn+1]−μ=Xn,\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n + \mathbb{E}[\xi_{n+1} - \mu \mid \mathcal{F}_n] = X_n + \mathbb{E}[\xi_{n+1}] - \mu = X_n,

using independence of ξn+1\xi_{n+1} from Fn\mathcal{F}_n. This has increments Xn+1−Xn=ξn+1−μX_{n+1}-X_n = \xi_{n+1}-\mu, not bounded in general, so we cannot always invoke case (b) of the Optional Stopping Theorem directly with a uniform constant cc; instead one applies a standard extension (proved by the same dominated-convergence architecture, using E[T]<∞\mathbb E[T]<\infty together with E∣ξ1∣<∞\mathbb E|\xi_1|<\infty to build an integrable dominating variable ∣X0∣+∑k=1T∣ξk−μ∣|X_0| + \sum_{k=1}^{T}|\xi_k - \mu|, whose expectation is finite by Wald's first identity for the auxiliary nonnegative walk ∣ξk−μ∣|\xi_k-\mu|) to get E[XT]=E[X0]=0\mathbb{E}[X_T] = \mathbb{E}[X_0] = 0, i.e. E[ST]=μ E[T]\mathbb{E}[S_T] = \mu\,\mathbb{E}[T]. ■\blacksquare

∎

Worked examples

Example 1: Gambler's ruin with a biased coin, computed via a martingale. A gambler starts with fortune k=3k=3 dollars. At each round she bets $1 on a coin with P(heads)=p=0.6\mathbb{P}(\text{heads}) = p = 0.6, P(tails)=q=0.4\mathbb{P}(\text{tails}) = q = 0.4, winning $1 on heads and losing $1 on tails, independently each round. She stops when her fortune hits 00 (ruin) or N=8N = 8 (target). Let SnS_n be her fortune after nn rounds, S0=3S_0 = 3, and T=min⁡{n:Sn∈{0,8}}T = \min\{n : S_n \in \{0,8\}\}. Since p≠qp \neq q, (Sn)(S_n) is not itself a martingale (it is a submartingale, drifting upward since E[Sn+1∣Fn]=Sn+(p−q)=Sn+0.2>Sn\mathbb{E}[S_{n+1}\mid \mathcal F_n] = S_n + (p-q) = S_n + 0.2 > S_n). Instead, the classical trick is to exponentially reweight: set r=q/p=0.4/0.6=2/3r = q/p = 0.4/0.6 = 2/3, and define

Mn:=rSn.M_n := r^{S_n}.

Check the martingale property directly. Conditional on Fn\mathcal{F}_n, Sn+1=Sn+1S_{n+1} = S_n + 1 w.p. pp and Sn−1S_n - 1 w.p. qq, so

E[Mn+1∣Fn]=rSn(p r+q r−1).\mathbb{E}[M_{n+1} \mid \mathcal{F}_n] = r^{S_n}\big(p\, r + q\, r^{-1}\big).

Compute pr+qr−1=0.6⋅23+0.4⋅32=0.4+0.6=1p r + q r^{-1} = 0.6 \cdot \tfrac23 + 0.4 \cdot \tfrac32 = 0.4 + 0.6 = 1. So E[Mn+1∣Fn]=rSn=Mn\mathbb{E}[M_{n+1}\mid \mathcal F_n] = r^{S_n} = M_n: (Mn)(M_n) is indeed a martingale. It is bounded: since 0≤Sn≤80 \le S_n \le 8 always (fortune stops changing once absorbed, or more precisely Sn∧T∈[0,8]S_{n\wedge T}\in[0,8] for all nn), Mn∧T=rSn∧T∈[r8,1]=[(2/3)8,1]M_{n\wedge T} = r^{S_{n\wedge T}} \in [r^8, 1] = [(2/3)^8, 1], so case (c) of the Optional Stopping Theorem applies (with T<∞T<\infty a.s. since a biased random walk absorbed at two finite barriers hits one a.s. — standard fact for random walks with nonzero drift and finite state space of the walk before absorption). Applying the theorem,

E[MT]=E[M0]=rS0=r3=(2/3)3=8/27.\mathbb{E}[M_T] = \mathbb{E}[M_0] = r^{S_0} = r^3 = (2/3)^3 = 8/27.

Let u=P(ST=0)u = \mathbb{P}(S_T = 0) (probability of ruin) and 1−u=P(ST=8)1-u = \mathbb{P}(S_T = 8). Then

E[MT]=u⋅r0+(1−u)⋅r8=u+(1−u)r8.\mathbb{E}[M_T] = u \cdot r^0 + (1-u)\cdot r^8 = u + (1-u) r^8.

Solve:

u+(1−u)r8=r3  ⟹  u(1−r8)=r3−r8  ⟹  u=r3−r81−r8.u + (1-u) r^8 = r^3 \implies u(1 - r^8) = r^3 - r^8 \implies u = \frac{r^3 - r^8}{1 - r^8}.

Numerically, r=2/3r = 2/3, so r3=8/27≈0.296296r^3 = 8/27 \approx 0.296296, r8=256/6561≈0.039018r^8 = 256/6561 \approx 0.039018. Thus

u=0.296296−0.0390181−0.039018=0.2572780.960982≈0.26774.u = \frac{0.296296 - 0.039018}{1 - 0.039018} = \frac{0.257278}{0.960982} \approx 0.26774.

So the probability the gambler is ruined before reaching $8, starting from $3 with p=0.6p=0.6, is approximately 0.2677\mathbf{0.2677}, and the probability of reaching $8 first is approximately 0.73230.7323. As a sanity check with the closed form for gambler's ruin, u=rk−rN1−rNu = \dfrac{r^k - r^N}{1 - r^N} with k=3k=3, N=8N=8 matches exactly what we derived, confirming the martingale computation reproduces the classical formula.

Example 2: A Pólya urn martingale — exact computation at a fixed finite time. An urn starts with 11 red and 11 blue ball. At each step, a ball is drawn uniformly at random and replaced together with one additional ball of the same color (so the urn grows by one ball each step). Let RnR_n be the number of red balls after nn steps (so the urn has n+2n+2 balls total after step nn, since it started with 22), and let

Xn:=Rnn+2X_n := \frac{R_n}{n+2}

be the fraction of red balls, with Fn=σ(R0,…,Rn)\mathcal{F}_n = \sigma(R_0, \dots, R_n).

Claim: (Xn)n≥0(X_n)_{n\geq 0} is a martingale. Given Fn\mathcal{F}_n, with probability Xn=Rn/(n+2)X_n = R_n/(n+2) a red ball is drawn (and one more red is added), giving Rn+1=Rn+1R_{n+1} = R_n + 1; otherwise (probability 1−Xn1 - X_n) Rn+1=RnR_{n+1} = R_n. So

E[Rn+1∣Fn]=Xn(Rn+1)+(1−Xn)Rn=Rn+Xn.\mathbb{E}[R_{n+1} \mid \mathcal{F}_n] = X_n (R_n+1) + (1-X_n) R_n = R_n + X_n.

Then

E[Xn+1∣Fn]=E[Rn+1∣Fn]n+3=Rn+Xnn+3=Rn+Rn/(n+2)n+3=Rn(n+3)/(n+2)n+3=Rnn+2=Xn.\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = \frac{\mathbb{E}[R_{n+1}\mid \mathcal F_n]}{n+3} = \frac{R_n + X_n}{n+3} = \frac{R_n + R_n/(n+2)}{n+3} = \frac{R_n(n+3)/(n+2)}{n+3} = \frac{R_n}{n+2} = X_n.

So indeed E[Xn+1∣Fn]=Xn\mathbb{E}[X_{n+1}\mid\mathcal F_n]=X_n, confirming the martingale property. Since 0≤Xn≤10 \le X_n \le 1 always, integrability is automatic and in fact (Xn)(X_n) is a bounded martingale. Now let's use this concretely. Take N=5N=5: what is E[X5]\mathbb{E}[X_5], and what is E[R5]\mathbb{E}[R_5]? Since (Xn)(X_n) is a martingale started at X0=R0/2=1/2X_0 = R_0/2 = 1/2, and N=5N=5 is a (trivial, deterministic) bounded stopping time, case (a) of the theorem gives immediately

E[X5]=E[X0]=12,\mathbb{E}[X_5] = \mathbb{E}[X_0] = \frac12,

so, since the urn has 77 balls after step 55,

E[R5]=7⋅E[X5]=7⋅12=3.5.\mathbb{E}[R_5] = 7 \cdot \mathbb{E}[X_5] = 7 \cdot \frac12 = 3.5.

This matches the well-known exchangeability fact for Pólya urns (the color proportion process is a martingale converging to a Beta-distributed limit; here Rn/(n+2)→Beta(1,1)=Uniform(0,1)R_n/(n+2)\to \mathrm{Beta}(1,1) = \mathrm{Uniform}(0,1) in distribution, whose mean is 1/21/2, consistent with E[Xn]=1/2\mathbb{E}[X_n] = 1/2 for every nn, not just in the limit — a clean illustration of the martingale property holding exactly at each finite step, not merely asymptotically). This computation would have been considerably more painful by direct combinatorics (summing over all (5k)\binom{5}{k}-type sequences of draws); the martingale property gives the answer in one line.

CounterexampleOptional stopping fails without an integrability/boundedness condition

Let (ξi)(\xi_i) be i.i.d. with P(ξi=1)=P(ξi=−1)=1/2\mathbb{P}(\xi_i = 1) = \mathbb{P}(\xi_i=-1) = 1/2 (symmetric simple random walk), S0=0S_0 = 0, Sn=∑i=1nξiS_n = \sum_{i=1}^n \xi_i, and Fn=σ(ξ1,…,ξn)\mathcal{F}_n = \sigma(\xi_1,\dots,\xi_n). Then (Sn)(S_n) is a martingale: adapted, integrable (E∣Sn∣≤n<∞\mathbb E|S_n|\le n <\infty), and

E[Sn+1∣Fn]=Sn+E[ξn+1]=Sn+0=Sn.\mathbb{E}[S_{n+1}\mid \mathcal F_n] = S_n + \mathbb E[\xi_{n+1}] = S_n + 0 = S_n.

Let T=min⁡{n:Sn=1}T = \min\{n : S_n = 1\}, the first time the walk reaches level 11. It is a classical fact (recurrence of simple symmetric random walk) that P(T<∞)=1\mathbb{P}(T < \infty) = 1: the walk hits 11 eventually almost surely. So TT is a well-defined, a.s.-finite stopping time, and by construction

XT=ST=1a.s.,so E[ST]=1.X_T = S_T = 1 \quad \text{a.s.}, \qquad \text{so } \mathbb{E}[S_T] = 1.

But E[S0]=0≠1=E[ST]\mathbb{E}[S_0] = 0 \neq 1 = \mathbb{E}[S_T].

Which hypothesis of the <span class="wiki-link-missing">Optional Stopping Theorem</span> fails, and why does the conclusion break? Condition (a) fails: TT is not bounded — it can be arbitrarily large with positive probability, e.g. P(T>n)>0\mathbb P(T>n)>0 for every nn. Condition (b) fails: although increments are bounded (∣ξi∣=1|\xi_i|=1), E[T]=∞\mathbb{E}[T] = \infty (a standard computation shows the hitting time of level 11 for symmetric simple random walk has infinite mean, since TT is (sub-)distributed like a first-passage time with heavy, non-integrable tails P(T=2k−1)∼c k−3/2\mathbb P(T = 2k-1) \sim c\, k^{-3/2}). Condition (c) fails: Sn∧TS_{n \wedge T} is not uniformly bounded — before hitting 11, the walk can dip arbitrarily far into negative territory, so sup⁡n∣Sn∧T∣\sup_n |S_{n\wedge T}| is a.s. finite pointwise (it equals the depth of the minimum before hitting 11) but has no deterministic finite bound MM valid on the whole sample space, and indeed E[sup⁡n∣Sn∧T∣]=∞\mathbb{E}[\sup_n |S_{n\wedge T}|] = \infty. This exhibits precisely how each hypothesis is doing real work: remove all three simultaneously (as here) and the "obvious" conclusion E[XT]=E[X0]\mathbb{E}[X_T]=\mathbb{E}[X_0] is false, even though TT is a perfectly legitimate, almost-surely-finite stopping time and (Sn)(S_n) is a genuine martingale.

Scope, edge cases & common traps

SituationWhat holdsWhat can fail
TT bounded by fixed NNOST always applies (case a)—
T<∞T<\infty a.s., bounded increments, E[T]<∞\mathbb E[T]<\inftyOST applies (case b)Fails if E[T]=∞\mathbb E[T]=\infty, even with bounded increments (see counterexample-style hitting times)
T<∞T<\infty a.s., Xn∧TX_{n\wedge T} uniformly boundedOST applies (case c)Fails if only pointwise-finite, not uniformly bounded
TT finite a.s. but none of (a)-(c) holdNo general conclusionE[XT]≠E[X0]\mathbb E[X_T]\ne \mathbb E[X_0] possible, as shown above
Submartingale, TT boundedE[XT]≥E[X0]\mathbb E[X_T]\ge \mathbb E[X_0]Equality not guaranteed
Supermartingale, TT boundedE[XT]≤E[X0]\mathbb E[X_T]\le \mathbb E[X_0]Equality not guaranteed

The mathematician behind it

Origins · 1 minJoseph Leo Doob and how this was discovered
JL
Joseph Leo Doob
1910–2004 · American mathematician, Institute for Advanced Study and University of Illinois

Doob built the modern theory of martingales in the 1940s–1950s, formalizing what had been an informal notion from gambling theory (the word "martingale" itself comes from a betting strategy and, earlier, a piece of horse tack) into a rigorous framework grounded in measure-theoretic conditional expectation. His 1953 book Stochastic Processes established martingale convergence theorems, the optional stopping theorem, and maximal inequalities as central tools, influencing the subsequent development of stochastic calculus by Itô, Meyer, and others.

History
- 1930s: informal "martingale" betting strategies studied in early probability, notably by Ville, who coined the probabilistic use of the term.
- 1940: Doob begins developing a rigorous measure-theoretic theory of martingales building on Kolmogorov's axiomatic probability.
- 1953: Doob publishes Stochastic Processes, containing the martingale convergence theorem and optional stopping results in essentially modern form.
- 1960s–1970s: Paul-André Meyer and others extend the theory to continuous time, developing the general theory of processes and semimartingales.
- 1970s–1980s: martingale methods become foundational in mathematical finance following the Harrison–Pliska martingale approach to option pricing.
What exactly distinguishes a martingale from an i.i.d. sum with mean zero?

An i.i.d. mean-zero sum Sn=ξ1+⋯+ξnS_n = \xi_1+\cdots+\xi_n is a special case of a martingale, but martingales are far more general: increments need not be independent or identically distributed, only conditionally mean-preserving given the past. For instance, the Pólya urn fraction process in the worked example is a martingale whose increments are neither independent nor identically distributed, yet the defining property E[Xn+1∣Fn]=Xn\mathbb E[X_{n+1}\mid \mathcal F_n]=X_n still holds exactly. This flexibility is precisely why martingale theory subsumes and extends classical results about Random Walks to much broader settings, including urn models, branching processes, and stochastic approximation algorithms.

Is every martingale bounded, or does it always converge?

No to both, in general. Martingales need not be bounded — the simple symmetric random walk is an unbounded martingale that does not converge (it oscillates and is recurrent). Boundedness (or, more generally, L1L^1-boundedness: sup⁡nE∣Xn∣<∞\sup_n \mathbb E|X_n|<\infty) is precisely the extra hypothesis needed for the martingale convergence theorem to guarantee almost sure convergence to an integrable limit. The Pólya urn martingale is bounded (values in [0,1][0,1]) and does converge almost surely, to a Beta(1,1)(1,1) = Uniform(0,1)(0,1) random limit, illustrating the theorem; the random walk illustrates its necessity.

Why do we need the filtration (Fn)(\mathcal F_n) explicitly, rather than just talking about the process (Xn)(X_n) alone?

The martingale property is not a property of the marginal distributions of XnX_n alone; it is a property relative to a specified flow of information. The same process can be a martingale with respect to one filtration and fail to be one with respect to a coarser or finer filtration containing different information. Conventionally one takes the natural filtration Fn=σ(X0,…,Xn)\mathcal F_n = \sigma(X_0,\dots,X_n), but the definition explicitly allows any filtration to which (Xn)(X_n) is adapted and for which the conditional expectation identity holds — this is essential in applications where Fn\mathcal F_n encodes auxiliary information beyond XnX_n itself, such as an entire vector of correlated observables.

How does this connect to concentration inequalities like Azuma-Hoeffding?

The martingale transform construction used in the Lemma's proof — writing Xn∧T−X0X_{n\wedge T}-X_0 as a sum of predictable, bounded multiples of martingale increments — is exactly the mechanism behind Azuma's inequality, which bounds P(∣Xn−X0∣≥t)\mathbb P(|X_n - X_0|\ge t) for martingales with bounded increments via an exponential supermartingale argument. This makes martingale increment bounds (as in condition (b) of the theorem) doubly useful: they enable both optional stopping and sharp tail bounds, which is why martingale methods are ubiquitous in the probabilistic analysis of randomized algorithms.

What is the practical difference between condition (b) and condition (c) in the theorem, and when would I choose one over the other?

Condition (b) is convenient when increments are naturally bounded (e.g. ±1\pm 1 steps, as in ruin problems) and you can bound E[T]\mathbb E[T] directly, often via Wald-type identities or explicit tail estimates. Condition (c) is convenient when the process itself is confined to a bounded range by construction — for instance the exponential martingale (q/p)Sn(q/p)^{S_n} in gambler's ruin, or the Pólya urn fraction Xn∈[0,1]X_n\in[0,1] — so uniform boundedness of Xn∧TX_{n\wedge T} is immediate without needing any control on E[T]\mathbb E[T] at all. In problems with absorbing barriers, (c) is usually the cleaner route; in problems where the process is unbounded but increments are controlled, (b) is typically the tool of choice.

Before this

Where this leads