Massachusetts Institute of Technology Handout 61 6.042J/18.062J: Mathematics for Computer Science May 8, 1999 Professor Albert R. Meyer

Problem Set 11 Solutions

Problem 1. (10 points) Compute the expected value for each of the following random variables. (Assume that all dice are fair and six-sided and that dice rolls are mutually independent.)

(a) The sum of the rolls of three dice.

Solution: The expected value of one die roll is

1 · \frac{1}{6} + 2 · \frac{1}{6} + 3 · \frac{1}{6} + 4 · \frac{1}{6} + 5 · \frac{1}{6} + 6 · \frac{1}{6} = \frac{7}{2}.

By linearity of expectation, the sum three rolls is

\frac{7}{2} + \frac{7}{2} + \frac{7}{2} = \frac{21}{2}.

(b) The product of the rolls of three dice.

Solution: For independent random variables, the expectation of the product is the product of the expectations. Therefore, the expected product is

\frac{7}{2} · \frac{7}{2} · \frac{7}{2} = \frac{343}{8}.

(c) The sum of the rolls of a number of dice that is given by the roll of a single die. (For example, if you roll a 3 on the single die, then you take the sum of 3 dice rolls; if you roll a 5 on the single die, then you take the sum of 5 dice rolls.)

Solution: By Wald’s Theorem, the answer is the expected number of dice rolled multiplied by the expected roll of one die, which is

\frac{7}{2} · \frac{7}{2} = \frac{49}{4}.

(d) Suppose now that the dice rolls are not guaranteed to be mutually independent. Which of your answers above must still be correct?

Solution: The first answer remains valid because linearity of expectation does not require independence. Neither of the remaining answers is necessarily correct, however; both make use of independence.

Problem 2. (15 points) Compute your expected payoff for the following two games.

(a) You roll two fair, independent, six-sided dice. If the sum is one of the five values 5, 6, 7, 8 or 9, then you pay me $1. If the sum is one of the six values 2, 3, 4, 10, 11, or 12, then I pay you $1.

Solution:

E [payoff in dollars]

= −1 · (\frac{4}{36} + \frac{5}{36} + \frac{6}{36} + \frac{5}{36} + \frac{4}{36}) + 1 · (\frac{1}{36} + \frac{2}{36} + \frac{3}{36} + \frac{3}{36} + \frac{2}{36} + \frac{1}{36})
= −1/3.

So you expect to lose 33 1/3 cents on each roll.

(b) You flip a fair coin until you get a head. For each tail that you flipped, you are allowed to roll a fair, six-sided die. I pay you a number of dollars equal to the sum of all your dice rolls. The catch is that I charge you 3 dollars initially just to play this game. (Assume that all coin flips and dice rolls are mutually independent.)

Solution: The expected number of tails is 1. The expected outcome of a die roll is 31/2. Therefore, by Wald’s Theorem, the expected dollar payoff is 1 · 31/2 − 3 = 1/2, namely 50 cents.

Problem 3. (10 points) There is a dinner party for n ≥ 2 couples. The hostess chooses a seating arrangement for the 2n people around a circular table uniformly at random. What is the expected number of couples such that the husband and wife are sitting next to each other?

Solution: Let I_{k} be an indicator variable for the event that couple k is sitting together. Then the number of couples sitting together is I_{1} + I_{2} + … + I_{n}. The probability that a couple is seated together is 2/(2n − 1), since a wife is equally likely to occupy each of the 2n−1 positions relative to her husband and there are 2 positions right next to him. Consequently, Pr {I_{k} = 1} = 2/(2n − 1), and we can reason as follows:

E [number of couples sitting together]

= E [∑_{k=1}^{n} I_{k}] = ∑_{k=1}^{n} E [I_{k}]

= ∑_{k=1}^{n} Pr \{I_{k} = 1\} = ∑_{k=1}^{n} \frac{2}{2n − 1} = \frac{2n}{2n − 1}

Thus, regardless of the size of the party, the expected number of couples seated together is always close to 1.

Problem 4. (10 points) Suppose that I roll n dice that are six-sided, fair, and mutually independent. What is the expected value of the largest number that comes up?

Solution: Let the random variable M be the largest number that comes up. We will use the identity

E [M] = ∑_{i=0}^{∞} Pr {M > i} .

We must compute the probability of the event M > i; that is, the event that some die shows a value greater than i.

E [M] = ∑_{i=0}^{5} Pr {M > i}

= ∑_{i=0}^{5} 1 − Pr {every die ≤ i}

= ∑_{i=0}^{5} 1 − (Pr {one die ≤ i})^{n}

= ∑_{i=0}^{5} 1 − (\frac{i}{6})^{n}
= 6 − \frac{1^{n} + 2^{n} + 3^{n} + 4^{n} + 5^{n}}{6^{n}}

Problem 5. (10 points) Stas, Zully, and Jared play the following game before 6.042 lecture. Each player puts $2 on the table and covertly writes down a number in the range 1 to 6. Then Stas rolls a fair, six-sided die. Everyone reveals their hidden numbers, and the money on the table is divided evenly among the players who correctly predicted the die roll. If no player correctly predicted the roll, then everyone takes their $2 back.

Stas and Jared guess numbers in the range 1 to 6 uniformly and independently at random. However, Zully peeks at Jared’s guess and picks a different number uniformly at random, independent of Stas’s guess.

(a) What is each player’s expected payoff?

Solution: Jared and Zully’s situations are symmetric. Between them, they pick a pair of distinct numbers uniformly at random and independently of Stas. We compute Stas’s expected payoff and derive Jared and Zully’s.

E [Stas’s payoff]

= 4 · Pr {Stas alone is right}

+ 1 · Pr {Stas and one other player are right} + 0 · Pr {All or none of the players are right} − 2 · Pr {Stas is wrong, another player is right}

= 4 · \frac{1}{6} · \frac{4}{6} + 1 · \frac{1}{6} · \frac{2}{6} − 2 · \frac{5}{6} · \frac{2}{6}
= −\frac{1}{18} dollars

Since the sum of all expected payoffs is zero, and Jared and Zully have the same expected payoff, their expected payoff must be 1/36 dollars.

(b) Subject to the restriction that Stas’s guess remain independent of Zully and Jared’s guesses, is there any guessing strategy Stas can use to increase his expected payoff? No proof is required, but explain your reasoning.

Solution: No. The calculation above remains valid no matter which number Stas guesses and even if he employs a randomized guessing strategy.

Problem 6. (15 points) In the board game Monopoly, the number of squares that a player advances in a single turn is determined by up to three rolls of dice as follows.

•Initially, the player rolls two dice, sums the results, and advances that many squares.

•If the same number comes up on both dice—this is called rolling a double—then the player rolls the dice a second time, sums the results, and advances that many additional squares.

•If the player rolled on double on the second roll, then the player rolls the dice a third time, sums the results, and advances that many additional squares.

•However, if third roll was a double, then the player “goes to jail”. We will treat this as though he had to reset his position to where he was just before the first roll, so the total number of squares advanced by the player in this case is zero.

What is the expected number of squares that a player advances in a single turn? Assume that the dice are fair and six-sided and that rolls are mutually independent.

Solution: Here is one approach to the problem.

It’s convenient to assume the dice are always rolled three times, with the player simply ignoring results of any roll which was preceded by a non-double roll.

Let the random variable R_{i} be the sum of the two dice on the ith roll, and let I_{i} be an indicator for the event that the ith roll was a double.

We can express the random variable R, the number of squares advanced by the player, as follows:

R = R_{1} + I_{1}R_{2} + I_{1}I_{2}R_{3} − I_{1}I_{2}I_{3}(R_{1} + R_{2} + R_{3})

Since the dice rolls are independent, we know that R_{i}’s and I_{j}’s at different rolls are independent. We can take expectations of both sides and reason as follows:

E [R] = E [R_{1}] + E [I_{1}R_{2}] + E [I_{1}I_{2}R_{3}]
− E [I_{1}I_{2}I_{3}R_{1}] − E [I_{1}I_{2}I_{3}R_{2}] − E [I_{1}I_{2}I_{3}R_{3}]
= E [R_{1}] + E [I_{1}] · E [R_{2}] + E [I_{1}] · E [I_{2}] · E [R_{3}]
− E [I_{2}] · E [I_{3}] · E [I_{1}R_{1}]
− E [I_{1}] · E [I_{3}] · E [I_{2}R_{2}]
− E [I_{1}] · E [I_{2}] · E [I_{3}R_{3}]

Note that the expectation of R_{i} is 7, and the expectation of I_{i} is 1/6. Finally, note that E [I_{i}R_{i}] = 7/6 by direct calculation. Substituting into the formula above gives:

E [R] = \frac{595}{72}.

Problem 7. (15 points) Suppose that R is a random variable. Let E be an event. The conditional expectation of R given that event E occurs is denoted E [R | E] and is defined to be

E [R | E] ::= ∑_{x∈range(R)} x · Pr {R = x | E} .

(a) Compute the expected value of the number rolled on a fair, six-sided die, given that the outcome is even.

Solution: Let the random variable R be the number rolled, and let E be the event that the number rolled is even.

E [R | E] = ∑_{x=1}^{6} x · Pr {R = x | E}
= 1 · 0 + 2 · \frac{1}{3} + 3 · 0 + 4 · \frac{1}{3} + 5 · 0 + 6 · \frac{1}{3}

(b) Compute the expected value of the number rolled on a fair, six-sided die, given that the outcome is odd.

Solution: Define R and E as before.

E [R | \overline{E}] = ∑_{x=1}^{6} x · Pr \{R = x | \overline{E}\}
= 1 · \frac{1}{3} + 2 · 0 + 3 · \frac{1}{3} + 4 · 0 + 5 · \frac{1}{3} + 6 · 0
= 3

(c) Prove the following identity, assuming that all expectations exist.

E [R] = Pr \{E\} · E [R | E] + Pr \{\overline{E}\} · E [R | \overline{E}]

Solution: We transform the right side into the left side. All summations are over x ∈ Range(R).

Pr \{E\} · E [R | E] + Pr \{\overline{E}\} · E [R | \overline{E}]

= Pr \{E\} · (∑_{x} x · Pr \{R = x | E\}) + Pr \{\overline{E}\} · (∑_{x} x · Pr \{R = x | \overline{E}\})

= Pr \{E\} · (∑_{x} x · \begin{matrix}Pr & \{[R = x] ∩ E\} \\ Pr & \{E\} \end{matrix}) + Pr \{\overline{E}\} · (∑_{x} x · \begin{matrix}Pr & \{[R = x] ∩ \overline{E}\} \\ Pr & \{\overline{E}\} \end{matrix})
= ∑_{x} x · (Pr \{[R = x] ∩ E\} + Pr \{[R = x] ∩ \overline{E}\})
= ∑_{x} x · (Pr \{([R = x] ∩ E) ∪ ([R = x] ∩ \overline{E})\})
= ∑_{x} x · Pr {R = x}
= E [R]

The first step uses the definition of conditional expectation. The second step uses the definition of conditional probability. The third step is simplification. The fourth step uses the fact that the probability of a disjoint union of events is equal to the sum of the event probabilities. The fifth step is simplification, and the final step uses the definition of expected value.

Problem 8. (15 points) Each bag of Doritos contains a cool sticker. There are n different kinds of sticker, and I want to collect at least one sticker of each kind. (Assume that sticker kinds in Dorito bags are uniformly random and mutually independent.)

(a) Suppose that I have already collected k kinds of sticker. What is the expected number of additional bags of Doritos that I must eat to collect one additional kind of sticker?

Solution: The probability that I must eat i or more bags is:

E [number of bags to get new kind]

= ∑_{i=0}^{∞} Pr {number of bags to get new kind > i}

= ∑_{i=0}^{∞} Pr {number of old kinds in first i bags}

= ∑_{i=0}^{∞} (\frac{k}{n})^{i}
= \frac{n}{n − k}

(b) What is the expected number of bags of Doritos that I must eat to collect at least one sticker of each kind?

Solution: We sum the expected number of bags to get the first kind, the expected number to get the second kind, and so forth.

E [number of bags to get all kinds]

= ∑_{k=0}^{n−1} \frac{n}{n − k} = n · ∑_{k=0}^{n−1} \frac{1}{n − k}

= n · ∑_{j=1}^{n} \frac{1}{j} = nH_{n}.