Massachusetts Institute of Technology Handout 46 6.042J/18.062J: Mathematics for Computer Science May 2, 1998 Professors David Karger and Nancy Lynch

Wald’s Theorem

1 Theorem Statement

Wald’s Theorem concerns the expected sum of a random number of random variables. For example, suppose that I flip a coin. If I get heads, then I roll two dice. If I get tails, then I roll three dice. What is the expected sum of the dice that I roll? Wald’s Theorem supplies a simple answer.

Theorem 1 (Wald’s Theorem). Let Q be a random variable with range ℕ, and let R, R_{1}, R_{2}, R_{3}, … be random variables with countable ranges such that

Pr(R_{i} = x | Q ≥ i) = Pr(R = x)

for all i ≥ 1 and all x in the range of R. Then

Ex(R_{1} + R_{2} + … + R_{Q}) = Ex(R) · Ex(Q)

provided that the expectations on the right exist and are finite.

The first equation in the theorem statement describes a tricky condition. Informally, this equation requires every random variable R_{i} appearing in the sum R_{1} + R_{2} + … + R_{Q} to have the same distribution as a “reference” random variable R. Note, however, that the distribution of a random variable R_{i} can be arbitrary in the event that R_{i} does not appear in the sum; that is, in the event that Q < i.

The coin-and-dice problem is solved easily using Wald’s Theorem. Based on the outcome of a coin toss, I roll either two or three dice. Thus, we define Q so that Pr(Q = 2) = Pr(Q = 3) = \frac{1}{2}, and we define R, R_{1}, R_{2}, … to take on values in the range 1 to 6 uniformly. The sum of the dice that I roll is equal to R_{1} + … + R_{Q}. By Wald’s Theorem, this sum is equal to:

Ex(R_{1} + … + R_{Q}) = Ex(R) · Ex(Q)
= \frac{7}{2} · \frac{5}{2}
= \frac{35}{4}

2 Proof Preliminaries

The proof of Wald’s Theorem requires two facts, which we state without proof. The first fact generalizes linearity of expectation to the case of an infinite sum.

Fact 1. Let R_{1}, R_{2}, R_{3}, … be random variables with countable ranges. If the summation

∑_{i=1}^{∞} |R_{i}|

converges for all points in the sample space, then

Ex (∑_{i=1}^{∞} R_{i}) = ∑_{i=1}^{∞} Ex(R_{i}).

The second fact that we will need is a statement about conditional expectation. The conditional expectation of a random variable R given an event E is denoted by Ex(R | E) and is defined as follows.

Ex(R | E) = ∑_{x∈Range(R)} x · Pr(R = x | E)

The fact that we need about conditional expectation is stated below.

Fact 2. Let R be a random variable, and let E be an event. Then

Ex(R) = Ex(R | E) · Pr(E) + Ex(R | \overline{E}) · Pr(\overline{E})

provided that all the expectations exist and are finite.

3 Proof of Wald’s Theorem

We want to prove that

Ex(R_{1} + R_{2} + … + R_{Q}) = Ex(R) · Ex(Q).

The sum R_{1} + R_{2} + … + R_{Q} is awkward, because the final subscript Q is a random variable. We eliminate this awkwardness by introducing some indicator random variables. In particular, let I_{i} be an indicator for the event that R_{i} appears in the sum R_{1} + R_{2} + … + R_{Q}; that is, I_{i} is the event that Q ≥ i. With this definition, we can rewrite the sum as follows.

R_{1} + R_{2} + … + R_{Q} = ∑_{i=1}^{∞} R_{i} · I_{i}

In effect, the indicator variables I_{i} “mask out” random variables R_{i} that do not appear in the sum R_{1} + R_{2} + … + R_{Q}. The proof of Wald’s Theorem begins by taking the expected value of both sides of this equation.

Ex(R_{1} + R_{2} + … + R_{Q}) = Ex (∑_{i=1}^{∞} R_{i} · I_{i})

According to Fact 1, we can apply linearity of expectation to break up this infinite sum provided that the sum

∑_{i=1}^{∞} |R_{i} · I_{i}|

always converges. At each point in the sample space, the random variable Q takes on some value in ℕ. Thus, at each point in the sample space, only finitely many of the indicator variables I_{i} are non-zero. Consequently, for each point in the sample space, the sum contains of only finitely many non-zero terms, and so the sum always converges. Thus, we can apply linearity of expectation and continue reasoning as follows.

Ex(R_{1} + R_{2} + … + R_{Q}) = ∑_{i=1}^{∞} Ex (R_{i} · I_{i})

= ∑_{i=1}^{∞} (Ex (R_{i} · I_{i} | I_{i} = 1) · Pr(I_{i} = 1) +
Ex (R_{i} · I_{i} | I_{i} = 0) · Pr(I_{i} = 0))
= ∑_{i=1}^{∞} Ex (R_{i} | I_{i} = 1) · Pr(I_{i} = 1)

The second equation uses Fact 2, and the third equation follows by simpifying. The next step is to simplify the conditional expectation in the last expression above. We break out and simplify this term below and then return to the main line of the argument.

Ex (R_{i} | I_{i} = 1) = ∑_{x} x · Pr(R_{i} = x | I_{i} = 1)
= ∑_{x} x · Pr(R_{i} = x | Q ≥ i)
= ∑_{x} x · Pr(R = x)
= Ex(R)

The first step uses the definition of expectation, the second step uses the definition of the indicator variable I_{i}, the third step uses the technical assumption in the theorem statement, and the final step uses the definition of expectation again. All summations are over x in the range of R_{i}.

Using this result, we can wrap up the proof of Wald’s Theorem.

Ex(R_{1} + R_{2} + … + R_{Q}) = ∑_{i=1}^{∞} Ex(R) · Pr(I_{i} = 1)

= Ex(R) · ∑_{i=1}^{∞} Pr(I_{i} = 1)

= Ex(R) · ∑_{i=1}^{∞} Pr(Q ≥ i)
= Ex(R) · Ex(Q)

The constant Ex(R) is pulled out in the second equation. The third step uses the definition of the indicator variable I_{i}, and the final step uses an identity for the expecatation of a random variable with range ℕ.