Optional stopping theorem

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.

The concept can be understood through the following key principles:

Statement

A discrete-time version of the theorem is given below, with ℕ0 denoting the set of natural numbers, including zero.

Let X=(Xt)t∈ℕ0 be a discrete-time martingale and τ a stopping time with values in ℕ0∪{∞}, both with respect to a filtration (ℱt)t∈ℕ0. Assume that one of the following three conditions holds:

(a) The stopping time τ is almost surely bounded, i.e., there exists a constant c∈ℕ such that τ≤c almost surely.
(b) The stopping time τ has finite expectation and the conditional expectations of the absolute value of the martingale increments are almost surely bounded. More precisely, 𝔼[τ]<∞ and there exists a constant c such that 𝔼[|Xt+1−Xt||ℱt]≤c almost surely on the event {τ>t} for all t∈ℕ0.
(c) There exists a constant c such that |Xmin⁡{t,τ}|≤c almost surely for all t∈ℕ0.

Then Xτ is an almost surely well-defined random variable and 𝔼[Xτ]=𝔼[X0].

Similarly, if the stochastic process X=(Xt)t∈ℕ0 is a submartingale or a supermartingale and one of the above conditions holds, then: 𝔼[Xτ]≥𝔼[X0] for a submartingale, and 𝔼[Xτ]≤𝔼[X0] for a supermartingale.

Remark

Under condition (c) it is possible that τ=∞ happens with positive probability. On this event, Xτ is defined as the almost surely existing pointwise limit of X=(Xt)t∈ℕ0. See the proof below for details.

Applications

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

Proof

Let Xτ 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:

If condition (c) holds, then the stopped process Xτ is bounded by the constant random variable M:=c. Otherwise, writing the stopped process as Xtτ=X0+∑s=0τ−1∧t−1(Xs+1−Xs),t∈ℕ0 gives Xtτ≤M for all t∈ℕ0, where M:=|X0|+∑s=0τ−1|Xs+1−Xs|=|X0|+∑s=0∞|Xs+1−Xs|⋅𝟏{τ>s}.

By the monotone convergence theorem, 𝔼[M]=𝔼[|X0|]+∑s=0∞𝔼[|Xs+1−Xs|⋅𝟏{τ>s}].

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

If condition (b) holds, then we continue by inserting a conditional expectation and using that the event {τ>s} is known at time s (note that τ is assumed to be a stopping time with respect to the filtration). This yields: 𝔼[M]=𝔼[|X0|]+∑s=0∞𝔼[𝔼[|Xs+1−Xs||ℱs]⋅𝟏{τ>s}⏟≤c𝟏{τ>s} a.s. by (b)]≤𝔼[|X0|]+c∑s=0∞ℙ(τ>s)=𝔼[|X0|]+c𝔼[τ]<∞, 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 M. Since the stopped process Xτ converges almost surely to Xτ, the dominated convergence theorem implies: 𝔼[Xτ]=limt→∞𝔼[Xtτ].

By the martingale property of the stopped process, 𝔼[Xtτ]=𝔼[X0],t∈ℕ0, hence 𝔼[Xτ]=𝔼[X0].

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