Published
In this lesson
Wide tables, equations, and code scroll sideways. Swipe, or Tab to focus them and use the left and right arrow keys.
Martingales
You will learn: Check conditional fairness and retain unfinished paths when applying bounded stopping.
Start with: Random walk · Conditioning and independence
A fair process is fair given what is already known. A martingale is an integrable process Mₜ whose value is determined by the history available at time t and satisfies E[Mₜ₊₁∣history through t]=Mₜ. Review conditioning, expectation, and random walks before choosing a stopping rule.
For independent steps Yᵢ taking values −1 or +1 with P(Yᵢ=1)=p, let Sₜ=Σᵢ₌₁ᵗYᵢ. Its predictable drift is 2p−1 per step. Subtracting it gives:
Here Fₜ denotes the information in the first t steps. The displayed raw walk S is a martingale only when p=1/2; the compensated M is a martingale for every fixed p in this model.
Independent ±1 increments start at zero. Mₜ=Sₜ−(2p−1)t subtracts predictable drift. Both position and its elapsed-time correction freeze when a boundary is reached; unfinished paths stop at N. At p=0.5, S and M coincide and are martingales.
Solid blue: one seeded path. Dashed red: exact expectation over all paths under the model. The graph joins integer times; it is not a histogram or an uncertainty band. Changing only the time cap preserves the sample prefix.
| Full-population quantity at cap N | Value |
|---|---|
| Expected stopped position | 0.000000 |
| Expected stopped compensated value | 0.000000 |
| Expected elapsed steps | 7.812331 |
| Boundary not yet reached | 0.1444644 |
Keep the unfinished paths in the average
| Outcome by cap N | Probability | Conditional mean S | Contribution to full mean S | Contribution to full mean M |
|---|---|---|---|---|
| Upper target reached | 0.8555356 | 1.000000 | 0.8555356 | 0.8555356 |
| Lower boundary reached | 0.000000 | Undefined: zero probability | 0.000000 | 0.000000 |
| Unfinished at cap | 0.1444644 | -5.922118 | -0.8555356 | -0.8555356 |
The mean among paths that reached the target is a conditional average. Excluding unfinished paths changes the question and can make a fair process look profitable. This calculation retains all terminal outcomes and uses no Monte Carlo estimate for its probabilities. Near-zero computed expectations can contain floating-point rounding residue.
Inspect the stopped sample, including its clock
| Time cap | Elapsed steps | Stopped S | Stopped M |
|---|---|---|---|
| 0 | 0 | 0 | 0.000000 |
| 1 | 1 | 1 | 1.000000 |
| 2 | 1 | 1 | 1.000000 |
| 3 | 1 | 1 | 1.000000 |
| 4 | 1 | 1 | 1.000000 |
| 5 | 1 | 1 | 1.000000 |
| 6 | 1 | 1 | 1.000000 |
| 7 | 1 | 1 | 1.000000 |
| 8 | 1 | 1 | 1.000000 |
| 9 | 1 | 1 | 1.000000 |
| 10 | 1 | 1 | 1.000000 |
| 11 | 1 | 1 | 1.000000 |
| 12 | 1 | 1 | 1.000000 |
| 13 | 1 | 1 | 1.000000 |
| 14 | 1 | 1 | 1.000000 |
| 15 | 1 | 1 | 1.000000 |
| 16 | 1 | 1 | 1.000000 |
| 17 | 1 | 1 | 1.000000 |
| 18 | 1 | 1 | 1.000000 |
| 19 | 1 | 1 | 1.000000 |
| 20 | 1 | 1 | 1.000000 |
| 21 | 1 | 1 | 1.000000 |
| 22 | 1 | 1 | 1.000000 |
| 23 | 1 | 1 | 1.000000 |
| 24 | 1 | 1 | 1.000000 |
| 25 | 1 | 1 | 1.000000 |
| 26 | 1 | 1 | 1.000000 |
| 27 | 1 | 1 | 1.000000 |
| 28 | 1 | 1 | 1.000000 |
| 29 | 1 | 1 | 1.000000 |
| 30 | 1 | 1 | 1.000000 |
Constant mean is a consequence, not the definition
Averaging the conditional equality gives E[Mₜ₊₁]=E[Mₜ], so a martingale has constant expectation. The converse fails. Start X₀=0, choose X₁ equally likely to be −1 or +1, then set X₂=−X₁. Every unconditional mean is zero, but after observing X₁ the next value is known to be its opposite. E[X₂∣X₁]=−X₁, not X₁.
For a biased walk with p=0.6, the next raw step has expected value 0.2. The compensated increment is Y−0.2: it is 0.8 with probability 0.6 and −1.2 with probability 0.4. Its conditional mean is 0.6·0.8−0.4·1.2=0, because the next independent step has the same probabilities after every recorded history.
What can a stopping rule know?
A stopping time allows you to decide whether to stop now using only the history through now. The first time a target is reached qualifies. “The time of the highest value over the next hundred steps” generally does not: identifying that time requires future information.
For a martingale and a stopping time τ bounded by a fixed finite N, optional stopping gives E[Mτ]=E[M₀]. Integrability and adaptation are part of the martingale definition. Bounded stopping is one sufficient condition; it is not permission to use every unbounded rule.
The experiment stops at a target or at N, whichever comes first. Its expectation calculation propagates all possible states, rather than averaging only the paths that happened to finish. For a biased walk, the compensated stopped value is Sτ−(2p−1)τ. After stopping, the clock τ freezes too; subtracting drift times the later display time would define a different process.
Make a prediction
If you only average target-reaching paths and get a profit, have you contradicted optional stopping?
Explore the answer
No. You have conditioned on reaching the target. That excludes the losses and unfinished outcomes needed for the original unconditional expectation. The table keeps both the group probabilities and their contributions to the full average visible.
An unbounded rule that changes the answer
For a fair walk, stop at its first visit to +1 with no lower boundary. This happens with probability one, so the terminal value is +1. Yet every capped version Smin(τ,N) has expectation zero. How can both statements hold?
Take N=2. Half the paths hit +1 immediately. The other half start with a down step: one quarter then return to zero, and one quarter reach −2. The capped expectation is (1/2)·1+(1/4)·0+(1/4)·(−2)=0. Among the paths that hit +1, the conditional mean is one. Among the unfinished half, it is −1.
As N grows, fewer paths remain unfinished, but their negative values still contribute enough to balance the target hits. The stopping time has infinite expectation, and this family of stopped values is not uniformly integrable. Taking an almost-sure limit does not by itself allow exchanging limit and expectation:
Other sufficient optional-stopping conditions include uniformly bounded process values with almost-surely finite stopping, or uniformly bounded increments together with finite expected stopping time. A proof must check the condition actually being used. Two-sided gambler’s ruin and a one-sided uncapped target are different stopping problems.
Beyond coin games
Brownian motion with zero drift is a continuous-time martingale with respect to its natural history. Brownian motion with deterministic drift becomes one after removing that drift. Independence of increments is sufficient in these constructions, but not required in the general martingale definition.
A martingale statement is always relative to specified information. Revealing future steps changes that information and can destroy the conditional-mean property. It is also a mathematical model statement, not a guarantee that observed financial prices, forecasts, or betting protocols satisfy it.
Sources
Random Services: martingale introduction develops conditional fairness and integrability. Its stopping-time lesson gives sufficient optional-stopping conditions and the one-sided random-walk counterexample. The two-step enumeration and compensated-increment calculation above are directly reproducible.