From a Stopped Sum to Indicator Sums
Suppose a process accumulates random increments, but observation stops at a random time. The final total is not generally a fixed number of increments, and the stopping rule may depend on what has already been observed. Wald’s first identity says that, under suitable conditions, the expected total is still simple: it is the expected number of increments multiplied by the mean of one increment. The key is to count each increment only when the process has not stopped before that increment is taken.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_k)_{k\ge1}\) be independent and identically distributed integrable random variables, with \(\mu=\mathbb{E}[X_1]\). Let \(\mathcal{F}_0=\{\varnothing,\Omega\}\) and \(\mathcal{F}_n=\sigma(X_1,\ldots,X_n)\) for \(n\ge1\). 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\). Assume \(\mathbb{E}[\tau]<\infty\). In particular, \(\tau<\infty\) almost surely. The stopped sum is \(S_\tau=\sum_{k=1}^{\tau}X_k\), with an empty sum defined to be zero when \(\tau=0\).
The filtration matters. The event that the \(k\)th increment is included is \(\{\tau\ge k\}\), meaning the process has not stopped by time \(k-1\). Because \(\tau\) is a stopping time, this event is known from \(\mathcal{F}_{k-1}\). It is therefore independent of \(X_k\), which is independent of the increments observed up to time \(k-1\). By contrast, whether the process stops exactly at time \(k\) may depend on \(X_k\), so that event need not be independent of the \(k\)th increment.
Proof by Survival Indicators
For every outcome with finite \(\tau\), the sum can be written as $$ S_\tau=\sum_{k=1}^{\infty}X_k\mathbf{1}_{\{\tau\ge k\}}. $$ To use this identity under expectation, first establish that the series is absolutely integrable. This also justifies the subsequent exchange of expectation and summation.
Proof. For each \(k\ge1\), \(\{\tau\ge k\}=\{\tau\not\le k-1\}\in\mathcal{F}_{k-1}\). Since \(X_k\) is independent of \(\mathcal{F}_{k-1}\), and \(\mathbb{E}|X_k|=\mathbb{E}|X_1|<\infty\), we have $$ \mathbb{E}\!\left[|X_k|\mathbf{1}_{\{\tau\ge k\}}\right] =\mathbb{E}|X_1|\,\mathbb{P}(\tau\ge k). $$ The pointwise identity \(\tau=\sum_{k=1}^{\infty}\mathbf{1}_{\{\tau\ge k\}}\) for nonnegative integer-valued \(\tau\), together with Tonelli’s theorem for nonnegative terms, gives \(\mathbb{E}[\tau]=\sum_{k=1}^{\infty}\mathbb{P}(\tau\ge k)\). Thus $$ \mathbb{E}\!\left[\sum_{k=1}^{\infty}|X_k|\mathbf{1}_{\{\tau\ge k\}}\right] =\mathbb{E}|X_1|\sum_{k=1}^{\infty}\mathbb{P}(\tau\ge k) =\mathbb{E}|X_1|\,\mathbb{E}[\tau]<\infty. $$ So the indicator series is absolutely integrable, and its expectation is the sum of the expectations of its terms. Independence also gives \(\mathbb{E}[X_k\mathbf{1}_{\{\tau\ge k\}}]=\mu\,\mathbb{P}(\tau\ge k)\). Therefore $$ \mathbb{E}[S_\tau] =\sum_{k=1}^{\infty}\mathbb{E}[X_k\mathbf{1}_{\{\tau\ge k\}}] =\mu\sum_{k=1}^{\infty}\mathbb{P}(\tau\ge k) =\mu\,\mathbb{E}[\tau]. $$ The absolute-integrability bound proves that \(S_\tau\) is integrable as well. \(\square\)
A finite-horizon version follows by the same indicator argument. It is useful when approximating an unbounded stopping time by a bounded one.
Proof. The sum on the left equals \(\sum_{k=1}^{n}X_k\mathbf{1}_{\{\tau\ge k\}}\), since the \(k\)th term is included exactly when \(\tau\wedge n\ge k\), for \(1\le k\le n\). Each event \(\{\tau\ge k\}\) belongs to \(\mathcal{F}_{k-1}\), so independence gives \(\mathbb{E}[X_k\mathbf{1}_{\{\tau\ge k\}}]=\mu\mathbb{P}(\tau\ge k)\). Summing these \(n\) equalities yields \(\mu\sum_{k=1}^{n}\mathbb{P}(\tau\ge k)\). The pointwise identity \(\tau\wedge n=\sum_{k=1}^{n}\mathbf{1}_{\{\tau\ge k\}}\) shows that this is \(\mu\mathbb{E}[\tau\wedge n]\), proving the proposition. \(\square\)
Worked Applications
Worked Example: Stop at the First Positive Increment
Let the increments be independent, with \(\mathbb{P}(X_k=1)=\mathbb{P}(X_k=-1)=\tfrac12\). Define \(\tau=\inf\{k\ge1:X_k=1\}\). Find the expected stopping time and the expected stopped sum.
This is a stopping time because the event \(\{\tau\le n\}\) is determined by \(X_1,\ldots,X_n\). For \(k\ge1\), the event \(\{\tau\ge k\}\) means that the first \(k-1\) increments are all \(-1\), so \(\mathbb{P}(\tau\ge k)=(\tfrac12)^{k-1}\). Consequently, $$ \mathbb{E}[\tau]=\sum_{k=1}^{\infty}\mathbb{P}(\tau\ge k) =\sum_{k=1}^{\infty}\left(\tfrac12\right)^{k-1}=2. $$ The geometric series converges, so the theorem applies. Since \(\mu=\tfrac12(1)+\tfrac12(-1)=0\), Wald’s identity gives \(\mathbb{E}[S_\tau]=0\).
Check by computing the stopped sum directly. If \(\tau\) is finite, the first \(\tau-1\) increments are \(-1\), and the last is \(1\). Thus \(S_\tau=-(\tau-1)+1=2-\tau\). Therefore \(\mathbb{E}[S_\tau]=2-\mathbb{E}[\tau]=2-2=0\), in agreement with the identity.
Worked Example: A Stopping Decision Based on the First Increment
Let the increments be independent with \(\mathbb{P}(X_k=1)=\mathbb{P}(X_k=3)=\tfrac12\). Stop at time \(\tau=1\) if \(X_1=1\), and at time \(\tau=2\) if \(X_1=3\). Compute the expected stopped sum.
The stopping decision at time \(1\) uses only \(X_1\), so this is a stopping time. The increment mean is \(\mu=\tfrac12(1)+\tfrac12(3)=2\), and $$ \mathbb{E}[\tau]=\tfrac12(1)+\tfrac12(2)=\tfrac32. $$ Wald’s identity predicts \(\mathbb{E}[S_\tau]=2\cdot\tfrac32=3\).
To check directly, when \(X_1=1\), the stopped sum is \(1\). When \(X_1=3\), it is \(3+X_2\); independence gives \(\mathbb{E}[X_2]=2\). Hence $$ \mathbb{E}[S_\tau] =\tfrac12(1)+\tfrac12(3+2) =\tfrac12+\tfrac52=3. $$ The indicator calculation gives the same result: \(\{\tau\ge1\}=\Omega\), while \(\{\tau\ge2\}=\{X_1=3\}\), which is independent of \(X_2\). The two expected contributions are \(\mathbb{E}[X_1]=2\) and \(\mathbb{E}[X_2\mathbf{1}_{\{\tau\ge2\}}]=2\cdot\tfrac12=1\), totaling \(3\).
Check: The expected number of included increments is \(\tfrac32\), each has mean \(2\) when included under the survival-event calculation, and their total expected contribution is \(2+1=3\).
Worked Example: Negative and Positive Increments
Suppose the independent increments satisfy \(\mathbb{P}(X_k=-1)=\mathbb{P}(X_k=2)=\tfrac12\). Stop at time \(1\) if \(X_1=-1\), and at time \(2\) if \(X_1=2\). Find the expected stopped sum using survival indicators, then check it directly.
The mean increment is \(\mu=\tfrac12(-1)+\tfrac12(2)=\tfrac12\), and the stopping rule is determined by the first observed increment. The expected stopping time is $$ \mathbb{E}[\tau]=\tfrac12(1)+\tfrac12(2)=\tfrac32, $$ so Wald’s identity predicts \(\mathbb{E}[S_\tau]=\tfrac12\cdot\tfrac32=\tfrac34\).
For the indicator sum, \(\{\tau\ge1\}=\Omega\), so the first term has expectation \(\mathbb{E}[X_1]=\tfrac12\). The event \(\{\tau\ge2\}=\{X_1=2\}\) has probability \(\tfrac12\) and is independent of \(X_2\). Thus the second term has expectation \(\mathbb{E}[X_2\mathbf{1}_{\{\tau\ge2\}}]=\tfrac12\cdot\tfrac12=\tfrac14\). Adding gives \(\tfrac12+\tfrac14=\tfrac34\).
Check directly: With probability \(\tfrac12\), the stopped sum is \(-1\). With probability \(\tfrac12\), it is \(2+X_2\), whose conditional mean is \(2+\tfrac12=\tfrac52\). Therefore \(\mathbb{E}[S_\tau]=\tfrac12(-1)+\tfrac12(\tfrac52)=-\tfrac12+\tfrac54=\tfrac34\), as predicted.
The Crucial Event and a Common Error
The factorization in the proof applies to the event that the process survives long enough to include the next increment: \(\{\tau\ge k\}\in\mathcal{F}_{k-1}\). It does not generally apply to \(\{\tau=k\}\), which can depend on \(X_k\). Confusing these events can produce a false calculation even when the stopping rule itself is valid.
Common mistake. In the second example, \(\{\tau=1\}=\{X_1=1\}\). A mistaken factorization would give \(\mathbb{E}[X_1\mathbf{1}_{\{\tau=1\}}]=\mathbb{E}[X_1]\mathbb{P}(\tau=1)=2\cdot\tfrac12=1\). But direct computation gives \(\mathbb{E}[X_1\mathbf{1}_{\{\tau=1\}}]=1\cdot\tfrac12+3\cdot0=\tfrac12\), not \(1\). The error is treating an event determined by \(X_1\) as independent of \(X_1\). The correct first indicator is \(\{\tau\ge1\}=\Omega\), so its expected contribution is \(2\); the second is \(\{\tau\ge2\}=\{X_1=3\}\), independent of \(X_2\), and contributes \(1\). Their sum is \(3\), the correct answer.
The identity is useful because it separates the mean size of an increment from the expected number of increments collected. Its assumptions do real work: integrability of \(X_1\) and finite \(\mathbb{E}[\tau]\) ensure the stopped sum is integrable, while the stopping-time condition ensures that inclusion of \(X_k\) is decided before \(X_k\) is observed. If a rule uses future increments to decide whether to include a present one, the key independence step need not hold.
Check Your Understanding
Use the indicator \(\mathbf{1}_{\{\tau\ge k\}}\) and check which information is available before increment \(X_k\) is observed.
- For integrable iid increments and a stopping time with finite expectation, why does \(\{\tau\ge k\}\) belong to \(\mathcal{F}_{k-1}\)?
- If \(\mathbb{E}[X_1]=-\tfrac13\) and \(\mathbb{E}[\tau]=6\), what is \(\mathbb{E}[S_\tau]\), assuming the theorem’s hypotheses hold?
- For the rule in the second worked example, calculate \(\mathbb{E}[X_2\mathbf{1}_{\{\tau\ge2\}}]\) and identify the independence that justifies the calculation.
- Explain why \(\{\tau=k\}\) need not be independent of \(X_k\), even when \(\tau\) is a stopping time.
- What condition in the proof ensures that exchanging expectation and the infinite indicator sum is valid?