CMPSC 360 Instructors: Sofya Raskhodnikova Discrete Mathematics for Computer Science Yanling Wang Pennsylvania State University April 15, 2015 Homework 11 - Due Wednesday, April 22 before the lecture; grace period until 4:30PM in 342G IST Instructions for submission are the same as for previous homework assignments. Problems 1-3 have to be submitted on Angel by 4:30PM on the due date. To answer parts which have numeric answers, enter an integer, a simplied fraction, or a decimal number accurate to at least 4 digits after the decimal point. Problems 4-10 have to be printed on separate sheets of paper. 1. [The Game of Goats] You are playing a game in which you are placed inside a circular room containing 6 doors. The host selects 2 random doors and places a car behind each of them. He also places a goat behind each of the other 4 doors. You get a chance to choose one door out of 6, and your aim is to get a car (so that you can escape from this game as fast as possible). (a) What is the probability that there will be a car behind the door that you choose? (b) You choose a door and it turns out that there is a goat behind it. You feel dejected but you don't give up. Knowing that you are anyway going back home with a goat, you ask the host if you can take a second chance instead and pick the door on the right of the one which you chose initially. What is the probability that there will be a car behind the second door that you choose? (c) Suppose you know that the host placed the two cars behind adjacent doors. Does this change the answers to parts (a) and (b) above? i. Enter your answer for the question in part (a) with the new car placing strategy. ii. Enter your answer for the question in part (b) with the new car placing strategy. 2. [Random Variables] Consider the sample space = {1, 2, 3, . . . , 10} with Pr() = this sample space, dene the random variables X and Y by X() = 2 and Y () = 2 for all . Answer the following questions: (a) What is Pr[X < 10]? 1 1 10 for all . For (b) What is Pr[Y < 10]? (c) What is (X + Y )()? Give an expression in terms of ; enter w instead of . (d) What is Pr[X + Y < 10]? (e) What is Pr[X > Y ]? (f) What is Pr[X = Y ]? (g) Are X and Y independent? Justify your answer. 3. Bruce Lee, in a movie that didn't go public, is practicing by trying to break 5 boards with his st. He is able to break a board with probability 0.8he is practicing with his left st, that's why it's not 1and he breaks each board independently. (a) What is the probability that Bruce breaks exactly 2 out of the 5 boards that are placed before him? (b) What is the probability that Bruce breaks at most 3 out of the 5 boards that are placed before him? (c) What is the expected number of boards Bruce will break? 2 CMPSC 360 Spring 2015 Homework 11 Name: Section: Collaborators: 4. [Playing Cards] For each part below, explain how you got your answer. Nearly all points will be allocated for explanation. Thirteen cards are drawn (without replacement) from a standard deck of cards. What is the probability that: (a) they are all spades? (b) they are all black? (c) they are not all of one color? (d) none of the cards is an ace? (continued on the next page) Continued from the previous page (e) none of the cards is an ace and none is a heart? CMPSC 360 Spring 2015 Homework 11 Name: Section: Collaborators: 5. [Chess board] Consider an 8 8 chess board in which the rows are numbered from 1 to 8, and likewise for the columns. And, as is usual for a chess board, the squares are alternately colored black and white. The squares of this chess board form the elements of a sample space in which all of the 64 squares on the chess board are equally likely; 1 that is, all have probability 64 . For each of the following pairs of events A and B, determine if the two events are independent and prove your answer is correct: (a) A is the event that a white square is chosen and B is the event that a black square is chosen. (b) A is the event that a square from an even numbered row is chosen and B is the event that a square from an even numbered column is chosen. (c) A is the event that a white square is chosen and B is the event that a square from an even numbered column is chosen. (continued on the next page) Continued from the previous page Determine if the following three events A, B and C are mutually independent and prove your answer is correct: (d) A is the event that a square from an even numbered row is chosen, B is the event that a square from an even numbered column is chosen, and C is the event that a white square is chosen. CMPSC 360 Spring 2015 Homework 11 Name: Section: Collaborators: 6. [Three-way collisions] In lecture on April 15, we analyzed the probability of collisions in a hash function. (This analysis is also explained in Berkeley Note 15, pages 1-2.) In this problem, you are asked to perform a similar analysis for 3-way collisions, that is, for three keys hashing to the same value. We phrase this problem directly in terms of balls and bins, hoping that you understand the analogy. There are m balls and n bins. Each ball is dropped uniformly at random into one of the n bins. That is, it has equal probability of landing in each bin. Let A be the event that no bin contains three or more balls. Clearly, Pr[A] will decrease as m increases (with n xed). Your goal is to nd as large value of m as you can (expressed in terms 1 of n) so that Pr[A] remains at least 2 . (a) A set of three balls is called a triple. Let k be the total number of triples. Express k in terms of m. (b) Let Ai be the event that all three balls in triple i land in the same bin. For each i = 1, 2, . . . , k separately, what is Pr[Ai ]? Explain your answer. (continued on the next page) Continued from the previous page (c) Use the union bound and the results from parts (a) and (b) to nd as large value of m as you can for which Pr[A] 1 . 2 Hint: Use the fact that m c m for positive c. CMPSC 360 Spring 2015 Homework 11 Name: Section: Collaborators: 7. [Detecting defects] You are in charge of inspecting cookies baked in your company. A worker is unreliable if the proportion of defective cookies he bakes is or higher. (For example, if he bakes 1000 cookies in a day, 1000 of them will be defective.) (a) You would like to make sure that if a worker is unreliable, you will nd at least one defective cookie with probability 99% and re him. You do not have time to inspect every single cookie. Instead you decide to choose k cookies uniformly at random. For simplicity, let's say that you will choose cookies with replacement. That is, on each try you nd a defective cookie with probability p, where p is the proportion of defective cookies the worker baked. Prove that if k ln 100 and p than you will nd at least one defective cookie with probability 99%. Hint: Use the fact that 1 + x ex . (continued on the next page) Continued from the previous page (b) You got a raise, and now you are inspecting cookies made by n workers. You would like to ensure that with probability at least 99%, all unreliable workers will be red, that is, you will detect a defective cookie for every one of them. You use the same random strategy as in part (a) for each worker, but now you have to inspect more cookies per worker because you want to achieve overall success probability of 99%, not just per worker. What should you choose k to be as a function of and n? Find the smallest k you can. Hint: Use the union bound. CMPSC 360 Spring 2015 Homework 11 Name: Section: Collaborators: 8. [Unexpected expectation] The term expected value can be a bit deceiving. The following questions ask you to nd random variables whose expected value is not what someone might expect! (a) Give an example of a random variable X whose expected value is 1, but the probability that X = 1 is 0. (b) Give an example of a random variable X whose expected value is negative, but the probability that X is positive is 99.999%. Continued from the previous page (This page is intentionally left blank.) CMPSC 360 Spring 2015 Homework 11 Name: Section: Collaborators: 9. [Chopping up DNA] Explain in detail how you arrive at your answers. (a) In a certain biological experiment, a piece of DNA consisting of a linear sequence (or string) of 4001 nucleotides is subject to bombardment by various enzymes. The eect of the bombardment is to randomly cut the string between pairs of adjacent nucleotides: each of the 4000 possible cuts occurs independently and 1 with probability 500 . What is the expected number of pieces into which the string is cut? [Hint: Use linearity of expectation. If you do it this way, you can avoid a huge amount of messy calculation. Remember to justify the steps in your argument; i.e., do not appeal to \"common sense.\"] (continued on the next page) Continued from the previous page (b) Suppose now that the cuts are no longer independent, but highly correlated, so that when a cut occurs in a particular place other cuts close by are much more 1 likely. The probability of each individual cut remains 500 . Does the expected number of pieces increase, decrease, or stay the same? Justify your answer with a precise explanation. CMPSC 360 Spring 2015 Homework 7 Name: Section: No collaboration allowed on optional problems 10 [Optional] A vending machine sells 20 kinds of fruit. Every time you pay, it dispenses one piece of fruit of a uniformly random kind. In expectation, how many times do you have to pay to get 10 dierent kinds of fruit? (This page is intentionally left blank.)