Wald's Identity

E[ _i=1^N X_i] = E[N] · E[X_1] for stopping times N.

The idea

Definition (Stopping time).

Let $X_1, X_2, \ldots$ be a sequence of random variables. A random number of terms $N$ is a stopping time if the decision to stop at $n$ depends only on $X_1, \ldots, X_n$, never on later terms.

Theorem (Wald's identity).

Let $X_1, X_2, \ldots$ be independent draws from the same distribution with $\mathbb{E}[|X_1|] < \infty$, and let $N$ be a stopping time with $\mathbb{E}[N] < \infty$. Then $\mathbb{E}\!\left[\sum_{i=1}^{N} X_i\right] = \mathbb{E}[N]\,\mathbb{E}[X_1].$

The first $n$ at which the partial sum $S_{n} = X_{1} + \cdots + X_{n}$ reaches a fixed level $\ell$ is a stopping time; the figure shows such a path stopped at the moment it crosses $\ell$.

For a fixed number of terms the identity is elementary: a sum of $n$ terms has mean $n\,\mathbb{E}[X_1]$ by linearity of expectation. The content of Wald's identity is that the same product survives when $N$ is random and decided by the very terms being added, so that the number of summands and the summands themselves are dependent.

The stopping-time condition is what makes this true. A rule allowed to look ahead could stop just after unusually large terms and push the sum well above $\mathbb{E}[N]\,\mathbb{E}[X_1]$; forbidding $N$ from seeing the future removes that advantage. The requirement that $\mathbb{E}[N]$ be finite is equally necessary.

Used in reverse, the identity computes expected waiting times: when we know what the sum equals at the moment of stopping, dividing by $\mathbb{E}[X_1]$ gives the expected number of terms.

Ways to work on it

• Walkthrough. Use Wald's identity to find the expected wait for a first heads.
• Practice. Use Wald's identity to compute expectations of random sums.
• Hardest. Decide whether Wald's identity applies to a given random-sum scenario.

Not sure where to start? Take the ten-question placement test.