Wald's equation ($\mathbb{E}[S_N]=\mathbb{E}[X_1]\mathbb{E}[N]$)

Wald's equation turns a random sum into a product of two expected values: the average contribution per step and the average number of steps. Its surprising feature is that the number of steps may depend on what has already happened. A procedure can stop on its first successful Bernoulli trial, for example, while the identity still accounts for its total cost. The crucial restriction is that the decision to take the next step cannot use that step's unobserved outcome.

Let $X_1,X_2,\dots$ be real independent and identically distributed random variables with $\mathbb{E}|X_1|<\infty$, let $\mu =\mathbb{E}[X_1]$, and put $S_0=0$ and $S_n={\sum }_{i=1}^n{X}_i$. Suppose $N$ is a nonnegative integer-valued stopping time for the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$, with $\mathbb{E}[N]<\infty$. Then $S_N$ is an integrable random variable andThese hypotheses allow statistical dependence between $N$ and the increments; they do not allow access to future increments. The finite-expected value requirement is stronger than stopping almost surely.^[ref]

For the proof idea, count step $i$ only on $\{N\ge i\}$. This event is determined by the first $i-1$ observations, so its indicator function is independent of $X_i$. The Proof of Wald's equation by stopping indicators combines this observation with the tail-sum formula for expectation. The same calculation with $|X_i|$ gives $\mathbb{E}{\sum }_{i=1}^N|X_i|=\mathbb{E}|X_1|\mathbb{E}[N]<\infty$, which justifies interchanging the expected value and the infinite series. This is why the result survives a data-dependent end point without assuming an independent count.

The identity is useful in randomized algorithms and repeated sampling: one can translate an average amount of work into an average number of attempts, or conversely, without first finding the full probability distribution of the total. The examples below separate a permissible stopping rule from a rule that peeks ahead and from a valid rule whose average waiting time is infinite.

Consider a stipulated repeated-attempt model, with independent Bernoulli trials of success probability $p\in (0,1]$. An unsuccessful attempt costs three units of work, and a successful attempt costs one. Let $B_i$ be its success indicator function, $X_i=3-2B_i$ its cost, and $N=\inf \{i\ge 1:B_i=1\}$ the first success. Observing $X_i$ reveals $B_i$, so $N$ is a stopping time for the costs' natural filtration. The geometric distribution gives $\mathbb{P}(N\ge i)=(1-p{)}^{i-1}$ and $\mathbb{E}[N]=1/p$, including the deterministic case $p=1$. ThusAt $p=1/4$, the average is four attempts and ten units of work. An independent check uses the pathwise identity $S_N=3(N-1)+1$: there are $N-1$ failures and one final success. No success probabilities or costs in this example are measured data.

Here $N$ is not independent of the observed costs. In particular, conditioning on $N=n$ forces every preceding cost to be three and the final cost to be one, so $\mathbb{E}[S_N\mid N=n]=3n-2$, generally different from $n\mathbb{E}[X_1]=(5/2)n$ at $p=1/4$. Nevertheless the unconditional identity holds. This distinction explains why conditioning on the total count as though the original cost law remained unchanged is a faulty proof.

Let $X_1,X_2$ be independent fair signs, each taking $-1$ and $1$ with equal probability. Set $N=1$ if $X_2=1$, and $N=2$ if $X_2=-1$. Deciding whether $N\le 1$ requires the second sign, so $N$ is not a stopping time for the natural filtration. The four equally likely possibilities giveBoth the increments and the count are bounded, but the identity fails because the second contribution is retained only when it is negative. This is selection using an unobserved outcome, rather than a legitimate sequential decision. Boundedness alone cannot replace the stopping time hypothesis.^[ref]

For a simple symmetric random walk starting at zero, let $T_1$ be its first hitting time of $1$. The infinite mean first passage of a simple symmetric random walk shows that $T_1<\infty$ almost surely but $\mathbb{E}[T_1]=\infty$. Since $S_{T_1}=1$, assuming a finite expected value for $T_1$ would let Wald's equation assert $1=0\mathbb{E}[T_1]=0$, a contradiction. The formal expression $0\cdot \infty$ is not an allowed use of the theorem.^[ref]

Compare $T_{\pm 2}=\inf \{n\ge 0:|S_n|=2\}$. From every surviving position in $\{-1,0,1\}$, three consecutive positive increments force absorption within three steps. Each fresh block has probability $1/8$ of this event, so $\mathbb{P}(T_{\pm 2}>3k)\le (7/8{)}^k$ and $\mathbb{E}[T_{\pm 2}]\le 24$. This establishes finiteness before invoking the theorem. If $e_j$ is the average remaining time from position $j$, the law of total expectation givesso $\mathbb{E}[T_{\pm 2}]=4$. Symmetry gives equal exit probabilities at $-2$ and $2$, and $\mathbb{E}[S_{T_{\pm 2}}]=0$, as Wald's equation predicts. This is a small gambler's ruin problem with two absorbing barriers.

Even for $T_1$, each bounded stopping time $T_1\wedge n$ satisfies $\mathbb{E}[S_{T_1\wedge n}]=0$. The stopped process tends to $1$ almost surely, but its expected value does not tend to $1$. Rare long negative excursions retain the balancing contribution. The existing stopped-walk martingale with almost sure but not L1 convergence explains the related failure of uniform integrability; almost sure convergence alone does not permit exchanging a limit and an expected value.

If $M$ is a stopping time for independent identically distributed integrable variables $X_i$ and $\mathbb{E}M<\infty$, then $\{M\ge i\}$ depends only on $X_1,\dots ,X_{i-1}$ and is independent of $X_i$. HenceThe interchange is justified because the same calculation with $|X_i|$ gives finite expected absolute sum.