Optional stopping theorem

From Wikipedia, the free encyclopedia

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 X1, X2, X3, ... be a martingale and τ a stopping time with respect to X1, X2, X3, ... . If
(a) \mathbb{E}\tau<\infty,
and
(b) there exists a constant c such that \operatorname{E}(\vert X_{i+1} - X_i \vert) \leq c for all i,
then
\mathbb{E}X_{\tau}=\mathbb{E}X_1.

[edit] 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[X1]. 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 Yn = Xn2 − n martingale from the examples section. If τ is the time at which we first reach ±m, then 0 = E[Y1] = E[Yτ] = m2 − E[τ]. We immediately get E[τ] = m2.
  • 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.

[edit] External links