Stopping Times and Integrability in Wald Problems

Stopping Rules and Stopped Sums

In a sequential experiment, observations arrive one at a time, and the decision to stop may depend on the observations already seen. Wald’s identities relate the expected value of a sum stopped in this way to the expected number of terms. Before applying such an identity, it matters both when stopping occurs and whether the resulting sum is integrable. In particular, stopping eventually with probability one is weaker than having a finite expected stopping time.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_k)_{k\ge1}$ be an iid sequence of real-valued random variables, and define its natural filtration by $\mathcal{F}_0=\{\varnothing,\Omega\}$ and $\mathcal{F}_n=\sigma(X_1,\ldots,X_n)$ for $n\ge1$. Write $S_0=0$ and $S_n=\sum_{k=1}^n X_k$. A random time $\tau$ taking values in $\{0,1,2,\ldots\}\cup\{\infty\}$ is a stopping time for this filtration if $\{\tau\le n\}\in\mathcal{F}_n$ for every $n\ge0$. Thus, by time $n$, the observations so far determine whether stopping has already occurred.

Definition: The stopped sum is $S_\tau=\sum_{k=1}^{\tau}X_k$ on the event $\{\tau<\infty\}$, with an empty sum equal to $0$ when $\tau=0$. If $\tau<\infty$ almost surely, this defines a finite sum almost surely. The stopped sum is integrable only if $\mathbb{E}|S_\tau|<\infty$; almost-sure finiteness of the sum does not by itself ensure this.

The identity $\mathbb{E}S_\tau=\mathbb{E}\tau\,\mathbb{E}X_1$, known as Wald’s first identity, applies when the increments are iid and integrable, and $\tau$ is a stopping time with $\mathbb{E}\tau<\infty$. Its derivation from indicator sums is the subject of the next step in the course. Here we establish why the hypotheses are useful: finite expected duration makes the stopped sum absolutely integrable, and allows deterministic truncations to approximate it in mean.

Theorem: Suppose $(X_k)$ is iid with $\mathbb{E}|X_1|<\infty$, and $\tau$ is a stopping time for its natural filtration with $\mathbb{E}\tau<\infty$. Then $\tau<\infty$ almost surely and $$ \mathbb{E}\left[\sum_{k=1}^{\tau}|X_k|\right] =\mathbb{E}|X_1|\,\mathbb{E}\tau<\infty. $$ Consequently, $S_\tau$ is integrable. Also $S_{\tau\wedge n}\to S_\tau$ in $L^1$ as $n\to\infty$.

Proof. For each $k\ge1$, the event $\{\tau\ge k\}=\{\tau>k-1\}$ belongs to $\mathcal{F}_{k-1}$, since its complement is $\{\tau\le k-1\}$. The variable $X_k$ is independent of $\mathcal{F}_{k-1}$, so $\mathbb{E}[|X_k|\mathbf{1}_{\{\tau\ge k\}}]=\mathbb{E}|X_1|\,\mathbb{P}(\tau\ge k)$. For a nonnegative integer-valued random variable, including one that may equal infinity, $\tau=\sum_{k\ge1}\mathbf{1}_{\{\tau\ge k\}}$; taking expectations by monotone convergence gives $\mathbb{E}\tau=\sum_{k\ge1}\mathbb{P}(\tau\ge k)$. Also, $\mathbb{E}\tau<\infty$ implies $\mathbb{P}(\tau=\infty)=0$, because positive probability of $\tau=\infty$ would make $\mathbb{E}\tau=\infty$. Applying Tonelli’s theorem to the nonnegative terms, $\mathbb{E}\sum_{k=1}^{\tau}|X_k|=\sum_{k\ge1}\mathbb{E}[|X_k|\mathbf{1}_{\{\tau\ge k\}}]=\mathbb{E}|X_1|\mathbb{E}\tau<\infty$. Since $|S_\tau|\le\sum_{k=1}^{\tau}|X_k|$, the stopped sum is integrable. Finally, \[ \mathbb{E}|S_\tau-S_{\tau\wedge n}| \le \mathbb{E}\sum_{k=n+1}^{\tau}|X_k| =\mathbb{E}|X_1|\sum_{k>n}\mathbb{P}(\tau\ge k)\longrightarrow 0. \] The last limit holds because the full tail-probability series has finite sum $\mathbb{E}\tau$. This is $L^1$ convergence. $\square$

The proof uses the stopping-time condition in a particular way: the decision to include $X_k$ in the sum, expressed by $\{\tau\ge k\}$, is determined before $X_k$ is observed. That event is therefore independent of $X_k$. An arbitrary random time need not have this property. The proof also makes a useful distinction: the finite-mean assumption guarantees absolute integrability of the whole stopped sum, not merely that the number of terms is finite on almost every outcome.

Worked Example: A Deterministic Stopping Horizon

Let $X_1,X_2,\ldots$ be iid Bernoulli random variables with $\mathbb{P}(X_k=1)=\tfrac13$ and $\mathbb{P}(X_k=0)=\tfrac23$. Stop at the deterministic time $\tau=3$. Check the integrability conditions and compute the expected absolute sum.

A deterministic time is a stopping time: for each $n$, $\{\tau\le n\}$ is either $\varnothing$ or $\Omega$, both in $\mathcal{F}_n$. Here $\mathbb{E}\tau=3$, and $\mathbb{E}|X_1|=1\cdot\tfrac13+0\cdot\tfrac23=\tfrac13$. Since each increment is nonnegative, $\sum_{k=1}^{\tau}|X_k|=S_3$. Directly, linearity of expectation gives $\mathbb{E}S_3=\mathbb{E}X_1+\mathbb{E}X_2+\mathbb{E}X_3=\tfrac13+\tfrac13+\tfrac13=1$. The theorem gives the same value: $\mathbb{E}|X_1|\,\mathbb{E}\tau=\tfrac13\cdot3=1$.

Check: The sum has three terms, each equal to $1$ with probability $\tfrac13$, so the expected number of ones is $3\cdot\tfrac13=1$. The direct calculation agrees with the theorem, and $S_3$ is integrable because it lies between $0$ and $3$.

Almost-Sure Finiteness Is Not Finite Mean

For a nonnegative integer-valued stopping time, the tail-sum formula is $\mathbb{E}\tau=\sum_{n\ge0}\mathbb{P}(\tau>n)$. It follows by writing $\tau=\sum_{n\ge0}\mathbf{1}_{\{\tau>n\}}$ and applying monotone convergence. Almost-sure finiteness says only that $\mathbb{P}(\tau>n)\to0$; it does not say that this series converges. The rate at which the tail probabilities decrease matters.

Worked Example: A Stopping Time That Is Finite Almost Surely but Has Infinite Mean

Let $X_k$ be iid uniform random variables on $(0,1)$, and use the natural filtration $\mathcal{F}_n=\sigma(X_1,\ldots,X_n)$. Define $\tau=\inf\{k\ge1:X_k\le\tfrac{1}{k+1}\}$. Find whether $\tau$ is a stopping time, whether it is finite almost surely, and whether it has finite mean.

For each $n\ge1$, the event $\{\tau\le n\}$ is the union, over $1\le k\le n$, of the events that $X_k\le\tfrac1{k+1}$ and no earlier threshold was met. Each such event is determined by $X_1,\ldots,X_n$, so $\tau$ is a stopping time. Independence and the uniform distribution give, for $n\ge1$, \[ \mathbb{P}(\tau>n) =\prod_{k=1}^n\mathbb{P}\left(X_k>\tfrac1{k+1}\right) =\prod_{k=1}^n\tfrac{k}{k+1} =\tfrac1{n+1}. \] For $n=0$, $\mathbb{P}(\tau>0)=1=\tfrac1{0+1}$. Since $\mathbb{P}(\tau=\infty)=\lim_{n\to\infty}\mathbb{P}(\tau>n)=\lim_{n\to\infty}\tfrac1{n+1}=0$, the stopping time is finite almost surely. But $\mathbb{E}\tau=\sum_{n\ge0}\mathbb{P}(\tau>n)=\sum_{n\ge0}\tfrac1{n+1}=\infty$, since the harmonic series diverges.

In this example $S_\tau$ is a finite sum almost surely, because $\tau<\infty$ almost surely and each $X_k$ lies in $(0,1)$. Nevertheless, its expectation is infinite. Indeed, using nonnegative terms and independence of $X_k$ from $\{\tau\ge k\}$, \[ \mathbb{E}S_\tau =\sum_{k\ge1}\mathbb{E}[X_k\mathbf{1}_{\{\tau\ge k\}}] =\sum_{k\ge1}\mathbb{E}X_k\,\mathbb{P}(\tau\ge k) =\sum_{k\ge1}\tfrac12\cdot\tfrac1k =\infty. \] Here $\mathbb{P}(\tau\ge k)=\mathbb{P}(\tau>k-1)=1/k$, and $\mathbb{E}X_k=\int_0^1x\,dx=\tfrac12$. This verifies directly that an almost-surely finite stopped sum need not be integrable.

Check: The probability of surviving the first $n$ tests is $\tfrac1{n+1}$, which tends to zero, but the sum of those tail probabilities diverges. Thus the probability of an infinite wait is zero while the expected waiting time is infinite.

The Increment Moment Condition Is Separate

Finite expected stopping time cannot compensate for increments that lack a first absolute moment. This is a separate requirement in the usual first Wald identity. Conversely, when the increments are integrable, finite $\mathbb{E}\tau$ is a convenient sufficient condition ensuring that the stopped sum is absolutely integrable. It is a sufficient condition, not a claim that every integrable stopped sum must have finite $\mathbb{E}\tau$.

Worked Example: Finite Stopping Time but Nonintegrable Increment

Let $X_1,X_2,\ldots$ be iid standard Cauchy random variables, with density $f(x)=1/(\pi(1+x^2))$, and take the deterministic stopping time $\tau=1$. Check the stopping-time and moment conditions.

The time $\tau=1$ is a stopping time and $\mathbb{E}\tau=1$. However, \[ \mathbb{E}|X_1| =\frac{2}{\pi}\int_0^\infty\frac{x}{1+x^2}\,dx =\infty, \] because $\int_0^R x/(1+x^2)\,dx=\tfrac12\log(1+R^2)$, which tends to infinity as $R\to\infty$. Since $S_\tau=X_1$, the stopped sum is not integrable. In particular, the finite-mean stopping-time condition alone does not ensure that $\mathbb{E}S_\tau$ is a finite expectation.

Check: Here $\mathbb{P}(\tau<\infty)=1$ and $\mathbb{E}\tau=1$, but $\mathbb{E}|S_\tau|=\mathbb{E}|X_1|=\infty$. The failure is in the increment moment condition, not in the stopping rule.

A Common Mistake: Treating the Stopping Event as Independent

Although $X_k$ is independent of the past, it is generally not independent of the event $\{\tau=k\}$: stopping at time $k$ can depend on the $k$th observation. The event relevant to deciding whether to include $X_k$ is $\{\tau\ge k\}$, which is determined by the first $k-1$ observations for a stopping time. Confusing these two events leads to incorrect factorization.

Worked Example: The First Success and a False Factorization

Let $X_k$ be iid Bernoulli random variables with success probability $p=\tfrac12$, and let $\tau=\inf\{k\ge1:X_k=1\}$. Calculate one term involving $\{\tau=2\}$ correctly, and compare it with the invalid independence calculation.

The event $\{\tau=2\}$ means $X_1=0$ and $X_2=1$, so $\mathbb{P}(\tau=2)=\tfrac12\cdot\tfrac12=\tfrac14$. Also, $X_2\mathbf{1}_{\{\tau=2\}}=1$ exactly on this event and is zero otherwise. Hence $\mathbb{E}[X_2\mathbf{1}_{\{\tau=2\}}]=\tfrac14$. A mistaken calculation would treat $X_2$ and $\{\tau=2\}$ as independent and write $\mathbb{E}X_2\,\mathbb{P}(\tau=2)=\tfrac12\cdot\tfrac14=\tfrac18$, which is wrong.

The correct factorization for a stopped sum uses $\{\tau\ge2\}$, not $\{\tau=2\}$. Here $\{\tau\ge2\}=\{X_1=0\}$, so it is independent of $X_2$, and $\mathbb{E}[X_2\mathbf{1}_{\{\tau\ge2\}}]=\tfrac12\cdot\tfrac12=\tfrac14$. Check: The direct value $\tfrac14$ agrees with this factorization; the erroneous value $\tfrac18$ does not.

There is a related distinction between a stopping time and a random time that looks ahead. For example, if $\tau=1$ when $X_2>0$ and $\tau=2$ otherwise, then $\{\tau\le1\}=\{X_2>0\}$, which need not belong to $\mathcal{F}_1$. The decision at time $1$ uses future information, so this is not a stopping time for the stated filtration. A finite random time is not automatically a stopping time.

For a Wald problem, first identify the filtration and verify the stopping-time condition. Then check $\mathbb{E}|X_1|<\infty$ and $\mathbb{E}\tau<\infty$ separately. Under these assumptions, the theorem above guarantees that $S_\tau$ is integrable and that finite-horizon stopped sums converge to it in $L^1$. These facts establish the basic integrability framework; the next step derives the expectation identity itself.

Check Your Understanding

For each question, distinguish carefully between almost-sure finiteness, finite expected duration, and integrability of the stopped sum.

Why is $\{\tau\ge k\}$ measurable with respect to $\mathcal{F}_{k-1}$ when $\tau$ is a stopping time?
If $\mathbb{P}(\tau>n)=1/(n+1)$ for $n\ge0$, is $\tau$ finite almost surely? Does it have finite mean?
Give the two separate integrability assumptions in the theorem that controls $\mathbb{E}\sum_{k=1}^{\tau}|X_k|$.
For the first-success stopping rule with success probability $p$, why is $\{\tau=k\}$ not independent of $X_k$, while $\{\tau\ge k\}$ is independent of $X_k$?
If $\tau$ is finite almost surely and $\mathbb{E}|X_1|=\infty$, what can be concluded from those facts alone about $\mathbb{E}|S_\tau|$?