Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science April 20, 2000 Professors David Karger and Nancy Lynch

Problem Set 8 Solutions

Problems:

Problem 1 Suppose the game Let’s Make A Deal is changed slightly. Instead of having 3 doors with 1 grand prize, in the new game there are 4 doors with 2 grand prizes. The rule of the game remains the same. Therefore the game now becomes:

At one stage of the game, a contestant is shown 4 doors. The contestant knows that there are 2 grand prizes behind 2 of the doors and that there are goats behind the 2 other doors. At the beginning, the contestant picks a door. To build suspense, the assistant of the game then opens a different door, revealing a goat. The contestant can then stick with his original door or switch to another unopened door. He wins a prize only if he now picks the door with the prize.

In the new game, what is the probability of winning with the “stick” strategy? How about the “switch” strategy? Can you explain why the two probabilities do not sum up to 1? Solution. The player wins with a “stick” strategy iff he chooses the “correct door” in the first place. Therefore the probability of winning with the “stick” strategy is \frac{1}{2}. To calculate the probability of winning with a “switch” strategy, let E_{1} be the event that “the player chooses the correct door at his first chance”. Let E_{2} be the event that “the player switches to the correct door at his second chance”.

P (winning with “switch” strategy) = P (E_{2}|E_{1})P (E_{1}) + P (E_{2}|\overline{E_{1}})P (\overline{E_{1}})
= \frac{1}{2} · \frac{1}{2} + 1 · \frac{1}{2}
= \frac{3}{4}

The two probabilities do not need to sum up to 1. They are calculated in a different probability space. In particular, the player winning by the “switch” strategy does not imply he will lose by the “stick” strategy, and vice versa. Therefore, the same winning event can be counted in both cases at the same time.

Problem 2 In a lottery, 6 distinct integers are drawn randomly from 1 to 45 without replacement.

(a) What is the probability that the first of the 6 numbers is at most k, where 1 ≤ k ≤ 45?

(b) What is the probability that the maximum of the 6 numbers is k, where 1 ≤ k ≤ 45? Solution. Solution.

Problem 3 There are three prisoners, A, B, and C. The parole board will release two of the prisoners, but has not yet announced which two. The pair to be released is selected by the board uniformly at random; that is, each of the three pairs of prisoners has a \frac{1}{3} probability of being chosen. Prisoner A figures that he will be released with probability \frac{2}{3}. A guard offers to tell prisoner A the name of one of the other prisoners who will be released (either B or C). However, prisoner A declines the offer. He reasons that if the guard says, for example, “B will be released”, then his own probability of release will drop to \frac{1}{2}. This is because he will then know that either he or C will be released, and these two events are equally likely. Either prove that prisoner A has reasoned correctly or prove that he is wrong. Assume that if the guard has a choice of saying either B or C, because both are to be released, then he picks one at random with equal probability for each. Solution. Prisoner A is wrong. He is conditioning on the event that prisoner B is to be released and not on the event that the guard says prisoner B is to be released. A correct calculation is given below.

Pr(A is released | guard says B) = \frac{Pr(A is released ∩ guard says B)}{Pr(guard says B)}
= \frac{Pr(A and B are released)}{Pr(guard says B)}
= \frac{\frac{1}{3}}{\frac{1}{2}}
= \frac{2}{3}

Thus, the probability that prisoner A will be released is not changed by what the guard tells him.

Problem 4 What is the probability that a random poker hand contains cards from at most two suits? Solution. The sample space consists of the \binom{52}{5} possible hands. Each hand is equally likely and comes up with probability 1/\binom{52}{5}. Therefore, the probability that a hand contains at most two suits is equal to the number of different hands of this type multiplied by 1/\binom{52}{5}. All that remains is to count the number of poker hands with at most two suits. There are \binom{4}{2} ways to choose two suits and \binom{26}{5} ways to choose five cards from these two suits. However, this triple-counts hands containing cards from a single suit. (For example, a hand with all spades is counted once as a spades-hearts hand, a second time as a spades-clubs hand, and a third time as a spades-diamonds hand.) The number of hands with a single suit is 4 · \binom{13}{5}. Therefore, the number of hands with at most two suits is

Problem 5

(a) You roll two dice. What is the probability that their sum is not 6?

(b) You roll three dice. What is the probability that at least one of the pairwise sums is something other than 6?

Problem 6 We know from statistics that when a policeman gets shot he/she survives with probability 0.8 if he/she wears a bullet-proof vest and survives with probability 0.12 if the policeman doesn’t wear a vest. Given that 15% of the policemen wear bullet-proof vests, what is the probability that a random policeman was wearing a bullet-proof vest if he/she survived a firearm attack?

Problem 7 A biased coin has probability p of heads and probability 1 − p of tails. Suppose we flip this coin n times.

(a) What is the probability of getting exactly k heads?

(b) For what values of k is the probability of getting exactly k heads greater than the probability of getting exactly k − 1 heads? For what values of k is it less? What value of k is the most likely number of heads?

(c) Show that if p = 1/n then the probability of getting no heads is ∼ 1/e (for large n). What is the ratio of the probability of no heads to the probability of exactly one head?

Problem 8

(a) Prove that P r(\overline{A}|C) = 1 − P r(A|C) for any events A and C.

(b) Is it possible for P r(A|B) and P r(A|C) to be very small, if P r(A|B ∩ C) is large? Give a counterexample or a proof to justify your answer.