Optional stopping theorem

Summarize Timeline Top Qs Fact Check

A discrete-time version of the theorem is given below, with ${\displaystyle \mathbb {N} _{0}}$ denoting the set of natural numbers, including zero.

Let ${\displaystyle X=(X_{t})_{t\in \mathbb {N} _{0}}}$ be a discrete-time martingale and ${\displaystyle \tau }$ a stopping time with values in ${\displaystyle \mathbb {N} _{0}\cup \{\infty \}}$, both with respect to a filtration ${\displaystyle ({\mathcal {F}}_{t})_{t\in \mathbb {N} _{0}}}$. Assume that one of the following three conditions holds:

(a) The stopping time ${\displaystyle \tau }$ is almost surely bounded, i.e., there exists a constant ${\displaystyle c\in \mathbb {N} }$ such that ${\displaystyle \tau \leq c}$ almost surely.

(b) The stopping time ${\displaystyle \tau }$ has finite expectation and the conditional expectations of the absolute value of the martingale increments are almost surely bounded. More precisely, ${\displaystyle \mathbb {E} [\tau ]<\infty }$ and there exists a constant ${\displaystyle c}$ such that ${\displaystyle \mathbb {E} {\bigl [}|X_{t+1}-X_{t}|\,{\big \vert }\,{\mathcal {F}}_{t}{\bigr ]}\leq c}$ almost surely on the event ${\displaystyle \{\tau >t\}}$ for all ${\displaystyle t\in \mathbb {N} _{0}}$.

(c) There exists a constant ${\displaystyle c}$ such that ${\displaystyle |X_{\min\{t,\tau \}}|\leq c}$ almost surely for all ${\displaystyle t\in \mathbb {N} _{0}}$.

Then ${\displaystyle X_{\tau }}$ is an almost surely well-defined random variable and ${\displaystyle \mathbb {E} [X_{\tau }]=\mathbb {E} [X_{0}]}$.^[4]

Similarly, if the stochastic process ${\displaystyle X=(X_{t})_{t\in \mathbb {N} _{0}}}$ is a submartingale or a supermartingale and one of the above conditions holds, then: $${\displaystyle \mathbb {E} [X_{\tau }]\geq \mathbb {E} [X_{0}]}$$ for a submartingale, and $${\displaystyle \mathbb {E} [X_{\tau }]\leq \mathbb {E} [X_{0}]}$$ for a supermartingale.

Remark

Under condition (c) it is possible that ${\displaystyle \tau =\infty }$ happens with positive probability. On this event, ${\displaystyle X_{\tau }}$ is defined as the almost surely existing pointwise limit of ${\displaystyle X=(X_{t})_{t\in \mathbb {N} _{0}}}$. See the proof below for details.

Summarize Timeline Top Qs Fact Check

The optional stopping theorem has widespread applications in probability, paradox resolution, and random walk theory:^[5]

• Impossibility of perfect betting strategies: The theorem can be used to prove the impossibility of successful betting strategies for a gambler with a finite lifetime (giving condition (a)) or a house limit on bets (condition (b)).
  • Suppose that the gambler can wager up to ${\displaystyle c}$ dollars on a fair coin flip at times 1, 2, 3, etc., winning their wager if the coin comes up heads and losing it if the coin comes up tails.
  • Suppose further that the gambler can quit whenever they like, but cannot predict the outcome of gambles that have not happened yet.
  • The gambler's fortune over time is a martingale, and the time ${\displaystyle \tau }$ at which they decide to quit (or go broke and are forced to quit) is a stopping time. So the theorem says that ${\displaystyle \mathbb {E} [X_{\tau }]=\mathbb {E} [X_{0}]}$. In other words, the gambler leaves with the same amount of money on average as when they started.
  • The same result holds if the gambler has a finite limit on their line of credit or how far in debt they may go, rather than a house limit on individual bets.
• Expected stop position of a random walk: Suppose a random walk starting at ${\displaystyle a\geq 0}$ goes up or down by one with equal probability on each step.
  • Suppose further that the walk stops if it reaches 0 or ${\displaystyle m\geq a}$; 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 (e.g., from Markov chain theory), the optional stopping theorem predicts that the expected stop position is equal to the initial position ${\displaystyle a}$.
  • Solving ${\displaystyle a=pm+(1-p)0}$ for the probability ${\displaystyle p}$ that the walk reaches ${\displaystyle m}$ before 0 gives ${\displaystyle p=a/m}$.
• Expected time of a random walk: Consider a random walk ${\displaystyle X}$ that starts at 0 and stops if it reaches ${\displaystyle -m}$ or ${\displaystyle +m}$, and use the ${\displaystyle Y_{n}=X_{n}^{2}-n}$ martingale from Martingale (probability theory) § Examples of martingales. If ${\displaystyle \tau }$ is the time at which ${\displaystyle X}$ first reaches ${\displaystyle \pm m}$, then ${\displaystyle 0=\mathbb {E} [Y_{0}]=\mathbb {E} [Y_{\tau }]=m^{2}-\mathbb {E} [\tau ]}$. This directly gives ${\displaystyle \mathbb {E} [\tau ]=m^{2}}$.
• Violations of the theorem (Counterexamples): Care must be taken to ensure that one of the conditions of the theorem holds.
  • For example, suppose the last example had instead used a 'one-sided' stopping time, so that stopping only occurred at ${\displaystyle +m}$, not at ${\displaystyle -m}$.
  • The value of ${\displaystyle X}$ at this stopping time would therefore be ${\displaystyle m}$, meaning the expectation value ${\displaystyle \mathbb {E} [X_{\tau }]}$ must also be ${\displaystyle m}$.
  • This seemingly violates the theorem which would give ${\displaystyle \mathbb {E} [X_{\tau }]=X_{0}=0}$. The failure of the optional stopping theorem in this case shows that all three of the conditions fail for a one-sided stopping time with an unrestricted state space.

Summarize Timeline Top Qs Fact Check

Let ${\displaystyle X^{\tau }}$ denote the stopped process, which is also a martingale (or a submartingale or supermartingale, respectively). The framework of the proof relies on analyzing this process under the provided conditions:

• Under condition (a) or (b), the random variable ${\displaystyle X^{\tau }}$ is well defined.
• Under condition (c) the stopped process ${\displaystyle X^{\tau }}$ is bounded, hence by Doob's martingale convergence theorem it converges almost surely pointwise to a random variable which we call ${\displaystyle X_{\tau }}$.

If condition (c) holds, then the stopped process ${\displaystyle X^{\tau }}$ is bounded by the constant random variable ${\displaystyle M:=c}$. Otherwise, writing the stopped process as $${\displaystyle X_{t}^{\tau }=X_{0}+\sum _{s=0}^{\tau -1\land t-1}(X_{s+1}-X_{s}),\quad t\in \mathbb {N} _{0}}$$ gives ${\displaystyle X_{t}^{\tau }\leq M}$ for all ${\displaystyle t\in \mathbb {N} _{0}}$, where $${\displaystyle M:=|X_{0}|+\sum _{s=0}^{\tau -1}|X_{s+1}-X_{s}|=|X_{0}|+\sum _{s=0}^{\infty }|X_{s+1}-X_{s}|\cdot \mathbf {1} _{\{\tau >s\}}.}$$

By the monotone convergence theorem, $${\displaystyle \mathbb {E} [M]=\mathbb {E} [|X_{0}|]+\sum _{s=0}^{\infty }\mathbb {E} {\bigl [}|X_{s+1}-X_{s}|\cdot \mathbf {1} _{\{\tau >s\}}{\bigr ]}.}$$

If condition (a) holds, then this series only has a finite number of non-zero terms, hence ${\displaystyle M}$ is integrable.

If condition (b) holds, then we continue by inserting a conditional expectation and using that the event ${\displaystyle \{\tau >s\}}$ is known at time ${\displaystyle s}$ (note that ${\displaystyle \tau }$ is assumed to be a stopping time with respect to the filtration). This yields: $${\displaystyle {\begin{aligned}\mathbb {E} [M]&=\mathbb {E} [|X_{0}|]+\sum _{s=0}^{\infty }\mathbb {E} {\bigl [}\underbrace {\mathbb {E} {\bigl [}|X_{s+1}-X_{s}|{\big |}{\mathcal {F}}_{s}{\bigr ]}\cdot \mathbf {1} _{\{\tau >s\}}} _{\leq \,c\,\mathbf {1} _{\{\tau >s\}}{\text{ a.s. by (b)}}}{\bigr ]}\\&\leq \mathbb {E} [|X_{0}|]+c\sum _{s=0}^{\infty }\mathbb {P} (\tau >s)\\&=\mathbb {E} [|X_{0}|]+c\,\mathbb {E} [\tau ]<\infty ,\\\end{aligned}}}$$ 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 ${\displaystyle M}$. Since the stopped process ${\displaystyle X^{\tau }}$ converges almost surely to ${\displaystyle X_{\tau }}$, the dominated convergence theorem implies: $${\displaystyle \mathbb {E} [X_{\tau }]=\lim _{t\to \infty }\mathbb {E} [X_{t}^{\tau }].}$$

By the martingale property of the stopped process, $${\displaystyle \mathbb {E} [X_{t}^{\tau }]=\mathbb {E} [X_{0}],\quad t\in \mathbb {N} _{0},}$$ hence $${\displaystyle \mathbb {E} [X_{\tau }]=\mathbb {E} [X_{0}].}$$

Similarly, if ${\displaystyle X}$ is a submartingale or supermartingale, respectively, change the equality in the last two formulas to the appropriate inequality.