Massachusetts Institute of Technology Handout 79 6.042J/18.062J: Mathematics for Computer Science December 4, 1999 (corrected 12/14) Professors Albert R. Meyer and Shafi Goldwasser

Problem Set 12 Solutions

Reading assignment: F97 Lecture Notes 22, 23 (skipping Wald’s Theorem), 24, and H72 notes on expectation.

Problem 1. Eight men and seven women, all single, happen randomly to have purchased single seats in the same 15-seat row of a theater.

(a) What is the probability that the first two seats contain a marriageable couple, i.e., a single man next to a single woman?

Solution: Here’s one way to do it. There are \binom{15}{2} = 105 possible pairs that could occupy the first two seats, but only 8 · 7 = 56 of them are marriageable couples. So the probability is 56/105 = 8/15. endsoln

(b) What is the expected number of pairs of adjacent seats which contain marriageable couples? (For example, if the sequence of men and women in the seats is

MMMWMMMMWWWWWWM,

then there are four possible couples sitting in the pairs of adjacent seats that start at the 3rd, 4th, 7th and 14th seats, respectively.)

Solution: Let the random variable S be the number of pairs of seats containing a marriageble couple; we want to find E [S]. We can solve this problem by introducing an indicator random variable S_{i}, where S_{i} = 1 if there is a marriageable couple in seats i and i + 1, and S_{i} = 0 otherwise. So we have S = ∑_{i=1}^{14} S_{i}. Since each seat is like any other, the probability that seats i and i+1 contain a marriageable couple is the same as in the first part, 8/15. Thus

E [S_{i}] = 1 · Pr(S_{i} = 1) + 0 · Pr(S_{i} = 0) = \frac{8}{15}.

Finally, because expectation is linear,

E [S] = ∑_{i=1}^{14} E [S_{i}] = 14 · \frac{8}{15}.

Note that this approach works despite the fact that the indicator random variables S_{i} are not independent. That’s the beauty of linearity of expectation! endsoln Problem 2. There are n MIT students who are taking 6.042 and 6.003 this term. To make it easier on themselves, the professors in charge of these classes have decided to randomly permute their class lists and then assign students grades based on their rank in the permutation^{1}. Assume all permutations are equally likely and that the ranking in each class is independent of the other.

(a) What is the expected number of students that have a higher rank in 6.042 than 6.003? Solution: Let X_{i} be random variable whose value is 1 if student i has higher rank in 6.042 than 6.003 and 0 otherwise. If student i has rank of r for 6.042 than the probability that student i has higher rank on 6.042, given that the student has rank r in 6.042, is (r − 1)/n. The probability student i has rank r in 6.042 is 1/n. Thus, the probability that student i has higher rank in 6.042 is

∑_{1≤r≤n} \frac{1}{n} \frac{r − 1}{n} = \frac{n − 1}{2n}.

By linearity of expectation, the expected number of students with a higher rank on 6.042 is

E [x] = E [x_{1}] + E [x_{2}] + ... + E [x_{n}] = \frac{n − 1}{2}.

Another way to solve this problem is to observe that students with higher rank in one class have lower rank in the other class, so by symmetry, the expected number of higher- and lower-ranked students in either class is the same. The expected number of students with the same rank equals 1 by linearity of expectation, since probability student ranked the same in both schools is 1/n. These observations now yield same answer as above. endsoln

(b) What is the expected number of students that have a ranking at least k higher in 6.042 than in 6.003? Solution: This part can be done in the same way as the previous one. Let X_{i} be the random variable whose value is 1 if student i is ranked at least k higher in 6.042 than 6.003 and 0 otherwise. If student i has rank of r (r > k) for 6.042 than the probability that student i has at least k higher rank in 6.042 given student ranked r in 6.042 is (r − k)/n. The probability student i has rank r in 6.042 is 1/n. Thus, the probability that student i has at least k higher rank in 6.042 is

∑_{k+1≤r≤n} \frac{1}{n} \frac{r − k}{n} = \frac{(n − k)(n − k + 1)}{2n^{2}}.

By linearity of expectation, the expected number of students with a higher rank on 6.042 is

E [x] = E [x_{1}] + E [x_{2}] + ... + E [x_{n}] = \frac{(n − k)(n − k + 1)}{2n}.

endsoln Problem 3. Ben Bitdiddle is asked to analyze a game in which a fair coin is tossed until the first time a head turns up. If this head occurs on the nth toss, and n is odd, then he wins $2^{n}/n, but if n is even, he loses $2^{n}/n. Ben observes that the expected dollar win from this game is the value of the series:

1 … just as many students have suspected :-)

(1/2) · 2 − (1/4) · 2 + (1/8) · 8/3 + ⋯ ± (1/2^{n}) · 2^{n}/n = 1 − 1/2 + 1/3 − 1/4 + ⋯ ± 1/n.

This is the alternating harmonic series—a series whihc is known to converge to a definite real number r > 0. Ben concludes that since r > 0, it’s to his advantage to play this game. As usual, Ben’s shoot-from-the-hip analysis is off the mark. Explain.

Solution:

This series is convergent, but not absolutely convergent. The definition of expectation requires absolute convergence, so the expectation in this case is not defined. The fact that the expectation is undefined is no mere formality. The number r is not relevant to the behavior of the game. Indeed, we showed in a tutorial problem that by reordering its terms, the series can be made to converge to any real value or diverge to ±∞.

endsoln

Problem 4. In the Monte Carlo version of roulette there is only one green slot—which is numbered 0—as opposed to the Las Vegas version, which has 2 green slots numbered 0 and 00. If you bet on red (or, symmetrically, on black) and 0 comes up, one or more of these three options may be offered:

(a) You get 1/2 of your bet back, and the casino gets the other half.

(b) Your bet is put “in prison.” If red comes up on the next turn, you get your bet back (but don’t win any money). If black or 0 comes up, you lose your bet.

(c) Your bet is put in prison as before. If red comes up on the next turn, you get your bet back, and if black comes up on the next turn, then you lose your bet. If a 0 comes up on the next turn, then your bet is put into “double prison.” If your bet is in double prison, and if red comes up on the next turn, then your bet is moved back to ordinary prison and the game proceeds as before. If your bet is in double prison, and if black or 0 come up on the next turn, then you lose your bet.

Note that all three of these options are better than Las Vegas roulette, in which you simply lose your entire bet if 0 or 00 comes up. But it is not clear which is the best choice. Find the expectation of a one dollar bet on red under each option. Which is best?

Solution:

Under option (a), if red turns up you win 1 dollar, if black turns up you lose one dollar, and if 0 turns up, you lose 1/2 dollar. Thus, the expected winnings are

1(\frac{18}{37}) + (−1)\frac{18}{37} + (\frac{−1}{2})(\frac{1}{37}) ≈ −0.0135.

Under option (b), if red turns up you win 1 dollar, if black turns up, you lose 1 dollar, and if 0 followed by black or 0 turns up, you lose 1 dollar. Thus the expected winnings are

1(\frac{18}{37}) + (−1)(\frac{18}{37}) + (−1)(\frac{1}{37})(\frac{19}{37}) ≈ −0.0139.

Under option (c), it is a bit more complicated. Let x be the probability that you lose your money given that it is in prsion, and let y be the probability that you lose given that your money is in double prison. Then

x = \frac{18}{37} + \frac{1}{37}y.

Also,

y = \frac{19}{37} + \frac{18}{37}x.

So, we have

x = \frac{18}{37} + \frac{1}{37}(\frac{19}{37} + \frac{18}{37}x).

Solving, we have that x = 685/1351. Thus, starting from the beginning, the probability that you lose your bet is

\frac{18}{37} + \frac{1}{37}x = \frac{25003}{49987}.

Now, the only way you can win is if red comes up on the first turn, which happens with probability 18/37. Thus the expected winnings are

1 · \frac{18}{37} − 1 · \frac{25003}{49987} = −\frac{685}{49987} ≈ −0.0137.

Thus, the simple option (a) is actually the best.

endsoln

Problem 5. Three hundred students take the 6.042 final exam. The mean on the exam is 90 and the lowest score was 30. You have no other information about the students and the exam, e.g., you should not assume that the final is worth 100 points.

(a) State a best possible upper bound on the number of students who scored at least 180. Hint: Markov.

Solution: Let R be the score. Apply Markov’s Bound to R − 30:

Pr {R ≥ 180} = Pr {R − 30 ≥ 150} ≤ E [R − 30] /150 = 60/150 = 2/5,

so at most (2/5)300 = 120 students score ≥ 180. endsoln (b) Give an example set of scores which achieve your bound.

Solution: Of the 300 students, 120 score 180 and 180 score 30. The mean is

(120 · 180 + 180 · 30)/300 = 90,

as required. endsoln

Problem 6. Suppose you are playing the game “Hearts” with three of your friends. In Hearts, all the cards are dealt to the players, in this case the four of you will each have 13 cards.

(a) What is the expectation and variance of the number of hearts that you will have in your hand?

Solution: Let H be the number of hearts in your hand, and let X_{i} be the indicator variable that is 1 if card i is a heart and is 0 otherwise, so H = ∑_{1≤i≤13} X_{i}. Because X_{i} is an indicator variable, its expectation is the probability that card i is a heart, namely, 1/4. So

E [H] = ∑_{1}^{13} 1/4 = 13/4.

To compute variance, we use the definition:

Var [∑_{i=1}^{13} X_{i}] = E [(∑_{i=1}^{13} X_{i})^{2}] − E [∑_{i=1}^{13} X_{i}]^{2}

= E [(∑_{i=1}^{13} X_{i})^{2}] − (13/4)^{2}
= E[X_{1}^{2} + X_{1}X_{2} + X_{1}X_{3} + … + X_{1}X_{13} +
X_{2}X_{1} + X_{2}^{2} + X_{2}X_{3} + … + X_{2}X_{13} +
⋮
X_{13}X_{1} + X_{13}X_{2} + … + X_{13}^{2}] − (13/4)^{2}
= E [X_{1}^{2}] + E [X_{1}X_{2}] + E [X_{1}X_{3}] + … + E [X_{1}X_{13}] +
E [X_{2}X_{1}] + E [X_{2}^{2}] + E [X_{2}X_{3}] + … + E [X_{2}X_{13}] +
⋮
E [X_{13}X_{1}] + E [X_{13}X_{2}] + … + E [X_{13}^{2}] − (13/4)^{2}.

Now we note that E [X_{i}^{2}] = E [X_{i}] since X_{i} is an indicator variable, so E [X_{i}^{2}] = 1/4. Also, when i ≠ j, X_{i}X_{j} = 1 if cards i and j are both hearts, and 0 otherwise. The probability that both cards are hearts is (1/4)(12/51), and thus E [X_{i}X_{j}] = (1/4)(12/51) = 3/51. In the summation above, there are 13 E [X_{i}^{2}] terms, and 2\binom{13}{2} = 156 terms of the form E [X_{i}X_{j}]. Thus,

Var [∑_{i=1}^{13} X_{i}] = 13 · \frac{1}{4} + 156 · \frac{3}{51} − (\frac{13}{4})^{2}
≈ 1.863970588.

endsoln

(b) What is the expectation and variance of the number of suits in your hand?

Solution: Similar to the first part: let N denote the number of suits in a hand. Let X_{s} be the indicator variable which is 1 if there is a spade in the hand and 0 otherwise. Define X_{h}, X_{d}, X_{c} analogously for the three remaining suits: hearts, diamonds, and clubs. Then N = X_{s} + X_{h} + X_{d} + X_{c}. The expectation of each of the indicator variables is the probability that a hand contains the corresponding suit. Thus, for i ∈ {s, h, d, c}

E [X_{i}] = 1 − \begin{matrix}( & {52−13 \atop 13} & ) \\ ( & {52 \atop 13} & ) \end{matrix} = 0.987209,

because \binom{52−13}{13} is the number of hands that are missing the particular suit, and \binom{52}{13} is the total number of hands.

E [N] = E [X_{s} + X_{h} + X_{d} + X_{c}] = E [X_{s}] + E [X_{h}] + E [X_{d}] + E [X_{c}] = 4 · 0.987209 = 3.94884.

To compute variance:

Var [N] = Pr {N = 1} (1 − E [N])^{2} + Pr {N = 2} (2 − E [N])^{2} +
Pr {N = 3} (3 − E [N])^{2} + Pr {N = 4} (4 − E [N])^{2}.

Now we must calculate each of the probabilities. First,

Pr \{N = 1\} = \frac{4}{\binom{52}{13}} = 6.299 × 10^{−12},

because there are four possible hands of all one suit out of \binom{52}{13} possible hands of 13 cards.

Pr \{N = 2\} = \frac{\binom{4}{2}[\binom{26}{13} − 2]}{\binom{52}{13}} = 9.827 × 10^{−5},

because there are \binom{4}{2} ways to choose which two suits. There are \binom{26}{13} ways to choose 13 cards from the 26 possible cards of those two suits. Two of those \binom{26}{13} hands actually contain only one suit. Thus \binom{4}{2}(\binom{26}{13} − 2) is the number of hands with two suits.

Pr \{N = 3\} = \frac{\binom{4}{3}[\binom{39}{13} − \binom{3}{2}\binom{26}{13} + 3]}{\binom{52}{13}} = 0.05097,

because there are \binom{4}{3} ways to choose the three suits. There are \binom{39}{13} ways to choose 13 cards from the 39 cards of those three suits. But that also includes hands with two suits and one suit. So, using Inclusion-Exclusion, we subtract the \binom{3}{2}\binom{26}{13} ways to choose two suits from the three suits and then choose choose 13 cards from the 26 cards of those suits. Next, we add back the three ways to choose hands of one suit among the three. Finally, we divide by the \binom{52}{13} ways to choose a possible hand of 13. Of course,

Pr {N = 4} = 1 − (Pr {N = 1} + Pr {N = 2} + Pr {N = 3}) = 0.9489.

This allows us to complete the calculation of the variance:

Var [N] = 0.04874.

endsoln

Problem 7. Suppose that n people have their hats returned at random. Let X_{i} = 1 if the ith person gets his or her own hat back and 0 otherwise. Let S_{n} = ∑_{i=1}^{n} X_{i}, so S_{n} is the total number of people who get their own hat back. Show that

(a) E [X_{i}^{2}] = 1/n. Solution: X_{i} = 1 with probability 1/n and 0 otherwise. Thus X_{i}^{2} = 1 with probability 1/n and 0 otherwise. So E [X_{i}^{2}] = 1/n. endsoln

(b) E [X_{i}X_{j}] = 1/n(n − 1) for i ≠ j. Solution: The probability that X_{i} and X_{j} are both 1 is 1/n · 1/(n − 1) = 1/n(n − 1). Thus X_{i}X_{j} = 1 with probability 1/n(n − 1), and is zero otherwise. So E [X_{i}X_{j}] = 1/n(n − 1). endsoln

(c) E [S_{n}^{2}] = 2. Hint: Use (a) and (b). Solution:

E [S_{n}^{2}] = ∑_{i} E [X_{i}^{2}] + ∑_{i} ∑_{j≠i} E [X_{i}X_{j}]

= n · \frac{1}{n} + n(n − 1) · \frac{1}{n(n − 1)}
= 2.

endsoln (d) Var [S_{n}] = 1.

Solution:

Var [S_{n}] = E [S_{n}^{2}] − E^{2} [S_{n}]
= 2 − (n(1/n))^{2}
= 2 − 1
= 1.

endsoln

(e) Using Chebyshev’s Inequality, show that Pr {S_{n} ≥ 11} ≤ .01 for any n ≥ 11.

Solution:

Pr {S_{n} ≥ 11} = Pr {S_{n} − E [S_{n}] ≥ 11 − E [S_{n}]}
= Pr {S_{n} − E [S_{n}] ≥ 10}
≤ \frac{Var [S_{n}]}{10^{2}} = .01

Note that the X_{i}’s are Bernoulli variables but are not independent, so S_{n} does not have a Bernoulli distribution and the Bernoulli estimates from Lecture Notes 21 do not apply. endsoln

Problem 8. Psychological diagnosis of sociopaths is notoriously unreliable. For example, a random psychologist is as likely to diagnose a normal patient as sociopathic as he is to recognize that the patient is normal. A random psychologist is actually slightly less likely to correctly diagnose a real sociopath than not—sociopaths are really good liars.

(a) In these circumstances it might seem there was no reliable way to diagnose sociopaths, but in theory there is a way—if we have a large enough population of psychologists who reach their judgements independently. Explain how to obtain a reliable diagnosis in this case. Briefly explain why your method will be reliable, citing appropriate results from class. A qualitative answer is all that’s required—you need not come up with any numerical estimates or growth rates.

Solution: Get a reliable test by repeatedly asking randomly chosen psychologists to do the diagnosis and computing the fraction, f, of “normal” diagnoses. Let s > 1/2 be the probability of a “normal” diagnosis on a sociopathic patient. Diagnose normal if f is closer to 1/2 than to s. By diagnosing independently enough times, there is small probability that f differs from the expected value of a diagnosis by very much (the expected value is either 1/2 or s depending on whether or not the patient is normal—we don’t know which). By the Law of Large Numbers, by Chebyshev’s bound, or by the estimation of the binomial distribution as used in the Gallup Poll example in Lecture Notes, if we diagnose enough times, we can make this probability as small as desired, so the probability of a correct diagnosis can be as close to 1 as desired. endsoln

(b) Is it plausible to assume that psychologists will make their diagnoses independently? Briefly explain. Solution: Not really. It figures that some sociopaths would be particularly good liars and be able to fool most psychologists. Conversely, there figure to be normal people whose anxious or defensive manner makes a sociopathic diagnosis by many psychologists more likely. Also, there may be some specially expert psychologists whose diagnoses are more reliable than average; this implies if one expert diagnoses “normal,” the diagnosis is likely to be correct, making it more likely that another expert will also correctly diagnose “normal,” so their diagnoses will not be independent of each other. endsoln

Problem 9. We have two coins: one is a fair coin and the other is a coin that produces heads with probability 3/4. One of the two coins is picked, and this coin is tossed n times.

(a) Does the Weak Law of Large Numbers allow us to predict what limit, if any, is approached by the expected proportion of heads that turn up as n approaches infinity? Briefly explain. Solution: There is no way to predict the proportion of heads in the long run, since this will depend upon which of the two coins is picked, and we have no information about which coin is picked or how it is picked. So while the Law of Large Numbers implies that the proportion of heads will, with probability appraoching one, be near either 1/2 or 3/4, it does not, and cannot, say anything about which of these numbers is the expected limit. endsoln

(b) How many tosses suffice to make us 95% confident which coin was chosen? Explain. Solution: To be 95 percent sure which coin was picked, bet that the fair coin was chosen if the proportion of heads is less than the average of 1/2 and 3/4, namely 5/8; otherwise bet that the biased coin was chosen. You will win the bet if the proportion of heads does not deviate from the probability of heads by more than 1/8. A quick calculation using Chebyshev’s bound and the fact that the variance of a Bernoulli variable is at most 1/4, implies that the probability of a deviation this large is at most 1/(4n(1/8)^{2}). This will be less than or equal to .05 if n > 320. In this problem, the number of heads in n flips will be a Bernoulli distribution, and the estimates from Lecture Notes 21 could also be applied to yield a tighter bound: n > 42. endsoln