CS 70 Discrete Mathematics for CS

Fall 2004  Rao  HW 6

Due on Thursday, October 28 at 3:29PM

1. (20 pts.) A paradox in conditional probability? Here is some on-time arrival data for two airlines, A and B, into the airports of Los Angeles and Chicago. (Predictably, both airlines perform better in LA, which is subject to less flight congestion and less bad weather.)

Airline A  Airline B
# flights # on time # flight # on time
Los Angeles 600  534  200  188
Chicago  250  176  900  685

(a) Which of the two airlines has a better chance of arriving on time into Los Angeles? What about Chicago?

(b) Which of the two airlines has a better chance of arriving on time overall?

(c) Do the result of parts (a) and (b) surprise you? Explain the apparent paradox, and interpret it in terms of conditional probabilities.

2. (20 pts.) Money bags I have a bag containing either a $1 or $5 bill (with equal probability assigned to both possibilities). I then add a $1 bill to the bag, so it now contains two bills. The bag is shaken, and you draw out a $1 bill. If a second student draws the remaining bill from the bag, what is the chance that it is a $1 bill? Show your work.

3. (20 pts.) Happy families

(a) Consider a collection of families, each of which has exactly two children. Each of the four possible combinations of boys and girls, bg,gb,bb,gg, occurs with the same frequency. A family is chosen uniformly at random, and we are told that it contains at least one boy. What is the (conditional) probability that the other child is a boy? Justify your answer with a precise calculation.

(b) On the same probability space as in part (a), let A be the event that the chosen family has children of both sexes, and B the event that the family has at least one girl. Are the events A and B independent? Justify your answer carefully.

(c) Consider now the probability space of families with three children, with each of the eight possible combinations of boys and girls equally likely. Define the events A and B as in part (b). Are these events independent? Again, justify your answer carefully.

4. (25 pts.) Monty Hall again!

(a) Consider the following variant of the Monty Hall problem. The contestant picks a door, but instead of revealing this door to Monty, he/she writes it down on a piece of paper. Monty then opens one of the two goat doors (chosen uniformly at random). If the door opened by Monty is the one chosen by the contestant, then the contestant knows he was wrong and picks one of the remaining two doors at random. Otherwise (i.e., when the door opened by monty is not his chosen door) the contestant is given the option of switching to the other unopened door. (Note that the switching option comes into play only in this second case.) Write down (in tree form) the entire sample space for this version of the game, and compute the probability that the contestant wins under both the switching and sticking stategies. Should the contestant switch?

(b) After many years, the standard version of the game with three doors becomes a little boring, so Monty decides to increase the number of doors to four (with one prize and three goats). What is now the probability that the contestant wins under the switching strategy?

(c) Finally, suppose there are n doors and m ≤ n − 2 prizes (each one behind a different color). Again, the contestant picks a door and Monty then opens a goat door. (The condition m ≤ n − 2 ensures that this is always possible.) What is the probability of winning under the “sticking” strategy? What is the probability of winning under the “switching” strategy? Both of your answers should be given as a function of m and n.

5. (15 pts.) Coin Tosses Suppose you have a biased coin with Pr[Head] ≠ 0.5. How could you use this coin to simulate a fair coin? (Hint: Think about pairs of tosses.)