Optional stopping theorem

Template:Short description Template:Distinguish Template:Refimprove In probability theory, the optional stopping theorem (or sometimes Doob's optional sampling theorem, for American probabilist Joseph Doob) says that, under certain conditions, the expected value of a martingale at a stopping time is equal to its initial expected value. Since martingales can be used to model the wealth of a gambler participating in a fair game, the optional stopping theorem says that, on average, nothing can be gained by stopping play based on the information obtainable so far (i.e., without looking into the future). Certain conditions are necessary for this result to hold true. In particular, the theorem applies to doubling strategies.

The optional stopping theorem is an important tool of mathematical finance in the context of the fundamental theorem of asset pricing.

Statement

A discrete-time version of the theorem is given below, with Template:Math denoting the set of natural integers, including zero.

Let Template:Math be a discrete-time martingale and Template:Math a stopping time with values in Template:Math}, both with respect to a filtration Template:Math. Assume that one of the following three conditions holds:

(Template:EquationRef) The stopping time Template:Math is almost surely bounded, i.e., there exists a constant Template:Math such that Template:Math a.s.

(Template:EquationRef) The stopping time Template:Math has finite expectation and the conditional expectations of the absolute value of the martingale increments are almost surely bounded, more precisely, $𝔼[\tau ]<\mathrm{\infty }$ and there exists a constant Template:Math such that $𝔼[|X_{t+1}-X_t||{ℱ}_t]\le c$ almost surely on the event Template:Math} for all Template:Math.

(Template:EquationRef) There exists a constant Template:Math such that Template:Math a.s. for all Template:Math where Template:Math denotes the minimum operator.

Then Template:Math is an almost surely well defined random variable and $𝔼[X_{\tau }]=𝔼[X_0].$

Similarly, if the stochastic process Template:Math is a submartingale or a supermartingale and one of the above conditions holds, then

$𝔼[X_{\tau }]\ge 𝔼[X_0],$

for a submartingale, and

$𝔼[X_{\tau }]\le 𝔼[X_0],$

for a supermartingale.

Remark

Under condition (Template:EquationNote) it is possible that Template:Math happens with positive probability. On this event Template:Math is defined as the almost surely existing pointwise limit of Template:Math , see the proof below for details.

Applications

• The optional stopping theorem can be used to prove the impossibility of successful betting strategies for a gambler with a finite lifetime (which gives condition (Template:EquationNote)) or a house limit on bets (condition (Template:EquationNote)). 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 Template:Math at which he decides to quit (or goes broke and is forced to quit) is a stopping time. So the theorem says that Template:Math. In other words, the gambler leaves with the same amount of money on average as when he started. (The same result holds if the gambler, instead of having a house limit on individual bets, has a finite limit on his line of credit or how far in debt he may go, though this is easier to show with another version of the theorem.)
• Suppose a random walk starting at Template:Math that goes up or down by one with equal probability on each step. Suppose further that the walk stops if it reaches Template:Math or Template:Math; the time at which this first occurs is a stopping time. If it is known that the expected time at which the walk ends is finite (say, from Markov chain theory), the optional stopping theorem predicts that the expected stop position is equal to the initial position Template:Math. Solving Template:Math for the probability Template:Math that the walk reaches Template:Math before Template:Math gives Template:Math.
• Now consider a random walk Template:Math that starts at Template:Math and stops if it reaches Template:Math or Template:Math, and use the Template:Math martingale from the examples section. If Template:Math is the time at which Template:Math first reaches Template:Math, then Template:Math. This gives Template:Math.
• Care must be taken, however, to ensure that one of the conditions of the theorem hold. For example, suppose the last example had instead used a 'one-sided' stopping time, so that stopping only occurred at Template:Math, not at Template:Math. The value of Template:Math at this stopping time would therefore be Template:Math. Therefore, the expectation value Template:Math must also be Template:Math, seemingly in violation of the theorem which would give Template:Math. The failure of the optional stopping theorem shows that all three of the conditions fail.

Proof

Let Template:Math denote the stopped process, it is also a martingale (or a submartingale or supermartingale, respectively). Under condition (Template:EquationNote) or (Template:EquationNote), the random variable Template:Math is well defined. Under condition (Template:EquationNote) the stopped process Template:Math is bounded, hence by Doob's martingale convergence theorem it converges a.s. pointwise to a random variable which we call Template:Math.

If condition (Template:EquationNote) holds, then the stopped process Template:Math is bounded by the constant random variable Template:Math. Otherwise, writing the stopped process as

$X_t^{\tau }=X_0+\sum _{s=0}^{\tau -1\wedge t-1}(X_{s+1}-X_s),t\in {\mathbb{N}}_0,$

gives Template:Math for all Template:Math, where

$M:=|X_0|+\sum _{s=0}^{\tau -1}|X_{s+1}-X_s|=|X_0|+\sum _{s=0}^{\mathrm{\infty }}|X_{s+1}-X_s|\cdot {\mathrm{𝟏}}_{\{\tau >s\}}$.

By the monotone convergence theorem

$𝔼[M]=𝔼[|X_0|]+\sum _{s=0}^{\mathrm{\infty }}𝔼[|X_{s+1}-X_s|\cdot {\mathrm{𝟏}}_{\{\tau >s\}}]$.

If condition (Template:EquationNote) holds, then this series only has a finite number of non-zero terms, hence Template:Math is integrable.

If condition (Template:EquationNote) holds, then we continue by inserting a conditional expectation and using that the event Template:Math} is known at time Template:Math (note that Template:Math is assumed to be a stopping time with respect to the filtration), hence

$\begin{array}{cc}𝔼[M]& =𝔼[|X_0|]+\sum _{s=0}^{\mathrm{\infty }}𝔼\left[\underset{\le c{\mathrm{𝟏}}_{\{\tau >s\}}\text{ a.s. by (b)}}{\underbrace{𝔼[|X_{s+1}-X_s||{ℱ}_s]\cdot {\mathrm{𝟏}}_{\{\tau >s\}}}}\right]\\ & \le 𝔼[|X_0|]+c\sum _{s=0}^{\mathrm{\infty }}\mathbb{P}(\tau >s)\\ & =𝔼[|X_0|]+c𝔼[\tau ]<\mathrm{\infty },\\ \end{array}$

where a representation of the expected value of non-negative integer-valued random variables is used for the last equality.

Therefore, under any one of the three conditions in the theorem, the stopped process is dominated by an integrable random variable Template:Math. Since the stopped process Template:Math converges almost surely to Template:Math, the dominated convergence theorem implies

$𝔼[X_{\tau }]=\underset{t\to \mathrm{\infty }}{\lim }𝔼[X_t^{\tau }].$

By the martingale property of the stopped process,

$𝔼[X_t^{\tau }]=𝔼[X_0],t\in {\mathbb{N}}_0,$

hence

$𝔼[X_{\tau }]=𝔼[X_0].$

Similarly, if Template:Math is a submartingale or supermartingale, respectively, change the equality in the last two formulas to the appropriate inequality.

References

1. Template:Cite book
2. Template:Cite book

External links

• Doob's Optional Stopping Theorem