Wald's equation
= Wald's equation
{c}
{title2=$\mathbb E[S_N]=\mathbb E[X_1]\,\mathbb E[N]$}
{wiki}
= Wald identity
{c}
{synonym}
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,\ldots$ 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}^nX_i$. Suppose $N$ is a nonnegative integer-valued <stopping time> for the <natural filtration> $\mathcal F_n=\sigma(X_1,\ldots,X_n)$, with $\mathbb E[N]<\infty$. Then $S_N$ is an <integrable random variable> and
$$
\boxed{\mathbb E[S_N]=\mu\,\mathbb E[N].}
$$
These 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>.<18.175 Lecture 16: Conditional expectation, random walks, martingales by Scott Sheffield>[PDF pp. 38–42 and 45–47]{ref}
For the proof idea, count step $i$ only on $\{N\geq 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.