Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science November 3, 1998 Professors Nancy Lynch and Srinivas Devadas

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 such that

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

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

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

provided that the expectations on the right are finite.

Informally, the first 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.

We can now solve the coin-and-dice problem. 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}, R_{3} 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 Linearity of Expectation for Infinite Sums

The proof of Wald’s Theorem uses a generalization of linearity of expectation to the case of an infinite sum. We state this generalization without proof.

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

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

is finite, then

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

3 Proof of the 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} = 1 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 first step of the proof is to take expectations on both sides of this equation.

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

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

= ∑_{i=1}^{∞} ∑_{x} x · Pr(R_{i} · I_{i} = x)  (3)

= ∑_{i=1}^{∞} ∑_{x} x · Pr(R_{i} = x ∩ I_{i} = 1)  (4)

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

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

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

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

Step 2 follows from Fact 1. Step 3 uses the definition of expected value. The inner summation is over x in the range of R_{i} · I_{i}, which is the range of R unioned with {0}. Step 4 uses a fact about multiplication. (This step is valid for the x = 0 term of the summation, since this term is zero both before and after the step.) Step 5 follows from the condition in the theorem that Pr(R_{i} = x | I_{i} = 1) = Pr(R = x). In step 6, we pull the constant Pr(I_{i} = 1) out of the inner summation. Step 7 uses the definition of expected value, and step 8 uses the definition of the indicator variables I_{i}. Finally, step 9 uses an identity for the expectation of a random variable with range ℕ.