37.04.01 · probability / 04-conditional-expectation-martingales

Discrete-Time Martingales, Stopping Times, and Optional Stopping

shipped3 tiersLean: none

Anchor (Master): Williams — Probability with Martingales Ch. 10-14; Durrett §4.1-4.8; Neveu — Discrete-Parameter Martingales (North-Holland, 1975) Ch. I-IV

Intuition Beginner

A martingale is the mathematics of a fair game. Picture your bankroll while gambling at a table where every bet is exactly fair: on average you neither win nor lose on the next round. The honest statement is that, given everything you have seen so far, your expected fortune after the next bet equals your fortune right now. That single sentence is the whole idea. A martingale is a running total whose best forecast for tomorrow, using all of today's information, is simply today's value.

The reason this matters is that "fair on every step" turns out to control the long run, not just one step. The headline fact is bleak-proof: no clever betting scheme that decides how much to wager based only on the past can turn a fair game into a profitable one. You may double your stake after losses, sit out certain rounds, or quit on a hunch, but as long as each individual bet stays fair, your average fortune stays put. People rediscover this the hard way every time a roulette system fails.

The second idea is a rule about when you are allowed to stop. A stopping time is a quitting rule you could actually obey in real time: "leave when I first reach 100 dollars" is legal, because at each moment you know whether the rule has fired, but "leave one bet before my peak" is illegal, because you would need to see the future to know your peak. The question of whether stopping at a clever moment can beat a fair game is exactly the question of optional stopping.

The takeaway: a martingale is a fair-game fortune, and the deep result is that fairness survives both your betting strategy and your stopping strategy, under reasonable conditions. When those conditions fail, the game can be beaten — and seeing exactly how they fail is the most instructive part.

Visual Beginner

Picture three columns of information growing taller as time passes. At each time step a new piece of information is revealed and added to the column, and your fortune is one number computed from everything revealed so far.

Top band: time 0, little information, fortune at its starting height. Each lower band adds the next step's information. The dashed line is the forecast: averaged over all the ways the next step could go, the fortune lands back at its current height. That is the fair-game balance. The jagged overlay is one real run, which of course wanders up and down — the balance is a statement about the average over many runs, not about any single path.

A stopping rule is a flag you can raise looking only at the bands above the current one. The optional-stopping question is whether raising that flag at a smart moment lets the fortune at the flag differ, on average, from the starting height.

Worked example Beginner

We test "you cannot beat the system" on the simplest fair game: a coin-flip walk. Start with fortune $0$ . Each round flip a fair coin; win $1$ on heads, lose $1$ on tails. After each round your fortune is the running sum of these plus-or-minus-one steps. This is a fair game: at any moment, the expected change on the next flip is $\frac{1}{2} (+ 1) + \frac{1}{2} (- 1) = 0$ , so your expected next fortune equals your current fortune. It is a martingale.

Step 1. A naive strategy. You decide to bet only on rounds $1, 3, 5$ and sit out the even rounds, hoping to "skip the unlucky flips." On a skipped round your fortune does not change. On a played round it goes up or down by $1$ with equal chance. The expected change on every round, played or skipped, is still $0$ . So after any number of rounds your expected fortune is still $0$ . Skipping rounds changed nothing on average.

Step 2. A doubling strategy. Now you bet $1$ ; if you lose you bet $2$ ; if you lose again you bet $4$ , doubling until your first win, then stop. Compute the expected fortune at the moment you stop. If your first win comes on round $k$ , you lost $1 + 2 + \dots + 2^{k - 2} = 2^{k - 1} - 1$ dollars on the earlier rounds and won $2^{k - 1}$ on round $k$ , for a net of exactly $+ 1$ . The chance the first win is on round $k$ is $(1/2)^{k}$ . So you finish $+ 1$ with probability $1$ — it looks like a sure profit.

Step 3. Where the catch hides. To guarantee that $+ 1$ you must be willing to keep doubling without limit. The total you might need to stake before winning has no finite ceiling: the expected size of your largest bet is infinite. With any real bankroll the strategy fails on the run where you lose many times in a row, and that rare run is large enough to wipe out all the small wins. The fair-game balance was never actually broken — it was only hidden by ignoring the unbounded stake.

Step 4. The honest score. If instead you cap the game at a fixed number of rounds, or cap your bankroll, the expected final fortune is exactly $0$ again, every time. The doubling "system" only seemed to win because it secretly required infinite resources and unbounded time.

What this tells us: a fair game stays fair under any past-based betting rule, and the only way to appear to beat it is to smuggle in an unbounded bet or an unbounded waiting time. The optional-stopping theorem is precisely the bookkeeping that says when the smuggling is impossible.

Check your understanding Beginner

Exercise (easy, multiple choice).

Which best describes the defining property of a martingale fortune $M_{0}, M_{1}, M_{2}, \dots$ ?

A. Each $M_{n}$ is larger than the previous one B. Given all information up to time $n$ , the expected value of $M_{n + 1}$ equals $M_{n}$ C. The fortune always returns to its starting value D. The fortune is a constant

Hint

Think about the fair-game forecast: what is your best guess for tomorrow's fortune given everything you know today?

Answer

B. A martingale is a sequence whose expected next value, conditioned on all the information observed so far, equals its current value. This is the fair-game condition. Option A describes an increasing sequence (a submartingale is the "at least fair" version); option C confuses the average behaviour with the behaviour of every path; option D is the constant case, only one special example. The forecast statement in B is what makes the no-beating-the-system result true.

Formal definition Intermediate+

Fix a probability space $(Ω, F, P)$ . A filtration is an increasing sequence of sub- $σ$ -algebras $F_{0} \subseteq F_{1} \subseteq \dots \subseteq F$ , where $F_{n}$ models the information available at time $n$ . A process $(X_{n})_{n \geq 0}$ is adapted to $(F_{n})$ if each $X_{n}$ is $F_{n}$ -measurable, and predictable if each $X_{n}$ is $F_{n - 1}$ -measurable (for $n \geq 1$ ); a predictable process is one whose value at time $n$ is decided one step in advance.

Throughout we take conditional expectation $E [\cdot ∣ G]$ as a verified construction from the Radon-Nikodym theorem 02.07.08: for $X \in L^{1} (P)$ and a sub- $σ$ -algebra $G \subseteq F$ , $E [X ∣ G]$ is the $P$ -a.s. unique $G$ -measurable element of $L^{1}$ with $\int_{G} E [X ∣ G] d P = \int_{G} X d P$ for all $G \in G$ . The properties used below are: linearity; the tower property $E [E [X ∣ G] ∣ H] = E [X ∣ H]$ when $H \subseteq G$ ; taking out what is known, $E [Y X ∣ G] = Y E [X ∣ G]$ for bounded $G$ -measurable $Y$ ; conditional Jensen $φ (E [X ∣ G]) \leq E [φ (X) ∣ G]$ for convex $φ$ ; and the $L^{2}$ characterisation of $E [\cdot ∣ G]$ as orthogonal projection onto $L^{2} (G)$ . We do not re-derive existence here.

Definition (martingale, sub/supermartingale). An adapted process $(X_{n})$ with each $X_{n} \in L^{1} (P)$ is a martingale (relative to $(F_{n})$ ) if $$ \mathbb{E}[X_{n+1} \mid \mathcal{F}n] = X_n \quad \text{a.s. for every } n \ge 0. $$ It is a submartingale if $\mathbb{E}[X{n+1} \mid \mathcal{F}n] \ge X_n $(a " f a v o u r ab l e " g am e) an d a * * s u p er ma r t in g a l e * * i f$ \mathbb{E}[X{n+1} \mid \mathcal{F}_n] \le X_n $(an " u n f a v o u r ab l e " g am e) . T ak in g u n co n d i t i o na l e x p ec t a t i o n s, ama r t in g a l e ha sco n s t an t m e an$ \mathbb{E}[X_n] = \mathbb{E}[X_0]$; a submartingale has nondecreasing mean; a supermartingale nonincreasing.

Definition (martingale transform). If $(C_{n})_{n \geq 1}$ is predictable and $(X_{n})$ is adapted, the transform $C ∙ X$ is the process $(C ∙ X)_{n} = \sum_{k = 1}^{n} C_{k} (X_{k} - X_{k - 1})$ with $(C ∙ X)_{0} = 0$ . Reading $C_{k}$ as the stake placed on game $k$ and $X_{k} - X_{k - 1}$ as the per-unit payoff, $C ∙ X$ is the discrete stochastic integral of $C$ against $X$ — the gambler's accumulated winnings.

Definition (stopping time). A map $τ : Ω \to {0, 1, 2, \dots} \cup {\infty}$ is a stopping time for $(F_{n})$ if ${τ \leq n} \in F_{n}$ for every $n$ (equivalently ${τ = n} \in F_{n}$ ). The stopped process is $X_{n}^{τ} := X_{τ \land n}$ , where $τ \land n = min (τ, n)$ . The $σ$ -algebra of the past at $τ$ is $F_{τ} = {A \in F : A \cap {τ \leq n} \in F_{n} for all n}$ , on which $X_{τ}$ is measurable (on ${τ < \infty}$ ).

Counterexamples to common slips Intermediate+

Constant mean is necessary but not sufficient for the martingale property. A process can satisfy $E [X_{n}] = E [X_{0}]$ for all $n$ without being a martingale: the conditional identity $E [X_{n + 1} ∣ F_{n}] = X_{n}$ is strictly stronger than equality of unconditional means. The martingale property is a statement at every $ω$ (a.s.), not merely on average.
Adapted is not predictable. A martingale is adapted, so $X_{n}$ is known at time $n$ ; it is almost never predictable. If a martingale were predictable it would be a.s. constant in $n$ : $X_{n} = E [X_{n} ∣ F_{n - 1}] = X_{n - 1}$ .
The last time is not a stopping time. For the coin-flip walk on $[0, N]$ , "the last time the walk visits $0$ " is not a stopping time — knowing time $n$ is the last visit requires the future. "The first time the walk hits $0$ " is a stopping time.
$E [X_{τ}] = E [X_{0}]$ can fail. For the symmetric walk, $τ =$ first hitting time of level $1$ is a.s. finite, yet $X_{τ} = 1 \neq = 0 = X_{0}$ in expectation. Optional stopping needs a hypothesis (boundedness, or uniform integrability); fairness does not extend to arbitrary unbounded stopping times for free.
A supermartingale stopped is still a supermartingale, not a martingale. Stopping preserves the inequality direction; it does not upgrade a strict supermartingale into a martingale.

Key theorem with proof Intermediate+

Theorem (you cannot beat the system; Doob's optional stopping). Let $(X_{n})$ be a martingale and $(C_{n})_{n \geq 1}$ a bounded predictable process. Then the transform $Y = C ∙ X$ is a martingale with $E [Y_{n}] = 0$ for all $n$ . Consequently, for a stopping time $τ$ the stopped process $X^{τ} = X_{τ \land n}$ is a martingale, so $E [X_{τ \land n}] = E [X_{0}]$ for all $n$ . If in addition any one of the following holds, then $X_{τ} \in L^{1}$ and $E [X_{τ}] = E [X_{0}]$ :

(i) $τ$ is bounded ( $τ \leq N$ a.s. for some constant $N$ );

(ii) $τ < \infty$ a.s., the increments are bounded ( $∣ X_{n} - X_{n - 1} ∣ \leq K$ a.s. for a constant $K$ ) and $E [τ] < \infty$ ;

(iii) the stopped family $(X_{τ \land n})_{n}$ is uniformly integrable.

Proof. Transform is a martingale. Since $C_{n + 1}$ is $F_{n}$ -measurable and bounded, taking out what is known and the martingale property of $X$ give $$ \mathbb{E}[Y_{n+1} - Y_n \mid \mathcal{F}n] = \mathbb{E}[C{n+1}(X_{n+1} - X_n) \mid \mathcal{F}n] = C{n+1},\mathbb{E}[X_{n+1} - X_n \mid \mathcal{F}n] = 0. $$ Each $Y_{n}$ is integrable (a finite sum of products of a bounded factor with $L^{1}$ increments), and $Y$ is adapted, so $\mathbb{E}[Y{n+1} \mid \mathcal{F}_n] = Y_n $:$ Y $i s ama r t in g a l e, w h e n ce$ \mathbb{E}[Y_n] = \mathbb{E}[Y_0] = 0$.

Stopped process is a martingale. Take the predictable strategy $C_{n} = 1_{{τ \geq n}} = 1_{{τ \leq n - 1}^{c}}$ . The event ${τ \geq n} = {τ \leq n - 1}^{c}$ lies in $F_{n - 1}$ , so $C$ is predictable and bounded by $1$ . Its transform telescopes to $$ (C \bullet X)n = \sum{k=1}^n \mathbf{1}{{\tau \ge k}}(X_k - X{k-1}) = X_{\tau \wedge n} - X_0. $$ By the first part this is a martingale of mean zero, so $X^{τ} = X_{τ \land n}$ is a martingale and $E [X_{τ \land n}] = E [X_{0}]$ for every $n$ . This is the precise form of "no past-based stopping rule beats a fair game over a finite horizon."

Passing to the limit $n \to \infty$ under each condition.

(i) If $τ \leq N$ , then $X_{τ \land N} = X_{τ}$ exactly, and the identity at $n = N$ reads $E [X_{τ}] = E [X_{0}]$ .

(ii) Bound the increments of the stopped process: $$ |X_{\tau \wedge n} - X_0| = \Big| \sum_{k=1}^{\tau \wedge n} (X_k - X_{k-1}) \Big| \le \sum_{k=1}^{\tau} |X_k - X_{k-1}| \le K,\tau. $$ Since $E [τ] < \infty$ , the integrable random variable $K τ$ dominates the family ${∣ X_{τ \land n} - X_{0} ∣ : n \geq 0}$ . As $τ < \infty$ a.s., $X_{τ \land n} \to X_{τ}$ a.s.; dominated convergence 02.07.05 gives $E [X_{τ \land n}] \to E [X_{τ}]$ , and the left side is constantly $E [X_{0}]$ .

(iii) A uniformly integrable family that converges a.s. converges in $L^{1}$ (Vitali's convergence theorem; uniform integrability plus a.s. convergence yields $L^{1}$ convergence). Here $X_{τ \land n} \to X_{τ}$ a.s. on ${τ < \infty}$ , and uniform integrability of $(X_{τ \land n})$ forces $P (τ < \infty) = 1$ and $L^{1}$ convergence, so $E [X_{τ \land n}] \to E [X_{τ}]$ , again equal to $E [X_{0}]$ . $□$

Bridge. The optional-stopping theorem builds toward the entire edifice of martingale limit theory and reappears in the convergence theorem and the Markov-chain hitting-time calculus, and it appears again in the continuous-time optional sampling of stochastic analysis. The foundational reason a fair game cannot be beaten is the predictability of the stake: because $C_{n + 1}$ is fixed before the increment $X_{n + 1} - X_{n}$ is revealed, the conditional expectation of the gain is the stake times zero, and this is exactly the discrete shadow of the non-anticipation that makes the Itô integral a martingale. The three conditions (i)-(iii) are one phenomenon in three guises — each is a way to license the interchange of limit and expectation $lim_{n} E [X_{τ \land n}] = E [lim_{n} X_{τ \land n}]$ , the central insight that the only way to break $E [X_{τ}] = E [X_{0}]$ is to lose uniform integrability at infinity. Condition (iii) generalises the other two: a bounded stopping time and the bounded-increment-integrable-time pair both force uniform integrability of the stopped family, so the bridge is that optional stopping is, at bottom, a uniform-integrability theorem dressed in the language of fair games. Putting these together, optional stopping is the engine that converts the abstract martingale identity into concrete computations of hitting probabilities and expected durations, which is exactly the gambler's-ruin calculus carried out below.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Let $(X_{n})$ be a martingale and $φ$ a convex function with $φ (X_{n}) \in L^{1}$ for all $n$ . Prove $(φ (X_{n}))$ is a submartingale. Deduce that $(∣ X_{n} ∣)$ and (when $X_{n} \in L^{2}$ ) $(X_{n}^{2})$ are submartingales.

Hint

Apply conditional Jensen and the martingale identity.

Answer

By conditional Jensen, $E [φ (X_{n + 1}) ∣ F_{n}] \geq φ (E [X_{n + 1} ∣ F_{n}]) = φ (X_{n})$ , where the equality uses the martingale property. Adaptedness of $φ (X_{n})$ and the integrability hypothesis make $(φ (X_{n}))$ a submartingale. Taking $φ (x) = ∣ x ∣$ gives $(∣ X_{n} ∣)$ a submartingale; $φ (x) = x^{2}$ gives $(X_{n}^{2})$ a submartingale when $X_{n} \in L^{2}$ . Rubric: full credit for the Jensen step, the use of the martingale identity inside $φ$ , and both specialisations. This is the source of Doob's maximal and $L^{p}$ inequalities.

Exercise 5 (medium, numeric).

A gambler starts with $3$ dollars and plays the symmetric coin-flip game (win or lose $1$ per round, fair) until reaching $0$ or $10$ . Using optional stopping on the martingale $X_{n}$ , compute the probability of reaching $10$ before $0$ .

Hint

Let $τ$ be the first hitting time of ${0, 10}$ . Apply $E [X_{τ}] = E [X_{0}] = 3$ and solve for the absorption probabilities.

Answer

Let $τ$ be the first time the walk hits $0$ or $10$ ; $τ < \infty$ a.s. and is bounded in increments with $E [τ] < \infty$ , so condition (ii) of optional stopping applies. Then $E [X_{τ}] = E [X_{0}] = 3$ . At $τ$ the walk is at $0$ (probability $1 - p$ ) or $10$ (probability $p$ ), so $E [X_{τ}] = 10 p = 3$ , giving $p = 3/10 = 0.3$ . The probability of ruin (hitting $0$ first) is $1 - p = 0.7$ . For the symmetric walk on ${0, \dots, N}$ from $a$ , the chance of reaching $N$ first is $a / N$ .

Exercise 7 (hard, symbolic).

Consider the asymmetric simple random walk with $P (ξ_{k} = + 1) = p$ , $P (ξ_{k} = - 1) = q = 1 - p$ , $p \neq = q$ , started at $a \in {0, 1, \dots, N}$ . Find a martingale of the form $r^{X_{n}}$ and use optional stopping to compute the probability of reaching $N$ before $0$ .

Hint

Choose $r$ so that $E [r^{ξ}] = 1$ , i.e. $p r + q / r = 1$ .

Answer

Set $r = q / p$ . Then $E [r^{ξ_{k}}] = p (q / p) + q (p / q) = q + p = 1$ , so $E [r^{X_{n + 1}} ∣ F_{n}] = r^{X_{n}} E [r^{ξ_{n + 1}}] = r^{X_{n}}$ : the process $Y_{n} = r^{X_{n}} = (q / p)^{X_{n}}$ is a martingale. Let $τ$ be the first hitting time of ${0, N}$ (a.s. finite, bounded increments, integrable). Optional stopping gives $E [Y_{τ}] = Y_{0} = r^{a}$ . Writing $P_{N}$ for the probability of reaching $N$ first, $E [Y_{τ}] = r^{0} (1 - P_{N}) + r^{N} P_{N} = (1 - P_{N}) + r^{N} P_{N} = r^{a}$ . Solving, $$ P_N = \frac{r^a - 1}{r^N - 1} = \frac{(q/p)^a - 1}{(q/p)^N - 1}. $$ Rubric: full credit for the choice $r = q / p$ making $r^{X_{n}}$ a martingale, the optional-stopping application, and the closed-form solution. As $p \to 1/2$ , $r \to 1$ and a limiting computation recovers $P_{N} = a / N$ , matching the symmetric case.

Exercise 8 (hard, symbolic).

State and prove Wald's identity: if $(ξ_{k})$ are i.i.d. with $E [ξ_{k}] = μ \in R$ and $E ∣ ξ_{k} ∣ < \infty$ , $S_{n} = \sum_{k = 1}^{n} ξ_{k}$ , and $τ$ is a stopping time (for the natural filtration) with $E [τ] < \infty$ , then $E [S_{τ}] = μ E [τ]$ .

Hint

The process $M_{n} = S_{n} - n μ$ is a martingale; bound $∣ M_{τ \land n} - M_{(τ \land n) - 1} ∣$ and apply the integrable-time form of optional stopping.

Answer

The centred sum $M_{n} = S_{n} - n μ$ is a martingale: $E [M_{n + 1} ∣ F_{n}] = M_{n} + E [ξ_{n + 1} - μ ∣ F_{n}] = M_{n}$ by independence. To apply optional stopping when the increments $ξ_{k}$ are not bounded, control the stopped sum directly. Let $T_{n} = \sum_{k = 1}^{τ \land n} ∣ ξ_{k} ∣$ . Since ${τ \geq k} \in F_{k - 1}$ is independent of $∣ ξ_{k} ∣$ , $$ \mathbb{E}\Big[\sum_{k=1}^{\tau} |\xi_k|\Big] = \mathbb{E}\Big[\sum_{k=1}^{\infty} |\xi_k| \mathbf{1}{{\tau \ge k}}\Big] = \sum{k=1}^\infty \mathbb{E}|\xi_k|, \mathbb{P}(\tau \ge k) = \mathbb{E}|\xi_1| \sum_{k \ge 1} \mathbb{P}(\tau \ge k) = \mathbb{E}|\xi_1|,\mathbb{E}[\tau] < \infty, $$ using $E [τ] = \sum_{k \geq 1} P (τ \geq k)$ . Thus $\sum_{k = 1}^{τ} ∣ ξ_{k} ∣$ is an integrable dominating function for $(S_{τ \land n})$ , and the same computation with $ξ_{k}$ in place of $∣ ξ_{k} ∣$ gives $E [S_{τ}] = μ E [τ]$ by dominated convergence 02.07.05 applied to $E [M_{τ \land n}] = 0$ , i.e. $E [S_{τ \land n}] = μ E [τ \land n] \to μ E [τ]$ . Rubric: full credit for the martingale identification, the independence-driven interchange (this is the heart of Wald), and the limit. Wald's identity computes expected durations of sequential procedures and is the cornerstone of sequential analysis.

Advanced results Master

The structural backbone of discrete martingale theory is the Doob decomposition: every adapted integrable process $(X_{n})$ has a unique decomposition $X_{n} = X_{0} + M_{n} + A_{n}$ with $M$ a martingale, $M_{0} = 0$ , and $A$ predictable with $A_{0} = 0$ , given by $A_{n} = \sum_{k = 1}^{n} E [X_{k} - X_{k - 1} ∣ F_{k - 1}]$ and $M_{n} = X_{n} - X_{0} - A_{n}$ . The process $X$ is a submartingale precisely when $A$ is a.s. nondecreasing. Specialising to $X_{n}^{2}$ for an $L^{2}$ -martingale produces the predictable quadratic variation (or angle bracket) $⟨ X ⟩_{n} = \sum_{k = 1}^{n} E [(X_{k} - X_{k - 1})^{2} ∣ F_{k - 1}]$ , the unique predictable increasing process with $X_{n}^{2} - ⟨ X ⟩_{n}$ a martingale; it is the discrete-time progenitor of the quadratic variation $[B]_{t} = t$ of Brownian motion, and $⟨ X ⟩_{n} = n$ recovers Exercise 3.

Optional stopping combines with the optional sampling theorem in its sharper form: if $(X_{n})$ is a uniformly integrable martingale and $σ \leq τ$ are stopping times, then $E [X_{τ} ∣ F_{σ}] = X_{σ}$ . Uniform integrability is the exact dividing line. A uniformly integrable martingale is one of the form $X_{n} = E [X_{\infty} ∣ F_{n}]$ for an integrable terminal variable $X_{\infty}$ — a closed martingale — and for such processes the optional-sampling identity holds for all pairs of stopping times without finiteness or boundedness side-conditions. The Radon-Nikodym viewpoint of 02.07.08 makes this transparent: $X_{n}$ is the density of the measure $A \mapsto \int_{A} X_{\infty} d P$ restricted to $F_{n}$ , against $P ∣_{F_{n}}$ , and optional sampling is the restriction of that density identity to the $σ$ -algebra $F_{τ}$ .

The martingale convergence theorem is the limit companion of optional stopping. Doob's upcrossing inequality bounds the expected number $U_{N} ([a, b])$ of upcrossings of an interval $[a, b]$ by time $N$ : $(b - a) E [U_{N} ([a, b])] \leq E [(X_{N} - a)^{-}]$ . An $L^{1}$ -bounded supermartingale cannot oscillate across any rational interval infinitely often, so it converges a.s. to an integrable limit $X_{\infty}$ . Convergence is in $L^{1}$ (and the martingale closes with terminal value $X_{\infty}$ ) if and only if the family is uniformly integrable; $L^{p}$ convergence for $p > 1$ holds for $L^{p}$ -bounded martingales via Doob's $L^{p}$ inequality $∥ sup_{n} ∣ X_{n} ∣ ∥_{p} \leq \frac{p}{p - 1} ∥ X_{\infty} ∥_{p}$ .

The gambler's-ruin problem is the canonical proving ground for the whole apparatus. For the asymmetric walk with up-probability $p \neq = q$ , the three martingales $X_{n} - (p - q) n$ , $X_{n}^{2} - ⟨ X ⟩_{n}$ , and $(q / p)^{X_{n}}$ deliver, via optional stopping, the ruin probability, the expected duration, and the boundary-absorption split. The exponential martingale $r^{X_{n}}$ with $r = q / p$ is the discrete Doléans-Dade exponential; the change of measure $d Q / d P ∣_{F_{n}} = (q / p)^{X_{n}}$ is a Radon-Nikodym derivative that conjugates the $p$ -walk into the $q$ -walk, the discrete Girsanov transform. This single example exhibits martingale, stopping time, optional stopping, change of measure, and the convergence dichotomy in one computation.

Synthesis. The foundational reason optional stopping holds is that the stopped martingale $X_{τ \land n} - X_{0}$ is the transform $(C ∙ X)_{n}$ by the predictable stake $C_{k} = 1_{{τ \geq k}}$ , and a predictable stake against a fair increment has zero conditional mean — this is exactly the mechanism by which non-anticipation makes the Itô integral a martingale, the discrete shadow of $d B^{2} = d t$ accounting carried by $⟨ X ⟩$ . Putting these together, the Doob decomposition, the angle bracket, optional sampling, and the convergence theorem are one structure: every adapted process splits into a predictable drift plus a martingale, the martingale part is controlled at stopping times by uniform integrability, and the same uniform integrability is dual to the closure $X_{n} = E [X_{\infty} ∣ F_{n}]$ that the Radon-Nikodym theorem produces. This is exactly the central insight that organises the subject: a martingale is a consistent system of conditional-expectation densities, optional stopping is the restriction of that consistency to stopping-time $σ$ -algebras, and the convergence theorem is the time-asymptotic Radon-Nikodym identification of the system with a single limit density. The gambler's ruin generalises this from a slogan into arithmetic, and it is dual to the continuous-time optional sampling that drives the Feynman-Kac and Girsanov machinery downstream.

Full proof set Master

The optional-stopping theorem and its three conditions are proved in full in the Key theorem section. The remaining Master claims are recorded here.

Proposition (Doob decomposition; uniqueness). Every adapted process $(X_{n})$ with $X_{n} \in L^{1}$ admits a unique decomposition $X_{n} = X_{0} + M_{n} + A_{n}$ with $M$ a martingale, $A$ predictable, $M_{0} = A_{0} = 0$ .

Proof. For existence, set $A_{n} = \sum_{k = 1}^{n} E [X_{k} - X_{k - 1} ∣ F_{k - 1}]$ , which is $F_{n - 1}$ -measurable (predictable) and integrable, and $M_{n} = X_{n} - X_{0} - A_{n}$ . Then $E [M_{n} - M_{n - 1} ∣ F_{n - 1}] = E [X_{n} - X_{n - 1} ∣ F_{n - 1}] - (A_{n} - A_{n - 1}) = 0$ , so $M$ is a martingale. For uniqueness, suppose $X_{0} + M_{n} + A_{n} = X_{0} + M_{n}^{'} + A_{n}^{'}$ with both $M, M^{'}$ martingales and $A, A^{'}$ predictable, vanishing at $0$ . Then $A_{n} - A_{n}^{'} = M_{n}^{'} - M_{n}$ is both predictable and a martingale; a predictable martingale satisfies $A_{n} - A_{n}^{'} = E [A_{n} - A_{n}^{'} ∣ F_{n - 1}] = E [M_{n}^{'} - M_{n} ∣ F_{n - 1}] = M_{n - 1}^{'} - M_{n - 1} = A_{n - 1} - A_{n - 1}^{'}$ , so the difference is constant in $n$ , hence equal to its value $0$ at $n = 0$ . Thus $A = A^{'}$ and $M = M^{'}$ . $□$

Proposition (Doob's upcrossing inequality). Let $(X_{n})$ be a supermartingale and $a < b$ . Let $U_{N} ([a, b])$ be the number of upcrossings of $[a, b]$ completed by time $N$ . Then $(b - a) E [U_{N} ([a, b])] \leq E [(X_{N} - a)^{-}]$ .

Proof. Define a predictable ${0, 1}$ -valued strategy $C$ that "buys at $a$ and sells at $b$ ": set $C_{1} = 1_{{X_{0} < a}}$ and, for $n \geq 2$ , $C_{n} = 1_{{C_{n - 1} = 1}} 1_{{X_{n - 1} \leq b}} + 1_{{C_{n - 1} = 0}} 1_{{X_{n - 1} < a}}$ , which is $F_{n - 1}$ -measurable. Each completed upcrossing increases the transform $(C ∙ X)_{N}$ by at least $b - a$ , while the final incomplete crossing costs at most $(X_{N} - a)^{-}$ , so $(C ∙ X)_{N} \geq (b - a) U_{N} ([a, b]) - (X_{N} - a)^{-}$ . Since $C$ is predictable, bounded, and nonnegative and $X$ is a supermartingale, $(C ∙ X)$ is a supermartingale with $E [(C ∙ X)_{N}] \leq 0$ . Taking expectations of the inequality yields $(b - a) E [U_{N} ([a, b])] \leq E [(X_{N} - a)^{-}]$ . $□$

Proposition (martingale convergence theorem). An $L^{1}$ -bounded supermartingale $(X_{n})$ converges a.s. to an integrable limit $X_{\infty}$ .

Proof. By the upcrossing inequality, for fixed rationals $a < b$ , $E [U_{\infty} ([a, b])] = lim_{N} E [U_{N} ([a, b])] \leq \frac{s u p _{N} E [( X _{N} - a ) ^{-} ]}{b - a} \leq \frac{∣ a ∣ + s u p _{N} E ∣ X _{N} ∣}{b - a} < \infty$ by $L^{1}$ -boundedness and monotone convergence, so $U_{\infty} ([a, b]) < \infty$ a.s. The event that $X_{n}$ fails to converge in $[- \infty, \infty]$ is $⋃_{a < b \in Q} {lim inf X_{n} < a < b < lim sup X_{n}}$ , a countable union of sets each forcing infinitely many upcrossings, hence of probability zero. So $X_{n} \to X_{\infty}$ a.s. in $[- \infty, \infty]$ . Fatou's lemma 02.07.05 gives $E ∣ X_{\infty} ∣ \leq lim inf_{n} E ∣ X_{n} ∣ \leq sup_{n} E ∣ X_{n} ∣ < \infty$ , so $X_{\infty}$ is a.s. finite and integrable. $□$

Proposition (closed martingales and uniform integrability). A martingale $(X_{n})$ is uniformly integrable if and only if there exists $X_{\infty} \in L^{1}$ with $X_{n} = E [X_{\infty} ∣ F_{n}]$ for all $n$ ; in that case $X_{n} \to X_{\infty}$ a.s. and in $L^{1}$ .

Proof. If $X_{n} = E [X_{\infty} ∣ F_{n}]$ , then ${X_{n}}$ is uniformly integrable because the family ${E [Y ∣ G] : G a sub- σ -algebra}$ is uniformly integrable for any fixed $Y \in L^{1}$ (conditional Jensen on $x \mapsto ∣ x ∣ 1_{∣ x ∣ > c}$ plus absolute continuity of the integral). Conversely, if $(X_{n})$ is uniformly integrable, it is $L^{1}$ -bounded, so by the convergence theorem $X_{n} \to X_{\infty}$ a.s.; uniform integrability upgrades this to $L^{1}$ convergence (Vitali). For fixed $m$ and $A \in F_{m}$ , the martingale property gives $\int_{A} X_{n} d P = \int_{A} X_{m} d P$ for all $n \geq m$ ; passing $n \to \infty$ under $L^{1}$ convergence yields $\int_{A} X_{\infty} d P = \int_{A} X_{m} d P$ , which is the defining identity $X_{m} = E [X_{\infty} ∣ F_{m}]$ . $□$

Connections Master

Conditional expectation and the Radon-Nikodym theorem 02.07.08 are the load-bearing prerequisite. The martingale property is an identity between conditional expectations, a closed martingale is literally the Radon-Nikodym density process $X_{n} = d (X_{\infty} d P) / d P ∣_{F_{n}}$ , and the optional-sampling theorem is the restriction of that density identity to a stopping-time $σ$ -algebra; without the existence and tower property of conditional expectation proved there, nothing in this unit is even definable.

Fatou's lemma and dominated convergence 02.07.05 are the analytic engine behind every limit taken here. The passage from the finite-horizon identity $E [X_{τ \land n}] = E [X_{0}]$ to the optional-stopping conclusion uses dominated convergence under conditions (i) and (ii), and the integrability of the a.s. limit in the convergence theorem is exactly Fatou applied to $∣ X_{n} ∣$ .

The elementary probability of rules and distributions 26.02.01 supplies the concrete random variables and the i.i.d. increment structure that the worked examples and gambler's-ruin computations run on; the binomial step distribution of the simple random walk, expectation linearity, and independence are all taken from there and lifted into the filtration-and-conditioning language of this unit.

Historical & philosophical context Master

The martingale property was isolated by Paul Lévy in the 1930s as a generalisation of sums of independent mean-zero variables, and the name — borrowed from the doubling betting system and ultimately from a piece of horse harness — was attached by Jean Ville in his 1939 Étude critique de la notion de collectif, where martingales served to refute von Mises's frequentist definition of randomness. Joseph Doob gave the theory its modern measure-theoretic form, introducing the systematic conditional-expectation formulation and the optional sampling theorem in his 1940 paper (Trans. Amer. Math. Soc. 47, 455) ^{[Doob 1940]} and codifying it in Stochastic Processes (1953). The upcrossing inequality and the convergence theorem are Doob's; the predictable decomposition of a submartingale is Doob's discrete-time result, later extended to continuous time by Meyer as the Doob-Meyer decomposition.

The gambler's-ruin problem long predates the abstract theory: Pascal and Fermat treated absorption probabilities in their 1654 correspondence, Huygens posed the ruin problem in De ratiociniis in ludo aleae (1657), and Abraham de Moivre gave the asymmetric solution in The Doctrine of Chances (1718) using the recurrence that the exponential martingale now solves in one line. Wald's identity arose from sequential analysis in the 1940s (Wald, Sequential Analysis, 1947), where stopping times model the random sample size of a sequential test. The conceptual content is that conditioning on an information filtration converts the static notion of a fair bet into a dynamic, time-indexed object whose fairness is preserved exactly when no information can be borrowed from the future — through the stake (predictability) or through the stopping rule (the stopping-time condition) — and the optional-stopping theorem is the precise accounting of when that borrowing is impossible.

Bibliography Master

@book{williams1991,
  author    = {Williams, David},
  title     = {Probability with Martingales},
  publisher = {Cambridge University Press},
  series    = {Cambridge Mathematical Textbooks},
  year      = {1991}
}

@article{doob1940,
  author  = {Doob, Joseph L.},
  title   = {Regularity properties of certain families of chance variables},
  journal = {Transactions of the American Mathematical Society},
  volume  = {47},
  number  = {3},
  pages   = {455--486},
  year    = {1940}
}

@book{doob1953,
  author    = {Doob, Joseph L.},
  title     = {Stochastic Processes},
  publisher = {John Wiley \& Sons, New York},
  year      = {1953}
}

@book{durrett2019,
  author    = {Durrett, Rick},
  title     = {Probability: Theory and Examples},
  edition   = {5th},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {2019}
}

@book{neveu1975,
  author    = {Neveu, Jacques},
  title     = {Discrete-Parameter Martingales},
  publisher = {North-Holland, Amsterdam},
  year      = {1975}
}

@book{wald1947,
  author    = {Wald, Abraham},
  title     = {Sequential Analysis},
  publisher = {John Wiley \& Sons, New York},
  year      = {1947}
}

@book{demoivre1718,
  author    = {de Moivre, Abraham},
  title     = {The Doctrine of Chances},
  publisher = {W. Pearson, London},
  year      = {1718}
}

Prerequisites

02.07.05
02.07.08
26.02.01

Tier anchors

beginner: Williams — Probability with Martingales Ch. 10 (informal); Grimmett-Stirzaker — Probability and Random Processes §12.1 (fair games)
intermediate: Williams — Probability with Martingales (CUP, 1991) Ch. 10-11; Durrett — Probability: Theory and Examples (5th ed.) §4.1-4.2, §4.8
master: Williams — Probability with Martingales Ch. 10-14; Durrett §4.1-4.8; Neveu — Discrete-Parameter Martingales (North-Holland, 1975) Ch. I-IV

References

Williams — Probability with Martingales (Cambridge University Press, 1991) · Ch. 10 (martingales), Ch. 11 (the convergence theorem), §10.10 (optional stopping), §10.12 (gambler's ruin)
Doob — Stochastic Processes (Wiley, 1953) · Ch. VII (martingale theory, optional sampling theorem)
Durrett — Probability: Theory and Examples (Cambridge University Press, 5th ed., 2019) · §4.1 (conditional expectation), §4.2 (martingales), §4.8 (optional stopping)
Neveu — Discrete-Parameter Martingales (North-Holland, 1975) · Ch. I-IV (filtrations, stopping times, optional stopping, convergence)
Doob — Regularity properties of certain families of chance variables (Trans. Amer. Math. Soc. 47, 1940) · pp. 455-486; the systematic introduction of the martingale property and optional sampling

Estimated time

beginner: 18m
intermediate: 50m
master: 95m