Optional stopping theorem

In probability theory, the optional stopping theorem (or optional sampling theorem) says that, under certain conditions, the expected value of a martingale at a stopping time is equal to its initial value (and also expected value at any deterministic time). One version of the theorem is given below:

Let X₁, X₂, X₃, ... be a martingale and τ a stopping time with respect to X₁, X₂, X₃, ... . If

(a) $\mathbb {E} \tau <\infty ,$

and

(b) there exists a constant c such that $\mathbb {E} (\vert X_{i+1}-X_{i}\vert )\leq c$ for all i,

then

$\mathbb {E} X_{\tau }=\mathbb {E} X_{1}.$

Applications

• We can use it to prove the impossibility of successful betting strategies for a gambler with a finite lifetime (which gives condition (a)) and a house limit on bets (condition (b)). Suppose that the gambler can wager up to c dollars on a fair coin flip at times 1, 2, 3, etc., winning his wager if the coin comes up heads and losing it if the coin comes up tails. Suppose further that he can quit whenever he likes, but cannot predict the outcome of gambles that haven't happened yet. Then the gambler's fortune over time is a martingale, and the time τ at which he decides to quit (or goes broke and is forced to quit) is a stopping time. So the theorem says that E[X_τ] = E[X₁]. In other words, the gambler leaves with the same amount of money on average as when he started.

• Suppose we have a random walk that goes up or down by one with equal probability on each step. Suppose further that the walk stops if it reaches 0 or m; the time at which this first occurs is a stopping time. If we happen to know that the expected time that the walk ends is finite (say, from Markov chain theory), the optional stopping theorem tells us that the expected position when we stop is equal to the initial position a. Solving a = pm + (1 − p)0 for the probability p that we reach m before 0 gives p = a/m.

• Now consider a random walk that starts at 0 and stops if we reach −m or +m, and use the Y_n = X_n² − n martingale from the examples section. If τ is the time at which we first reach ±m, then 0 = E[Y₁] = E[Y_τ] = m² − E[τ]. We immediately get E[τ] = m².

• Care must be taken, however, to ensure that all the conditions of theorem hold. For example, suppose in the last example, we had instead a 'one sided' stopping time that stopped once the random walk exceeds a certain value. Then, since the value, and hence expected value at this stopping time must be exactly equal to our limit, we can see from the failure of the optional stopping theorem that the expected time for the random walk to exceed any non-zero level must be infinite.

Proof

Assume the conditions in the version given above and let $X_{t}^{\tau }$ denote the stopped process. This is also a martingale. Obviously it converges to $X_{\tau }$ almost surely. Now writing the stopped process as

$X_{t}^{\tau }=X_{1}+\sum _{i=1}^{\tau \land t-1}(X_{i+1}-X_{i})$

gives

$|X_{t}^{\tau }|\leq |X_{1}|+\sum _{i=1}^{\tau \land t-1}|X_{i+1}-X_{i}|\leq |X_{1}|+c\cdot (\tau -1).$

Since the right side is integrable the dominated convergence theorem implies $\mathbb {E} X_{1}=\mathbb {E} X_{t}^{\tau }\rightarrow \mathbb {E} X_{\tau }$.

External links

• Doob's Optional Stopping Theorem