Mathematics.

discrete time processes

Stopping Times

Stochastic Processes55 minDifficulty7 out of 10

You should know: martingales, markov chains

Overview

A stopping time is a random variable T taking values in {0, 1, 2, ...} U {infinity} such that the event {T <= n} depends only on information available up to time n. Stopping times formalize the idea of a decision rule that acts on currently observed data without 'looking into the future'. They are essential in the optional stopping theorem, sequential analysis, and optimal stopping theory.

Intuition

Think of a stopping time as a strategy for when to 'stop the clock' based only on what you have seen so far. A gambler who quits when they first reach $100 is using a stopping time: the decision at each moment depends only on the current and past wealth. Crucially, you cannot look ahead -- you cannot stop 'just before a loss'. This no-peeking condition is precisely the measurability requirement {T <= n} in F_n.

Formal Definition

Definition

Let (Omega, F, P) be a probability space with filtration {F_n}. A random variable T: Omega -> {0, 1, 2, ...} U {infinity} is a stopping time with respect to {F_n} if for every n >= 0 the event {T <= n} belongs to F_n.

{T≤n}∈Fnfor all n≥0\{T \le n\} \in \mathcal{F}_n \quad \text{for all } n \ge 0
Stopping time condition
FT={A∈F:A∩{T≤n}∈Fn for all n}\mathcal{F}_T = \{A \in \mathcal{F} : A \cap \{T \le n\} \in \mathcal{F}_n \text{ for all } n\}
Sigma-algebra at stopping time
E[MT]=E[M0](Optional Stopping, under integrability conditions)\mathbb{E}[M_T] = \mathbb{E}[M_0] \quad \text{(Optional Stopping, under integrability conditions)}
Optional stopping theorem

Notation

NotationMeaning
TTStopping time: a random variable with {T <= n} in F_n
FT\mathcal{F}_TSigma-algebra of events determined at the stopping time T
MTM_TMartingale evaluated at the stopping time T

Theorems

Theorem 1: Theorem 1 (Optional Stopping Theorem)
Let {Mn} be a martingale and T a stopping time. If any one of the following holds: (a) T≤N a.s. for some constant N, (b) E[T]<∞ and ∣Mn+1−Mn∣≤C a.s., or (c) {Mn∧T} is uniformly integrable, then E[MT]=E[M0].\text{Let } \{M_n\} \text{ be a martingale and } T \text{ a stopping time. If any one of the following holds: (a) } T \le N \text{ a.s. for some constant } N, \text{ (b) } \mathbb{E}[T] < \infty \text{ and } |M_{n+1} - M_n| \le C \text{ a.s., or (c) } \{M_{n \wedge T}\} \text{ is uniformly integrable, then } \mathbb{E}[M_T] = \mathbb{E}[M_0].
Theorem 2: Theorem 2 (Minimum of Stopping Times)
If S and T are stopping times, then S∧T,  S∨T, and S+T are also stopping times.\text{If } S \text{ and } T \text{ are stopping times, then } S \wedge T,\; S \vee T, \text{ and } S + T \text{ are also stopping times.}

Worked Examples

  1. 1

    We need {T <= n} in F_n for all n. The event {T <= n} = {S_1 = 1 or S_2 = 1 or ... or S_n = 1} (more precisely, the first time S hits 1 is at most n).

    {T≤n}={max⁡1≤k≤nSk≥1}∈Fn\{T \le n\} = \{\max_{1 \le k \le n} S_k \ge 1\} \in \mathcal{F}_n
  2. 2

    Since S_1, ..., S_n are F_n-measurable, any event defined by their values is in F_n.

    {T≤n}∈Fnfor all n≥0\{T \le n\} \in \mathcal{F}_n \quad \text{for all } n \ge 0

✓ Answer

T is a stopping time because {T <= n} is determined entirely by (S_1, ..., S_n), which are F_n-measurable.

Practice Problems

Mediumfree response

Let X_1, X_2, ... be i.i.d. real random variables and define T = min{n >= 1 : X_n > 5}. Is T a stopping time with respect to the natural filtration F_n = sigma(X_1, ..., X_n)?

Mediumfree response

A gambler starts with $5 and bets $1 per round at fair odds. Let T = min{n : S_n = 0 or S_n = 10}. Use the optional stopping theorem to find E[T].

Common Mistakes

Common Mistake

Thinking any random time is a stopping time

The key constraint is that {T <= n} must lie in F_n -- the decision to stop cannot use future information. 'Stop at the last time before the maximum' is NOT a stopping time.

Common Mistake

Applying optional stopping without checking integrability

E[M_T] = E[M_0] requires conditions: bounded T, or bounded increments with finite E[T], or uniform integrability. Violating these can give wrong answers.

Quiz

Which condition defines a stopping time T with respect to a filtration {F_n}?
For the optional stopping theorem E[M_T] = E[M_0] to hold, which condition is sufficient?
If S and T are stopping times, which of the following is NOT necessarily a stopping time?

Summary

  • A stopping time T satisfies {T <= n} in F_n for all n: the stopping decision uses only current and past information.
  • The sigma-algebra F_T captures all information known at the stopping time.
  • Optional Stopping Theorem: E[M_T] = E[M_0] for a martingale M under suitable integrability conditions.
  • Classic applications: gambler's ruin (E[T] = ab for hitting times of +a or -b), sequential testing, and optimal stopping.

References

  1. BookDurrett, R. -- Probability: Theory and Examples, 4th ed., Chapter 4
  2. BookWilliams, D. -- Probability with Martingales, Chapter 10
  3. WebsiteWikipedia -- Stopping time