CS 70 Discrete Mathematics and Probability Theory Fall 2013 Vazirani Counting + Probability Practice 1. Counting, counting and counting The only way to learn counting is to practice, practice, practice, so here is your chance to do so. We encourage you to leave your answer as an expression (rather than trying to evaluate it to get a specific number). (a) How many 10-bit strings are there that contain exactly 4 ones? (b) How many different 13-card bridge hands are there? (A bridge hand is obtained by selecting 13 cards from a standard 52-card deck. The order of the cards in a bridge hand is irrelevant.) (c) How many different 13-card bridge hands are there that contain no aces? (d) How many different 13-card bridge hands are there that contain all four aces? (e) How many different 13-card bridge hands are there that contain exactly 6 spades? (f) How many 99-bit strings are there that contain more ones than zeros? (g) If we have a standard 52-card deck, how many ways are there to order these 52 cards? (h) Two identical decks of 52 cards are mixed together, yielding a stack of 104 cards. How many different ways are there to order this stack of 104 cards? (i) How many different anagrams of FLORIDA are there? (An anagram of FLORIDA is any reordering of the letters of FLORIDA, i.e., any string made up of the letters F, L, O, R, I, D, and A, in any order. The anagram does not have to be an English word.) (j) How many different anagrams of ALASKA are there? (k) How many different anagrams of ALABAMA are there? (l) How many anagrams does the word PAPASAN have where the S and N are not adjacent? For example, count APPSANA but do not count APAANSP. (m) We have 9 balls, numbered 1 through 9, and 27 bins. How many different ways are there to distribute these 9 balls among the 27 bins? (n) We throw 9 identical balls into 7 bins. How many different ways are there to distribute these 9 balls among the 7 bins such that no bin is empty? (o) How many different ways are there to throw 9 identical balls into 27 bins? (p) How many ways are there to place 50 unlabeled balls in 9 labeled bins where each bin contains at least as many balls as its bin number. (That is, bin 1 contains at least 1 ball, bin 2 contains at least 2, and so on.) (q) There are exactly 20 students currently enrolled in a class. How many different ways are there to pair up the 20 students, so that each student is paired with one other student? 2. More Counting Let A, B be finite sets, with |A| = m and |B| = n. CS 70, Fall 2013, Counting + Probability Practice 1 (a) How many subsets does A have? (Recall that the empty set and A are both subsets of A.) (b) How many distinct functions f : A → B are there from A to B? (c) Suppose m = n. How many distinct bijections are there from A to B? 3. And More Counting How many non-negative integer solutions (x1 , . . . , x7 ) are there to the following equation? x1 + x2 + x3 + x4 + x5 + x6 + x7 = 2003 x1 ≥ 0, . . . , x7 ≥ 0, x1 , . . . , x7 ∈ Z Order matters. For instance, (1, 2002, 0, 0, 0, 0, 0) counts as a different solution than (2002, 1, 0, 0, 0, 0, 0). 4. Sum of digits Choose a number uniformly at random between 0 and 999,999, inclusive. What is the probability that the digits sum to 19? 5. Algebraic vs. combinatorial proofs Consider the following identity: 2n n =2 + n2 . 2 2 (a) Prove the identity by algebraic manipulation (using the formula for the binomial coefficients). (b) Prove the identity using a combinatorial argument. (Write both sides as the answer to a question of the form “how many ways can you...?”) 6. Red cards Consider a deck with just the four aces (red: hearts, diamonds; black: spades, clubs). Melissa shuffles the deck and draws the top two cards. Given that Melissa has the ace of hearts, what is the probability that Melissa has both red cards? Given that Melissa has at least one red card, what is the probability that she has both red cards? 7. Sample Space and Events Consider the sample space Ω of all outcomes from flipping a coin 4 times. (a) List all the outcomes in Ω. How many are there? (b) Let A be the event that the first flip is a Heads. List all the outcomes in A. How many are there? (c) Let B be the event that the third flip is a Heads. List all the outcomes in B. How many are there? (d) Let C be the event that the first flip and the third flip are both Heads. List all the outcomes in C. How many are there? (e) Let D be the event that the first flip or the third flip is a Heads. List all the outcomes in D. How many are there? (f) Are the events A and B disjoint? Express the event C in terms of A and B. Express the event D in terms of A and B. (g) Suppose now the coin is flipped n ≥ 3 times instead of 4 flips. Compute |Ω|, |A|, |B|, |C|, |D|. CS 70, Fall 2013, Counting + Probability Practice 2 8. Probability Models Suppose you have two coins, one is biased with a probability of p coming up Heads, and one is biased with a probability of q coming up Heads. Answer the questions below, but you don’t need to provide justifications. (a) Suppose p = 1 and q = 0. i. You pick one of the two coins randomly and flip it. You repeat this process n times, each time randomly picking one of the two coins and then flipping it. Consider the sample space Ω of all possible length n sequences of Heads and Tails so generated. Give a reasonable probability assignment (i.e. assign probabilities to all the outcomes) to model the situation. ii. Now you pick one of the two coins randomly, but flip the same coin n times. Identify the sample space for this experiment together with a reasonable probability assignment to model the situation. Is your answer the same as in the previous part? (b) Repeat the above two questions for arbitrary values of p and q. Express your answers in terms of p and q. 9. Independence We flip two unbiased coins: a nickel and a dime, and consider the following events: (a) The nickel comes up heads. (b) The dime comes up heads. (c) The nickel and dime both come up heads. (d) Exactly one of the nickel and dime comes up heads. (e) The nickel and dime both come up the same way. State without proof whether each of the following pairs of events are independent: • (a) and (b): • (a) and (c): • (a) and (d): • (a) and (e): • (c) and (b): • (d) and (b): • (e) and (b): • (c) and (d): • (c) and (e): • (d) and (e): State without proof whether each of the following triples of events are independent: • (a), (b), (c): • (a), (b), (d): • (a), (b), (e): CS 70, Fall 2013, Counting + Probability Practice 3 • (b), (d), (e): • (a), (c), (e): 10. Correlation It was suggested in class that, when Pr[A|B] > Pr[A], then A and B may be viewed intuitively as being positively correlated. One might wonder whether “being positively correlated” is a symmetric relation. Prove or disprove: If Pr[A|B] > Pr[A] holds, then Pr[B|A] > Pr[B] must necessarily hold, too. (You may assume that both Pr[A|B] and Pr[B|A] are well-defined, i.e., neither Pr[A] nor Pr[B] are zero.) 11. Monty Hall Again In the three-door Monty Hall problem, there are two stages to the decision, the initial pick followed by the decision to stick with it or switch to the only other remaining alternative after the host has shown an incorrect door. An extension of the basic problem to multiple stages goes as follow. Suppose there are four doors, one of which is a winner. The host says: "You point to one of the doors, and then I will open one of the other non-winners. Then you decide whether to stick with your original pick or switch to one of the remaining doors. Then I will open another (other than the current pick) non-winner. You will then make your final decision by sticking with the door picked on the previous decision or by switching to the only other remaining door. (a) How many possible strategies are there? (b) For each of the possible strategies, calculate the probability of winning. What is the best strategy? 12. Smokers A health study tracked a group of people for five years. At the beginning of the study, 20% were classified as heavy smokers, 30% as light smokers, and 50% as nonsmokers. Results of the study showed that light smokers were twice as likely as nonsmokers to die during the five-year study, but only half as likely as heavy smokers. Suppose we select, uniformly at random, a participant from this study, and it turns out that this participant died at some point during the five-year period. Calculate the probability that this participant was classified as a heavy smoker at the beginning of the study. Show your calculation clearly. 13. The myth of fingerprints A crime has been committed. The police discover that the criminal has left DNA behind, and they compare the DNA fingerprint against a police database containing DNA fingerprints for 20 million people. Assume that the probability that two DNA fingerprints (falsely) match by chance is 1 in 10 million. Assume that, if the crime was committed by someone whose DNA fingerprint is on file in the police database, then it’s certain that this will turn up as a match when the police compare the crime-scene evidence to their database; the only question is whether there will be any false matches. Let D denote the event that the criminal’s DNA is in the database; ¬D denotes the event that the criminal’s DNA is not in the database. Assume that it is well-documented that half of all such crimes are committed by criminals in the database, i.e., assume that Pr[D] = Pr[¬D] = 1/2. Let the random variable X denote the number of matches that are found when the police run the crime-scene sample against the DNA database. (a) Calculate Pr[X = 1|D]. CS 70, Fall 2013, Counting + Probability Practice 4 (b) Calculate Pr[X = 1|¬D]. (c) Calculate Pr[¬D|X = 1]. Evaluate the expression you get and compute this probability to at least two digits of precision. As it happens, the police find exactly one match, and promptly prosecute the corresponding individual. You are appointed a member of the jury, and the DNA match is the only evidence that the police present. During the trial, an expert witness testifies that the probability that two DNA fingerprints (falsely) match by chance is 1 in 10 million. In his summary statement, the prosecutor tells the jury that this means that the probability that the defendant is innocent is 1 in 10 million. (d) What is wrong with the prosecutor’s reasoning in the summary statement? (e) Do you think the defendant should be convicted? Why or why not? 14. Poisoned pancakes You have been hired as an actuary by IHOP corporate headquarters, and have been handed a report from Corporate Intelligence that indicates that a covert team of ninjas hired by Denny’s will sneak into some IHOP, and will have time to poison five of the pancakes being prepared (they can’t stay any longer to avoid being discovered by Pancake Security). Given that an IHOP kitchen has 50 pancakes being prepared, and there are ten patrons, each ordering five pancakes (which are chosen uniformly at random from the pancakes in the kitchen), calculate the probabilities that the first patron: (a) will not receive any poisoned pancakes; (b) will receive exactly one poisoned pancake; (c) will receive at least one poisoned pancake; (d) will receive at least one poisoned pancake given that the second patron received at least one poisoned pancake; (e) Calculate the probability that any of the first three receive at least one poisoned pancake. 15. Colorful coins We are given three coins. The first coin is a fair coin painted blue on the heads side and white on the tails side. The other two coins are biased so that the probability of heads is p. They are painted blue on the tails side and red on the heads side. One coin is randomly chosen and flipped twice. (a) Describe the outcomes in the sample space, and give their probabilities. [N OTE: You may want to draw a tree to illustrate the sample space.] (b) Now suppose two coins are chosen randomly with replacement and each flipped once. Describe the outcomes in the sample space in this new experiment, and give their probabilities. Are they the same as in part (a)? [N OTE: You may want to draw a tree to illustrate the sample space.] (c) Now suppose two coins are chosen randomly without replacement and each flipped once. Describe the outcomes in the sample space in this new experiment, and give their probabilities. Are they the same as in parts (a) or (b)? [N OTE: You may want to draw a tree to illustrate the sample space.] (d) Suppose the probability that the two sides that land face up are the same color is experiment in part (c). What does this tell you about the possible values of p? CS 70, Fall 2013, Counting + Probability Practice 29 96 in the 5 (e) Let A be the event that you get a head on the first flip and B is the event that you get a head on the second flip. In each of the experiments in (a), (b) and (c), determine whether A and B are independent events. 16. 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.) Los Angeles Chicago Airline A # flights # on time 600 534 250 176 Airline B #flights # on time 200 188 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 results of parts (a) and (b) surprise you? Explain the apparent paradox, and interpret it in terms of conditional probabilities. 17. A flippant choice We have noted that if a fair coin is flipped three times, there are eight equally probable outcomes: HHH, HHT, HTH, HTT, THH, THT, TTH, and TTT. Two CS 70 students play a game based on coin flipping. Player A selects one of the triplets just listed; player B selects a different one. The coin is then repeatedly flipped until one of the chosen triplets appears as a run and wins the game. For example, if player A chooses HHT and player B chooses THT and the flips are THHHT, player A wins. Fill in the table below to show player B’s best choice of triplet for each possible choice that player A makes, and the probability of player B winning with a best choice. Then explain why the odds for one player winning are so lopsided. Player A’s choice HHH HHT HTH HTT THH THT TTH TTT Player B’s best choice Player B’s probability of winning 18. Stakes well done Two players, Alice and Bob, each stake 32 pistoles on a three-point, winner-take-all game of chance. The game is played in rounds; at each round, one of the two players gains a point and the other gains none. Normally the first player to reach 3 points would win the 64 pistoles. However, it starts to rain during the game, and play is suspended at a point where Alice has 2 points and Bob has 1 point. Alice and Bob have to figure out how to split the money. CS 70, Fall 2013, Counting + Probability Practice 6 You should assume that Alice and Bob are evenly matched, so that in each round Alice and Bob each have a 50% chance of winning the round. Assume also that Alice’s share should be proportional to the conditional expected valueof her winnings (specifically, her winnings if the game were continued to the end from this point). The same goes for Bob. Calculate a fair way to distribute the 64 pistoles using this notion of fairness. How many pistoles does Alice receive? Bob? CS 70, Fall 2013, Counting + Probability Practice 7