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

Problem Set 9 Solutions

Problem 1. (10 points) Suppose that you are the contestant on a variant of Lets Make a Deal where the keys to a new Corvette are behind one door, tickets for a dream vacation are behind a second door, and there is a diminutive, stuffed pig behind a third door. You do not know which door conceals which prize. Your objective is to maximize your probability of winning the pig.

As before, you pick a door initially. Carol then opens a different door. Specifically, if you picked the door concealing the pig or the keys, then she reveals the tickets. If you picked the door concealing the tickets, then she reveals the keys. You can then either stay with your original door or switch to the remaining, closed door. You are awarded the prize behind the door that you choose at this second stage.

In substance, this variant differs from the original in that you know Carol’s door-opening rules. This may give you a slight edge. Give a strategy that maximizes your probability of winning the pig and prove that no better strategy exists.

Let p be the probability that you switch if you are shown the tickets, and let q be the probability that you switch if you are shown the keys. The tree diagram below illustrates the various cases.

Your probability of winning is therefore

\frac{p}{3} + \frac{q}{3} + \frac{1 − p}{3} = \frac{1}{3} + \frac{q}{3}.

This expression achieves its maximum value of \frac{2}{3} when q = 1. This means that in an optimal strategy, you always switch if you are shown the keys. Your action when you are shown the tickets does not affect your chance of winning.

Problem 2. (10 points) In each problem part, either define a probability space and events A, B, and C such that all the equations hold simultaneously, or else prove that no such probability space and events exist.

(a)

Pr(A | B) = \frac{1}{4}
Pr(A | C) = \frac{1}{4}
Pr(A | B ∩ C) = \frac{3}{4}

These events can exist, as indicated in the diagram below. Empty regions have zero probability.

(b)

Pr(A | B) = \frac{3}{4}
Pr(A | C) = \frac{3}{4}
Pr(A | B ∩ C) = \frac{1}{4}

These events can exist, as indicated in the diagram below.

(c)

Pr(A | B) = \frac{3}{4}
Pr(A | C) = \frac{3}{4}
Pr(A | B ∪ C) = \frac{1}{4}

These events can not exist. At least one of the events B or C must be at least half as likely as B ∪ C. Without loss of generality, assume that this is true for event B; that is,

\frac{Pr(B)}{Pr(B ∪ C)} ≥ \frac{1}{2}.

The first equation implies that

\frac{Pr(A ∩ B)}{Pr(B)} = \frac{3}{4}.

Multiplying the equation and the inequality above gives

\frac{Pr(A ∩ B)}{Pr(B ∪ C)} ≥ \frac{3}{8}.

Note that the set A∩(B∪C) contains the set A∩B. Therefore, Pr(A∩(B∪C)) ≥ Pr(A ∩ B). Substituting this fact into the preceding inequality gives

\frac{Pr(A ∩ (B ∪ C))}{Pr(B ∪ C)} ≥ \frac{3}{8}.

Consequently, Pr(A | B ∪ C) ≥ \frac{3}{8} > \frac{1}{4}, contradicting the third equation.

Problem 3. (10 points) Suppose that I pick a pair of distinct numbers in the range 1 to 10 uniformly at random.

(a) If one of the numbers is even, then what is the probability that the other number is even?

The sample space consists of the \binom{10}{2} = 45 pairs of distinct numbers in the range 1 to 10. Since the sample space is uniform, each outcome has probability \frac{1}{45}. With this observation, we can compute the probability of an event by counting the number of outcomes in the event and then multiplying by \frac{1}{45}. Let E be the event that at least one number is even, and let B be the event that both numbers are even. We must compute

Pr(B | E) = \frac{Pr(B ∩ E)}{Pr(E)}
= \frac{Pr(B)}{Pr(E)}

The second equality holds because B is contained in E; that is, if both number are even, then at least one of the numbers is even. Since there are 5 even numbers in the range 1 to 10, the event B contains \binom{5}{2} = 10 outcomes and thus has probability 10 · \frac{1}{45} = \frac{2}{9}. The event E consists of all pairs of numbers in the range 1 to 10 that are not both odd. That is, event E contains 45 − \binom{5}{2} = 35 outcomes, and thus has probability 35 · \frac{1}{45} = \frac{7}{9}. Substituting these probabilities into the above equation gives

Pr(B | E) = \frac{Pr(B)}{Pr(E)}
= \frac{\frac{2}{9}}{\frac{7}{9}}
= \frac{2}{7}.

(b) If one of the numbers is a 2, then what is the probability that the other number is even?

Let T be the event that one number is 2, and let U be the event that one number is 2 and the other is even. We must compute

Pr(U | T) = \frac{Pr(U ∩ T)}{Pr(T)}
= \frac{Pr(U)}{Pr(T)}

The event T consists of 9 outcomes, since every pair must contain 2 and there are 9 choices for the other number (1, 3, 4, …, 10). The event U consists of 4 outcomes, since every pair must contain a 2 and there are 4 choices for the other number (4, 6, 8, 10). Therefore, we have:

Pr(U | T) = \frac{Pr(U)}{Pr(T)}
= \frac{\frac{4}{45}}{\frac{9}{45}}
= \frac{4}{9}.

Problem 4. (10 points) Three gunfighters, A, B, and C, plan to fight a three-cornered pistol duel. They all know that A’s chance of hitting his target is 0.3, B never misses, and C’s chance of hitting is 0.5. They will shoot one at a time in the sequence ABCABC . . .. On his turn, a gunfighter may target either of the other two, or may fire harmlessly into the air. Assume that each gunfighter uses the shooting strategy that maximizes his probability of being the only one left standing. What should gunfighter A do on his first shot and what probability of survival does this give him?

Suppose that A shoots into the air. Then B shoots C, and A gets one shot to kill B before he himself is killed. Therefore A has a 0.3 chance of survival.

Suppose that A shoots at B. If he hits, then he enters a duel with C, where C gets the first shot. In this case, let p be the probability that he wins the duel. For this to happen, either C must miss and A must hit (probability 0.5 · 0.3) or else C must miss, A must miss, and then A must win a duel of the same type as before (probability 0.5 · 0.7 · p). As an equation:

p = 0.5 · 0.3 + 0.5 · 0.7 · p
= \frac{3}{13}

Thus, If A hits B, then his odds of survival are lower than if he fires into the air. On the other hand, suppose that A shoots at C. If he hits, then B immediately kills him.

Therefore, A’s best strategy is to fire into the air. This gives him a 0.3 chance of survival.

Problem 5. (10 points) After their arrest and sentencing for unlawful use of firearms, and short hospital stays, the three gunfighters, A, B, and C applied for parole. The parole board decided to release two of the three, chosen uniformly at random, but has not released their names. Gunfighter A figures that he will be released with probability \frac{2}{3}. A guard offers to tell gunfighter A the name of one of the other gunfighters who will be released (either B or C). However, gunfighter 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 also be released, but these events are equally likely. Either prove that gunfighter A has reasoned correctly or prove that he is wrong. Assume that if the guard has a choice of saying B or C because both are to be released, then he picks one uniformly at random.

Gunfighter A has reasoned incorrectly. We must compute

Pr(A released | guard says “B”) = \frac{Pr(A released and guard says “B”)}{Pr(guard says “B”)}.

These probabilities are worked out in the tree diagram below.

Plugging these probabilities into the preceding equation gives

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

If the guard says that B will be released, then A still has a \frac{2}{3} chance of release.

Problem 6. (10 points) Suppose that Let’s Make a Deal is modified so that there are four doors. As before, a prize is hidden behind one door. The contestant picks a door, Carol opens a different door to reveal no prize, and then the contestant is allowed to stay with his or her original door or to pick one of the other two that are still closed. If the contestant chooses the door concealing the prize in this second stage, then he or she wins it.

(a) Contestant Stu, a sanitation engineer from Trenton, New Jersey, stays with his original door. What is the probability that he wins the prize?

Stu guesses the right door initially with probability \frac{1}{4} and guesses the wrong door with probability \frac{3}{4}. If he was right initially, then he surely wins the prize. If he was wrong initially, then he surely does not win the prize. Therefore, his probability of winning is \frac{1}{4} · 1 + \frac{3}{4} · 0 = \frac{1}{4}.

(b) Contestant Zelda, an alien abduction researcher from Helena, Montana, randomly picks one of the other two doors with equal probability. What is the probability that she wins the prize?

Zelda also guesses the right door initially with probability \frac{1}{4} and guesses the wrong door with probability \frac{3}{4}. If she was right initially, then she can not win. If she was wrong initially, then she wins with probability \frac{1}{2}. Therefore, her probability of winning is \frac{1}{4} · 0 + \frac{3}{4} · \frac{1}{2} = \frac{3}{8}.

Problem 7. (10 points) Even if he is very, very careful, the probability that Theory Pig can avoid “provoking” 6.042 TA Brian Dean is only a small, positive constant ϵ. If Theory Pig does “provoke” Brian, then the probability that Brian will refrain from doing something really wicked to our porky pal is only a small, positive constant δ.

(a) Compute a tight lower bound on the probability that Brian does something really wicked to Theory Pig.

Let P be the event that Theory Pig provokes Brian. Let W be the event that Brian does something wicked to Theory Pig. From the problem statement, we have:

Pr(P) = 1 − ϵ
Pr(W | P) = 1 − δ

We can now reason as follows:

Pr(W) ≥ Pr(W ∩ P)
= Pr(W | P) · Pr(P)
= (1 − δ) · (1 − ϵ)

The first step uses a fact that the event W ∩ P is a subset of the event W. The second step uses the definition of conditional probability, and the final step is substitution.

(b) Prove that your lower bound is tight; that is, describe circumstances consistent with the problem statement such that the probability that Brian does something wicked to Theory Pig is equal to your lower bound.

Suppose that Brian never does something really wicked unless he is provoked. That is, the event W is contained in the event P. Then W = W ∩ P, and the only inequality in the solution to the previous problem part is an equality.

Problem 8. (15 points) Each morning Theory Pig pops out of his desk drawer home— all bright and perky— and goes bounding off to play around the Laboratory for Computer Science. The desk drawer is located at position (0, 0). At each time step, Theory Pig is equally likely to bound north or east. A northward bound increments the first coordinate of his position, and an eastward bound increments the second coordinate of his position. (Assume that his direction at one time step is independent of his direction at all other time steps.)

At position (4, 4), 6.042 TA Brian Dean is waiting with a bat, for some reason. What is the probability that Theory Pig visits position (4, 4) within his first 10 bounds?

There are 2^{10} equally likely routes for Theory Pig. He visits position (4, 4) if 4 of his first 8 bounds are north, 4 of his first 8 bounds are east, and his remaining two bounds are in any direction. Therefore, Theory Pig visits (4, 4) in

\binom{8}{4} · 2^{2} = 280

of these outcomes. Therefore, the probability that Theory Pig visits position (4, 4) within his first 10 bounds is

\frac{280}{2^{10}} = \frac{35}{128}.

Problem 9. (15 points) Suppose that you roll three six-sided dice.

(a) What is the probability that the sum of the first two rolls is 7?

There are 36 equally-likely outcomes for the first two rolls. In 6 of these outcomes, the sum of the rolls is 7. Therefore, the probability is \frac{6}{36} = \frac{1}{6}.

(b) What is the probability that the sum of the first two rolls is 7 and the sum of the last two rolls is 7?

There are 6^{3} = 216 equally-likely outcomes for all three rolls. In 6 of these outcomes, the sum of the first two rolls is 7 and the third is equal to the first. Therefore, the probability is \frac{6}{216} = \frac{1}{36}.

(c) What is the probability that every pair of rolls sums up to 7?

The probability is zero. Assume that there were a set of rolls such that every pair summed to 7. Since the first rolls sum to 7, one of these rolls must be odd and the other even. As a result, the third roll can always be paired with one of the same parity to give an even sum.

(d) What is the probability that some pair of rolls sums up to 7?

Let A be the event that the first two rolls sum up to 7, B be the event that the last two rolls sum to 7, and C be the event that the first and last rolls sum to 7. The probability that some pair of rolls sums up to 7 is Pr(A ∪ B ∪ C). We can evaluate this quantity with inclusion exclusion:

Pr(A ∪ B ∪ C) = Pr(A) + Pr(B) + Pr(C)
− Pr(A ∩ B) − Pr(A ∩ C) − Pr(B ∩ C)
+ Pr(A ∩ B ∩ C)
= \frac{1}{6} + \frac{1}{6} + \frac{1}{6} − \frac{1}{36} − \frac{1}{36} − \frac{1}{36} + 0
= \frac{5}{12}

All the probabilities were computed in preceding steps.