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
The first result of this type has appeared in the seminal paper of Abraham Wald on sequential hypothesis testing (hence the name), and it can be stated as follows:
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
Blackwell’s proof
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.
Seems like a renewal-reward theorem argument with the \tau sequence being the renewal epochs and the S sequence being the rewards that one gets.
That’s certainly a nice take on it.
Ah so cute!