Fair games and information
Definition 2.3.1
(Filtration, martingale and stopping time)
Let be an increasing sequence of information sets, formally a filtration of -algebras. A discrete-time martingale is adapted to this filtration, satisfies , and obeys .
A stopping time takes values in and satisfies for each .
Its conditional next increment has mean zero; this is a precise fairness statement, not a promise that every random stopping rule preserves the initial expectation. Whether one has stopped by time can be decided using information available by that time. Hitting a specified set is a stopping time for an adapted process. Looking into the future to select the last winning time need not be one.
Bounded optional stopping
Theorem 2.3.2
(Optional stopping at a bounded time)
Let be a martingale and a stopping time. For every deterministic integer , . In particular, if almost surely, then .
Proof
(Stopping as a predictable selection of increments)
For every deterministic and any stopping time , the stopped time is bounded. Its increment decomposition is
The indicator is -measurable, since its complement is . The increments are integrable and the indicators bounded, so conditional expectation gives each summand mean zero. Consequently
For an unbounded , passing to the limit in the expectation requires a separate justification; almost-sure convergence alone does not suffice.
A finite fair gambler's ruin problem
Fix an integer and . Start , and let , where the are independent and each is or with probability . Use the natural filtration generated by the increments. Put , with infimum of the empty set equal to infinity. The unstopped walk is defined for all ; the stopped walk stays in .
Proposition 2.3.3
(Fair gambler's ruin)
In this model almost surely, , and .
Proof
(Two martingales stopped at bounded times)
Both and are martingales. The second follows by expanding and using the independent increment's mean and square . Bounded stopping yields, for each ,
Because , the second equality bounds . Monotone convergence then gives , so almost surely. Since the stopped position is bounded, dominated convergence applies to both the position and its square. Writing gives
Proof X-ray
Finiteness is earned, not assumed
The argument never applies optional stopping at the unbounded time itself. It applies the bounded theorem at , where the theorem is automatic, and only then lets . The two martingales do different jobs. The quadratic martingale converts the bounded range into the bound , uniform in ; monotone convergence turns this into , which is where finiteness of comes from. The linear martingale then identifies . Passing to the limit in the two identities uses dominated convergence for the positions and their squares and monotone convergence for . The hypothesis doing the work is that the stopped position is bounded; the next section shows that without it the same limiting step fails.
The proof did not assume finite expected stopping time in order to obtain it. The formulas concern this fair, independent-increment model; biased walks need different martingales and give different probabilities.
Common mistake
(Using the fair formulas for a biased walk)
The formula relies on being a martingale. If each step is with probability and with probability , take and : then and , not . For a biased walk is not a martingale, and a different martingale is needed.
Worked example 2.3.4
(Upper barrier five, start two)
Take and . The probability of reaching first is , the probability of reaching first is , and the expected number of steps is . The quadratic martingale gives a check: , while .
Worked example 2.3.5
(A start next to both barriers)
Take and . The first step reaches or , so deterministically, in agreement with ; and is the probability that the first step is upward. In this edge case is bounded, so the bounded theorem applies directly and no limit is needed.
Worked example 2.3.6
(A bounded time that looks ahead)
In the same walk let if and otherwise. Then is bounded, yet . The theorem is not contradicted: does not belong to , so is not a stopping time. The decision to stop at time zero used the first step, which had not yet happened.
Why an unbounded stopping time is different
The finiteness proof above relied on the bounded range of the stopped walk. Remove the lower barrier and the conclusion fails.
Counterexample mode
An almost-surely finite stopping time can break optional stopping
Start a fair walk at and let . For each positive integer , stop instead on reaching either or . Translating the preceding finite-interval result gives probability of reaching first, and the finite-interval hitting time is almost surely finite. As these events increase to : a finite path reaching has a finite minimum. Hence almost surely and almost surely, whereas .
Thus substituting directly into the bounded theorem would falsely give . In fact : if it were finite, then and dominated convergence would imply , a contradiction. The limit step needs domination: for instance a stopped process bounded by a constant, or bounded through when increments are bounded by one and .
Common mistake
(Inferring a finite mean from almost-sure finiteness)
This example also shows that almost-surely finite stopping is not the same as a bounded stopping time or finite expected duration. In gambler's ruin, came from the bounded range, not from .
Exercises
Quick check
(In the finite fair game with and initial position , find the probability of hitting first and the mean time to hit either boundary.)
Apply and .
Solution · Answer
The probability is and the mean duration is .
Quick check
(For the same game, explain why applying bounded optional stopping to is legitimate even before proving that is finite.)
Check the two hypotheses of the bounded theorem.
Solution · Answer
The minimum is at most the deterministic integer and is a stopping time; the martingales at each deterministic time are integrable. The theorem applies without assuming .
Quick check
(In the unbounded example, why is the union of the events that the walk hits before , over ?)
Prove both inclusions.
Solution · Answer
If the walk hits before , then is finite. Conversely, a finite path up to the first hit of has a finite minimum; choosing larger than its absolute value ensures that was not reached first.