Fairness with information
A random walk can be stopped according to its observed history: stop when it reaches a boundary, for example. The time chosen is random and can depend on previous increments, so substituting it into a formula proved for a fixed time needs justification. Martingales encode the particular form of fairness that makes such an argument possible.
Let be an increasing sequence of -fields on a probability space. Think of as the information available at time . A random variable is -measurable when its value is determined by this information. An integrable process adapted to the filtration is a martingale if
Integrable means at each fixed time. Adapted means is -measurable. Fairness is conditional on everything already known, not merely the assertion that all the unconditional means are equal. For example, if are independent with mean zero and finite first moments, then , , is a martingale for its natural filtration: the next increment is independent of the past and has conditional mean zero. Taking expectations in the definition shows at every fixed .
Counterexample mode
Constant means are not enough
Let be equally likely to be or , set , , and , and let . All three values have mean zero, but . Once is known, the next value is predictable and the process is not fair.
Stopping using only past information
A random variable taking values in is a stopping time if for every . By time one can decide whether stopping has already occurred. A first hitting time of an adapted process has this property: . By contrast, choosing the last time a walk visits zero before a future horizon generally requires seeing the future.
Common mistake
(Stopping at the best time in hindsight)
A rule such as stopping at the largest value among is not a stopping time, even though it is bounded by . For a fair walk from , let be the earliest time at which that maximum is attained. Then is the complement of the path , so it depends on and is not in . The four equally likely paths give , hence . Bounded stopping fails because the decision to stop at time one uses the next increment.
The key identity is a finite sum of increments:
The indicator is -measurable: the decision to continue through step is made using information available by time . It is bounded, and the increment is integrable. Consequently the defining property of conditional expectation gives
Theorem 19.1.1
(Bounded stopping)
If is an integrable discrete-time martingale and is a stopping time with almost surely for a deterministic integer , then .
Proof
(A finite sum of fair increments)
Apply the displayed identity with and take expectations term by term in the finite sum. Each term has expectation zero, and almost surely.
Proof X-ray
What each hypothesis does in the stopped sum
The whole proof rests on writing as plus increments switched on by the indicators . The stopping-time property enters only here: is the complement of , so each switch is set before the increment it controls. Integrability of the increments and boundedness of the indicator make each product integrable, so that the tower property can replace the increment by its conditional mean, which is zero.
The deterministic bound is used twice, and only at the end: it makes the sum finite, so that expectation passes through it term by term, and it gives . For an unbounded the identity still holds for every ; what can fail is only the limit . The worked example below closes that gap by domination, and the doubled-bet counterexample shows that without such control it cannot be closed.
Two martingales for a fair walk
Let be independent with , and . With the natural filtration, both and are martingales. For the second, expand the square and use and . All fixed-time variables are integrable.
Worked example 19.1.2
(Absorption probability and mean time)
Choose integers and , and let be the first time the walk reaches or . From any interior state, a run of consecutive increments forces absorption within the next steps. Independent successive blocks therefore give
Thus almost surely and . The sum is at most . Bounded stopping applied to gives . Since and almost surely, dominated convergence yields . At absorption is either or , so
Similarly, bounded stopping for gives . Dominated convergence handles the bounded square and monotone convergence handles . Because , we obtain
For and , the upper boundary is hit with probability and the mean absorption time is . These formulas require the fair, independent increment model; they do not say that every path takes eight steps.
Worked example 19.1.3
(Ruin probability for a biased walk)
Let the increments be independent with and , where and , and stop at the first time the walk from reaches or . With , the process is a martingale, because
A run of consecutive up-steps again forces absorption, now with probability per block, so almost surely. Bounded stopping gives , and lies between and , so dominated convergence yields . Writing , this reads , hence
For , and , we have and the probability is . A first-step check agrees: and give .
Worked example 19.1.4
(Capping a hitting time at two steps)
For a fair walk from , let be the first time . This is unbounded, but is a stopping time bounded by , so . A direct check over the four equally likely paths confirms it. If , then and ; this covers the paths and . The level cannot be first reached at the even time , so on the paths and the walk is stopped at the cap, with values and . The mean is .
The same bookkeeping holds for every cap : since , we get . As grows, the unstopped paths become rarer but carry ever more negative values, which is why is not the limit of .
Why unbounded stopping needs more care
Counterexample mode
A fair game stopped at its first win
Toss a fair coin repeatedly. Start with capital zero and bet on heads at toss , stopping further bets after the first head. Let be the first head and let be the capital after tosses. Each fixed-time capital is integrable and the next conditional expected gain is zero: before it is with equal probabilities, and after it is zero. Thus is a martingale and is a stopping time. Moreover , so is finite almost surely, and on that event. Yet .
Indeed if a head has appeared and otherwise; its expectation is zero for each . The rare loss has magnitude growing with , so almost-sure convergence to does not justify interchanging expectation and limit. The strategy also requires arbitrarily large credit. This example refutes optional stopping under almost-sure finiteness alone.
Exercises
Quick check
(Let be independent with . Show is a martingale, where .)
Solution · Answer
. Conditional on the past, and each have expectation zero, since is known, and . Adaptedness and fixed-time integrability are immediate.
Quick check
(For the absorbing walk above with and , compute both absorption probabilities and the mean absorption time.)
Solution · Answer
The upper probability is , the lower probability , and .
Quick check
(Let be the first head in independent fair coin tosses. Is a stopping time bounded by a constant? If is any integrable martingale for the same filtration, what is ?)
Solution · Answer
Yes: is determined by the first tosses for , and is the whole space for . It is at most , so bounded stopping gives .
Quick check
(In the doubled-bet example compute . Explain why this does not contradict almost-sure convergence.)
Solution · Answer
The difference is zero unless the first tosses are tails, when its absolute value is . Its expectation is for every . Almost-sure convergence imposes no general convergence of absolute expectations; these rare losses have growing size.