Massachusetts Institute of Technology Lecture 24 6.042J/18.062J: Mathematics for Computer Science 5 December 2000 Professors Nancy Lynch and Srinivas Devadas

Computing Expectation

1 The Expected Value of a Product

This lecture continues the discussion of expected value.

In the last lecture, we looked at the expected value of a sum of random variables. The main result, called linearity of expectation, says that the expected value of a sum is the sum of the expected values; that is, Ex(R_{1} + R_{2}) = Ex(R_{1}) + Ex(R_{2}). The wonderful thing about linearity of expectation is that R_{1} and R_{2} need not be independent.

In this lecture, we will look at the expected value of a product of random variables. If R_{1} and R_{2} are independent, then an analogous result holds. Namely, the expected value of a product is the product of the expected values.

Theorem 1.1 For any two independent random variables R_{1} and R_{2}

Ex(R_{1} · R_{2}) = Ex(R_{1}) · Ex(R_{2})

Proof. We will transform the left side into the right side. We first use the definition of expected value.

Ex(R_{1} · R_{2}) = ∑_{x∈Range(R_{1}·R_{2})} x · Pr(R_{1} · R_{2} = x)

Next, we break the summation over the product R_{1} · R_{2} into separate sums over R_{1} and R_{2}.

= ∑_{x_{2}∈Range(R_{2})} ∑_{x_{1}∈Range(R_{1})} x_{1}x_{2} · Pr((R_{1} = x_{1}) ∩ (R_{2} = x_{2}))

We now use the fact that R_{1} and R_{2} are independent. The probability of the intersection of the events R_{1} = x_{1} and R_{2} = x_{2} is the product of the probabilities of the two events.

= ∑_{x_{2}∈Range(R_{2})} ∑_{x_{1}∈Range(R_{1})} x_{1}x_{2} · Pr(R_{1} = x_{1}) · Pr(R_{2} = x_{2})

In the remaining four steps, we alternate pulling a term out of a summation and applying the definition of expected value.

= ∑_{x_{2}∈Range(R_{2})} x_{2} · Pr(R_{2} = x_{2}) ∑_{x_{1}∈Range(R_{1})} x_{1} · Pr(R_{1} = x_{1})
= ∑_{x_{2}∈Range(R_{2})} x_{2} · Pr(R_{2} = x_{2}) · Ex(R_{1})
= Ex(R_{1}) ∑_{x_{2}∈Range(R_{2})} x_{2} · Pr(R_{2} = x_{2})

= Ex(R_{1}) · Ex(R_{2})

1.1 The Product of Two Independent Dice

Suppose we throw two independent, fair dice and multiply the numbers that come up. What is the expected value of this product?

Let random variables R_{1} and R_{2} be the numbers shown on the two dice. We can compute the expected value of the product as follows:

Ex(R_{1} · R_{2}) = Ex(R_{1}) · Ex(R_{2})
= 3\frac{1}{2} · 3\frac{1}{2}
= 12\frac{1}{4}

The first step uses Theorem 1.1 and the fact that the dice are independent. In the second step, we use the result from last lecture that the expected value of one die is 3\frac{1}{2}. The last step is simplification. The expected value of the product is 12\frac{1}{4}.

1.2 The Product of Two Dependent Dice

Suppose that the two dice are not independent; in fact, assume that the second die is always the same as the first. Now what is the expected value of the product?

Because the dice are not independent, we can no longer apply Theorem 1.1. However, is the expected value of the product really changed by this loss of independence? As before, let random variables R_{1} and R_{2} be the numbers shown on the two dice. We can compute the expected value of the product without Theorem 1.1 as follows:

Ex(R_{1} · R_{2}) = Ex(R_{1}^{2})
= ∑_{i=1}^{6} i^{2} · Pr(R_{1} = i)

= \frac{1^{2}}{6} + \frac{2^{2}}{6} + \frac{3^{2}}{6} + \frac{4^{2}}{6} + \frac{5^{2}}{6} + \frac{6^{2}}{6}
= 15\frac{1}{6}

The first step uses the fact that the outcome of the second die is always the same as the first. In the second step, we expand Ex(R_{1}^{2}) according to the definition of expected value. In the third step, we use the fact that the probability of each number coming up is \frac{1}{6}, since the dice are fair. The last step is simplification. The expected value of the product has changed to 15\frac{1}{6}.

The preceding two examples show that for dependent variables, the expected value of a product need not be the product of the expected values; that is, Ex(R_{1} · R_{2}) ≠ Ex(R_{1}) · Ex(R_{2}). The general rules for expected values of sums and products are summarized below.

For random variables R_{1} and R_{2}:

• Regardless of whether R_{1} and R_{2} are independent, Ex(R_{1} + R_{2}) = Ex(R_{1}) + Ex(R_{2}).

• If R_{1} and R_{2} are independent, then Ex(R_{1} · R_{2}) = Ex(R_{1}) · Ex(R_{2}).

1.3 Corollaries

Theorem 1.1 extends to a collection of mutually independent variables.

Corollary 1.2 If random variables R_{1}, R_{2}, …, R_{n} are mutually independent, then

Ex(R_{1} · R_{2} ⋯ R_{n}) = Ex(R_{1}) · Ex(R_{2}) ⋯ Ex(R_{n})

The proof of the corollary is an induction argument using Theorem 1.1 and the definition of mutual independence.

Details are omitted here.

Adjusting a random variable by an additive or multiplicative constant adjusts the expected value in the same way.

Corollary 1.3 If R is a random variable and a and b are constants, then

Ex(aR + b) = a Ex(R) + b

This corollary is proved by regarding a and b as random variables that take on a particular value with probability 1. We can prove that a is always independent of R. The result then follows from linearity of expectation and Theorem 1.1.

2 The Danger of Expectation of Quotients

We now know the expected value of a sum or product of random variables. Unfortunately, the expected value of a reciprocal is not so easy to characterize. Here is a flawed attempt.

False Theorem 1 If Z and R are independent random variables with R ≠ 0 (that is, R can never be 0) then Ex(Z/R) = Ex(Z)/ Ex(R)

Proof.

Ex(Z) = Ex((Z/R) · (R))
= Ex(Z/R) · Ex(R)

by Theorem 1.1. Now divide both sides by Ex(R).

This proof is bogus! We can not apply Theorem 1.1 in the second step, because Z/R and R are not necessarily independent. Indeed, one can see the likely dependence: R being large will make Z/R small.

Of course, a bogus proof does not mean a false theorem, so here is a counterexample:

Suppose the random variable Z = 1 always (with probability 1), while the random variable R is 1 with probability \frac{1}{2} and is 2 with probability \frac{1}{2}. Then we have:

\frac{1}{Ex(R)} = \frac{1}{1 · \frac{1}{2} + 2 · \frac{1}{2}} = \frac{2}{3}

Ex(\frac{1}{R}) = \frac{1}{1} · \frac{1}{2} + \frac{1}{2} · \frac{1}{2} = \frac{3}{4}

The two quantities are not equal, so the theorem is false.

3 Conditional Expectation

Just like event probabilities, expectations can be conditioned on some event.

Definition 3.1 The conditional expectation of X given event A, written Ex[X | A] is

∑_{x} x · Pr(X = x | A)

In other words, it is the expected value of the variable X once we skew the distribution of X to be conditioned on event A.

Example 3.2 Let D be the outcome of a random fair die role. What is E[D | D ≥ 4]?

∑_{i=1}^{6} i · Pr(D = i | D ≥ 4) = ∑_{i=4}^{6} i · 1/3

= 5

Since E[X | A] is just an expectation over a different probability distribution, it is unsurprising that the rules for expectation extend to conditional expectation:

Theorem 3.3 Ex(X + Y | A) = Ex(X | A) + Ex(Y | A).

A real benefit of conditional expectation is the way it lets you divide complicated expectation calculations into simpler ones.

Theorem 3.4 Let A_{1}, A_{2}, ⋯ be a partition of the sample space: that is, ∪A_{i} is the entire sample space, but A_{i} ∩ A_{j} = ∅ for any i ≠ j. Then

Ex(X) = ∑_{i} Ex(X | A_{i}) Pr(A_{i})

provided that all the expectations exist and are finite.

In other words, tree diagrams work for expectations too.

Proof.

Ex(X) = ∑_{x} x · Pr(X = x)

= ∑_{x} x · ∑_{i} Pr(X = x | A_{i}) Pr(A_{i})

= ∑_{i} ∑_{x} x · Pr(X = x | A_{i}) Pr(A_{i})

= ∑_{i} Pr(A_{i}) ∑_{x} x · Pr(X = x | A_{i})

= ∑_{i} Pr(A_{i}) Ex(X | A_{i})

Example 3.5 Half the people in the world are male, half female. The expected height of a randomly chosen male is 5′11′′, while the expected height of a randomly chosen female is 5′5′′. What is the expected height of a randomly chosen individual?

Let H(P) be the height of the randomly person P. The events M =“P is male” and F =“P is female” are a partition of the sample space (at least for the moment—though with modern science you never know). Then

Ex(H) = Ex(H | M) Pr(M) + Ex(H | F) Pr(F)

= 5′11′′ · \frac{1}{2} + 5′5′′ · \frac{1}{2}

= 5′8′′

4 Wald’s Theorem

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.

4.1 Theorem Statement

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

1. All R_{i} have the same distribution.

2. For all i, random variable R_{i} is independent of the event Q ≥ i

Then

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

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

The condition in the theorem requires that 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.

The second, “independence” condition in the theorem needs to be explained. It mixes our previous notions of independence of events and independence of random variables in a natural way. It means that that each event R_{i} = x is independent of the event 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}

4.2 Proof Preliminary

The proof of Wald’s Theorem requires a fact, which we state without proof. It 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}).

4.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. Then

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 nonzero. 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 Theorem 3.4, and the third equation follows by simplifying. 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_{i} = x)
= Ex(R_{1})

since all the R_{i} have the same distribution, so same expectation.

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_{1}) · Pr(I_{i} = 1)

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

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

The constant Ex(R_{1}) 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 expectation of a random variable with range ℕ.

5 Building a System

Wald’s Theorem turns out to be useful in analyzing algorithms and systems. The following example was taught incorrectly in 6. 033 for several years. The problem– and erroneous solution– originated in a paper by Herbert Simon, who won the Nobel Prize in economics.

Suppose that we are trying to build a system with n components. We add one component at a time. However, whenever we add a component, there is a probability p that the whole system falls apart and we must start over from the beginning. Assume that these collapses occur mutually independently. What is the expected number of steps required to finish building the system?

5.1 The Sample Space

We can regard the sample points in this experiment as infinite strings of S’s and F ’s. An S in the i-th position indicates that a component is successfully added in the i-th step. An F in the i-th position indicates that the system falls apart in the i-th step. For example, in outcome SSF SF … we add two components, and then the system collapses while we are adding the third. So we start over from scratch. We then add one component successfully, but the system collapses again while we are adding the second. We start over again, etc.

Using this notation, the system is completed after we encounter a string of n consecutive S’s. This indicates that all n components were added successfully without the system falling apart. For example, suppose we are building a system with n = 3 components. In outcome SSF SF F \underline{SSS}F SF …, the system is completed successfully after 9 steps, since after 9 steps we have encountered a string of three consecutive S’s.

5.2 Tries

Define a “try” to be a sequence of steps that starts with a system of zero components and ends when the system is completed or collapses. Let R_{k} be the number of steps in the k-th try, and let Q be the number of tries required to complete the system. The number of steps needed to build the system is then:

T = ∑_{k=1}^{Q} R_{k}

For example, if we are building a system with n = 3 components, then we can break outcome SSF SF F SSSF SF … into tries as shown below:

\underbrace{S S F}_{\begin{matrix}R_{1} = 3 \\ failure \end{matrix}} \underbrace{S F}_{\begin{matrix}R_{2} = 2 \\ failure \end{matrix}} \underbrace{F}_{\begin{matrix}R_{3} = 1 \\ failure \end{matrix}} \underbrace{S S S}_{\begin{matrix}R_{4} = 3 \\ success! \end{matrix}} \underbrace{F}_{\begin{matrix}R_{5} = 1 \\ failure \end{matrix}} \underbrace{S F}_{\begin{matrix}R_{6} = 2 \\ failure \end{matrix}} …

(Note that we regard an outcome as an infinite string of S’s and F ’s, and so an outcome formally consists of an infinite number of tries. However, the remainder of the string after the first successful try is not relevant. )

In the above example, four tries are required to complete the system, so we have Q = 4. The number of steps needed to complete the system is:

T = ∑_{k=1}^{Q} R_{k} = R_{1} + R_{2} + R_{3} + R_{4} = 3 + 2 + 1 + 3 = 9

5.3 Applying Wald’s Theorem

Our goal is to determine Ex(T), the expected number of steps needed to complete the system. The first step is to apply Wald’s Theorem:

Ex(T) = Ex (∑_{k=1}^{Q} R_{k})
= Ex(Q) · Ex(R)

Here R is a random variable indicating the number of steps in a try.

To verify the second step, we must check the three conditions in Wald’s Theorem. First, the number of tries, Q, is always a non-negative integer. We will show that Ex(Q) is finite later. Second, all tries are symmetric, so all random variables R_{k} have the same distribution. Furthermore, Ex(|R|) is finite because every try lasts at most n steps. Third, the number of steps in try k is independent of the event that k or more tries are required; that is, R_{k} is independent of an indicator variable for the event that Q ≥ k.

(Note that we are using the general form of Wald’s Theorem, not the restricted form that we proved. The number of tries Q is not bounded above by any constant c. )

To solve the problem, we must still find Ex(Q) and Ex(R_{1}).

5.4 Computing the Expected Number of Tries

Let’s compute Ex(Q), the expected number of tries needed to complete the system.

First, we will compute the probability that a particular try is successful. A successful try consists of n consecutive S’s. The probability of an S in each position is 1 − p. The probability of n consecutive S’s is therefore (1−p)^{n}; we can multiply probabilities, since system collapses occur mutually independently.

Now, if a try is successful with probability (1 − p)^{n}, what is the expected number of tries needed to succeed? We encountered this question in another guise during the last lecture. Then we asked the expected number of hours until Mir’s main computer went down, given that it went down with probability q in each hour. We found that the expected number of hours until a main computer failure was \frac{1}{q}. Here we want the number of tries before the system is completed, given that a try is successful with probability (1 − p)^{n}. By the same analysis, the expected number of tries needed to succeed is \frac{1}{(1−p)^{n}}. Therefore, we have:

Ex(Q) = \frac{1}{(1 − p)^{n}}

This also shows that Q is finite, provided p ≠ 1.

5.5 Computing Expected Length of a Try

Now let’s compute Ex(R), the expected number of steps in a try. Since the number of steps in a try is always a non-negative integer, we can write:

Ex(R) = ∑_{i=0}^{∞} Pr(R > i)

= ∑_{i=0}^{n−1} Pr(R > i)

The second equality holds because a try never lasts for more that n steps; if the system does not collapse within n steps, then the system is completed, and the try is done anyway. Therefore, Pr(R > n) = 0, and so only the first n terms of the infinite sum can be non-zero.

Now we must evaluate Pr(R > i), the probability that a try consists of more than i steps. This is just the probability that the system does not collapse in the first i steps, which is (1 − p)^{i}. Therefore, Pr(R > i) = (1 − p)^{i}. Substituting this into the equation above and summing the resulting geometric series gives the expected number of steps in a try:

= ∑_{i=0}^{n−1}(1 − p)^{i}

= \frac{1 − (1 − p)^{n}}{1 − (1 − p)}
= \frac{1 − (1 − p)^{n}}{p}

Now we can compute the expected number of steps needed to complete the system.

Ex(T) = Ex(Q) · Ex(R)
= \frac{1}{(1 − p)^{n}} · \frac{1 − (1 − p)^{n}}{p}
= \frac{1 − (1 − p)^{n}}{p(1 − p)^{n}}
= \frac{1}{p(1 − p)^{n}} − \frac{1}{p}

For example, suppose that there is only a 1% chance that the system collapses when we add a component (p = 0.01). The expected number of steps to completed a system with n = 10 components is about 10. For n = 100 components, the number of steps is about 173. But for n = 1000 components, the number is about 2,316,257. As the number of components increases, the number of steps required increases exponentially! The intuition is that adding, say, 1000 components without a single failure is very unlikely; therefore, we need a tremendous number of tries!

5.6 A Better Way to Build Systems

The moral of this analysis is that one should build a system in pieces so that all work is not lost in a single accident.

For example, suppose that we break a 1000 components system into 10 modules, each with 10 submodules, each with 10 components. Assume that when we add a component to a submodule, the submodule falls apart with probability p. Similarly, we can add a submodule to a module in one time step, but with probability p the module falls apart into submodules. (The submodules remain intact, however. ) Finally, we can add a module into the whole system in one time step, but the system falls apart into undamaged modules with probability p.

Altogether, we must build a system of 10 modules, build 10 modules consisting of 10 submodules each, and build 100 submodules consisting of 10 components each. This is equivalent to building 111 systems of 10 components each. The expected time to complete the system is 111 · 10.57 … ≈ 1173 steps. This compares very favorably with the 2. 3 million steps required in the direct method!