Blackwell’s proof of Wald’s identity
Every once in a while you come across a mathematical argument of such incredible beauty that you feel compelled to tell the whole world about it. This post is about one such gem: David Blackwell’s 1946 proof of Wald’s identity on the expected value of a randomly stopped random walk. In fact, even forty years after the publication of that paper, in a conversation with Morris DeGroot, Blackwell said: “That’s a paper I’m still very proud of. It just gives me pleasant feelings every time I think about it.”
Let be a sequence of independent real-valued random variables with common mean . Let be a stopping time, i.e., a random variable taking values in , such that the occurrence or nonoccurrence of the event is determined only by . We say that Wald’s identity holds for the pair if
Theorem 1 Assume that are i.i.d., , and . Then Wald’s identity holds for the pair .
The standard proof of this theorem uses martingale arguments. In 1946, David Blackwell found a beautiful proof that uses only Kolmogorov‘s Strong Law of Large Numbers (SLLN) and its converse. Since the latter is, perhaps, less well known than the former, I will just give both for convenience (see, e.g., Chapter 12 in Probability With Martingales by David Williams):
- SLLN: Let be i.i.d. with for all . Then
- Converse to SLLN: If are i.i.d. with , then
Let us define recursively a sequence of random variables as follows. Let . Then, assuming have been defined, let
In other words, is the stopping time determined by the original full sequence , is the stopping time determined by the remaining data after the first stopping time, i.e., by , is the stopping time determined by the data remaining after the second stopping time, i.e., by , etc. We now claim that is an i.i.d. sequence. To see this, let us compute the conditional probability that given . Given positive integers , define the event
as well as the event
By construction, the occurrence or nonoccurrence of is determined only by , so is independent of . Therefore,
Moreover, since the ‘s are i.i.d., . Thus, we have shown that, for every and every ,
from which we conclude that is an i.i.d. sequence.
Now let us define, for each , the random variable
(where ). Exactly the same argument as above can be used to show that are i.i.d.. Now, noting that
we can write
Let’s see what happens as . First of all, if we let , then, by the SLLN, a.s. as . Since any subsequence of a convergent sequence converges to the same limit, we have
Moreover, since are i.i.d. with mean , almost surely as . Therefore,
Now we invoke the converse to the SLLN (more precisely, the contrapositive to the converse): Since are i.i.d. and the limit of exists a.s., then is finite and equal to this limit. Hence,
The theorem is proved.