Stopping Times

A stopping time is a random time at which we can decide to "stop" observing a stochastic process based only on information available up to that time. Stopping times are fundamental in the optional stopping theorem, optimal stopping problems, and the study of martingales.

Definition

Definition3.1Stopping time

Let $(\mathcal{F}_n)$ be a filtration. A random variable $\tau: \Omega \to \{0, 1, 2, \ldots\} \cup \{\infty\}$ is a stopping time (or optional time) if for each $n \geq 0$ :

$\{\tau = n\} \in \mathcal{F}_n.$

Equivalently, $\{\tau \leq n\} \in \mathcal{F}_n$ for all $n$ .

Intuition: The decision to stop at time $n$ can be made using only information available up to time $n$ . We cannot use "future knowledge" to decide when to stop.

ExampleFirst passage time

Let $(X_n)$ be a stochastic process and $A$ a set. The first passage time (or hitting time) is:

$\tau_A = \inf\{n \geq 0 : X_n \in A\}.$

Then $\{\tau_A = n\}$ occurs iff $X_0, \ldots, X_{n-1} \notin A$ and $X_n \in A$ , which depends only on $X_0, \ldots, X_n$ . So $\tau_A$ is a stopping time.

ExampleLast visit is NOT a stopping time

Let $\tau = \sup\{n : X_n = 0\}$ be the last time the process visits 0. To check whether $\tau = n$ , we need to know that $X_k \neq 0$ for all $k > n$ — this requires knowledge of the future. So $\tau$ is not a stopping time.

Examples

ExampleFixed time

$\tau = n_0$ (a deterministic constant) is a stopping time: $\{\tau = n\} = \begin{cases} \Omega & \text{if } n = n_0, \\ \varnothing & \text{otherwise}, \end{cases}$ which is in $\mathcal{F}_n$ .

ExampleFirst return to the origin

For a random walk $(X_n)$ , the first return time is $\tau = \inf\{n \geq 1 : X_n = 0\}$ . This is a stopping time.

ExampleTime of maximum (before time N)

Let $\tau = \arg\max_{0 \leq k \leq N} X_k$ be the time at which the maximum over $[0, N]$ is achieved. This is not a stopping time (in general), because determining $\tau$ requires comparing $X_n$ to all future values $X_{n+1}, \ldots, X_N$ .

Properties

Theorem3.1Algebra of stopping times

If $\sigma$ and $\tau$ are stopping times, then so are:

$\min(\sigma, \tau)$ .
$\max(\sigma, \tau)$ .
$\sigma + \tau$ (on $\{\sigma < \infty, \tau < \infty\}$ ).
Any fixed time $n$ .

Definition3.2Stopped process

For a process $(X_n)$ and a stopping time $\tau$ , the stopped process is:

$X_n^\tau = X_{\min(n, \tau)}.$

If $(X_n)$ is a martingale and $\tau$ is a stopping time, then $(X_n^\tau)$ is also a martingale.

Optional stopping theorem

Theorem3.2Optional stopping theorem

Let $(M_n)$ be a martingale and $\tau$ a stopping time. If any of the following conditions hold:

$\tau$ is bounded: $\tau \leq N$ a.s. for some constant $N$ .
$\mathbb{E}[\tau] < \infty$ and $\sup_n |M_{n+1} - M_n| < C$ a.s. (bounded increments).
$\mathbb{E}[\tau] < \infty$ and $\mathbb{E}[\sup_n |M_n|] < \infty$ .

Then $\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$ .

The theorem fails without additional conditions, as the doubling strategy example shows.

ExampleSymmetric random walk hitting time

Let $X_n$ be a symmetric random walk starting at 0, and $\tau = \inf\{n : X_n = 1\}$ the first time the walk reaches 1. Then $\mathbb{P}(\tau < \infty) = 1$ by recurrence, but $\mathbb{E}[\tau] = \infty$ .

The optional stopping theorem with $\tau \wedge N = \min(\tau, N)$ gives $\mathbb{E}[X_{\tau \wedge N}] = 0$ . Taking $N \to \infty$ and using dominated convergence (the increments are bounded):

$\mathbb{E}[X_\tau] = \lim_{N \to \infty} \mathbb{E}[X_{\tau \wedge N}] = 0.$

But $X_\tau = 1$ a.s., so this is consistent: $\mathbb{E}[X_\tau] = 1 \cdot \mathbb{P}(\tau < \infty) = 1$ . Wait, this seems wrong! The resolution: the limit does not converge properly without additional conditions. The correct statement requires bounded stopping times or bounded increments.

Wald's identity

Theorem3.3Wald's identity

Let $\xi_1, \xi_2, \ldots$ be i.i.d. with $\mathbb{E}[\xi_i] = \mu$ and $S_n = \sum_{i=1}^n \xi_i$ . If $\tau$ is a stopping time with $\mathbb{E}[\tau] < \infty$ and $\mathbb{E}[|\xi_1|] < \infty$ , then:

$\mathbb{E}[S_\tau] = \mu \mathbb{E}[\tau].$

Wald's identity is a powerful tool for computing expectations of sums over random indices. It follows from the optional stopping theorem applied to the martingale $M_n = S_n - n\mu$ .

ExampleCoupon collector

A collector seeks to collect all $n$ types of coupons. Each coupon type appears independently with probability $1/n$ . Let $\tau$ be the number of coupons collected until all $n$ types are obtained. By Wald's identity (applied to suitable martingales), $\mathbb{E}[\tau] = n H_n \sim n \log n$ , where $H_n = \sum_{k=1}^n 1/k$ is the $n$ -th harmonic number.

Summary

Stopping times formalize the notion of "when to stop" based on observable information:

Definition: $\{\tau = n\} \in \mathcal{F}_n$ (decision depends only on past).
Optional stopping: Under appropriate conditions, $\mathbb{E}[M_\tau] = \mathbb{E}[M_0]$ for martingales.
Wald's identity: $\mathbb{E}[S_\tau] = \mu \mathbb{E}[\tau]$ for i.i.d. sums.
Applications: Optimal stopping, gambling strategies, sequential analysis.

Stopping times are central to the theory of martingales and stochastic optimization.