Problem 1(a)(b)(c)(d)Problem 2Problem 3(a)(b)(c)Problem 4Problem 5(a)(b)(c)Problem 6(a)(b)(c)(d)Problem 7Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 21 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised November 20, 2005, 1178 minutes Problem Set 9 Due: December 2 Reading: Week 12 Notes. Week 13 Notes, Sections 1 and 2 (Random Variables and the Birthday Principle). Problem 1. Professor Plum, Mr. Green, and Miss Scarlet are all plotting to shoot Colonel Mustard. If one of these three has both an opportunity and the revolver, then that person shoots Colonel Mustard. Otherwise, Colonel Mustard escapes. Exactly one of the three has an opportunity with the following probabilities: Pr {Plum has opportunity} = 1/6 Pr {Green has opportunity} = 2/6 Pr {Scarlet has opportunity} = 3/6 Exactly one has the revolver with the following probabilities, regardless of who has an opportuntity: Pr {Plum has revolver} = 4/8 Pr {Green has revolver} = 3/8 Pr {Scarlet has revolver} = 1/8 (a) Draw a tree diagram for this problem. Indicate edge and outcome probabilities. (b) What is the probability that Colonel Mustard is shot? (c) What is the probability that Colonel Mustard is shot, given that Miss Scarlet does not have the revolver? (d) What is the probability that Mr. Green had an opportunity, given that Colonel Mus-tard was shot? Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld.2 Problem Set 9 Problem 2. There are three prisoners in a maximum-security prison for fictional villains: the Evil Wizard Voldemort, the Dark Lord Sauron, and Little Bunny Foo-Foo. The parole board has declared that it will release two of the three, chosen uniformly at random, but has not yet released their names. Naturally, Sauron figures that he will be released to his home in Mordor, where the shadows lie, with probability 2/3. A guard offers to tell Sauron the name of one of the other prisoners who will be released (either Voldemort or Foo-Foo). However, Sauron declines this offer. He reasons that if the guard says, for example, “Little Bunny Foo-Foo will be released”, then his own probability of release will drop to 1/2. This is because he will then know that either he or Voldemort will also be released, and these two events are equally likely. Using a tree diagram and the four-step method, either prove that the Dark Lord Sauron has reasoned correctly or prove that he is wrong. Assume that if the guard has a choice of naming either Voldemort or Foo-Foo (because both are to be released), then he names one of the two uniformly at random. Problem 3. You shuffle a deck of cards and deal your friend a 5-card hand. (a) Suppose your friend says, “I have the ace of spades.” What is the probablity that she has another ace? (b) Suppose your friend says, “I have an ace.” What is the probability that she has an-other ace? (c) Are your answers to (a) and (b) the same? Explain why. Problem 4. Finalphobia is a rare disease in which the victim has the delusion that he or she is being subjected to an intense mathematical examination. • A person selected uniformly at random has finalphobia with probability 1/100. • A person with finalphobia has shaky hands with probability 9/10. • A person without finalphobia has shaky hands with probability 1/20. What is the probablility that a person selected uniformly at random has finalphobia, given that he or she has shaky hands?�3 Problem Set 9 Problem 5. Outside of their hum-drum duties as 6.042 TAs, Sayan is trying to learn to levitate using only intense concentration and Jelani is launching a “Nelson 2008” presi-dential campaign. Suppose that Sayan’s probability of levitating is 1/6, Jelani’s chance of becoming president is 1/4, and the success of one does not alter the other’s chances. (a) If at least one of them succeeds, what is the probability that Sayan learns to levitate? (b) If at most one of them succeeds, what is the probability that Jelani becomes the pres-ident of the United States? (c) If exactly one of them succeeds, what is the probability that it is Sayan? Problem 6. Suppose n balls are thrown randomly into n boxes, so each ball lands in each box with uniform probability. Also, suppose the outcome of each throw is independent of all the other throws. (a) Let Xi be an indicator random variable whose value is 1 if box i is empty and 0 otherwise. Write a simple closed form expression for the probability distribution of Xi. Are X1, X2, . . . , Xn independent random variables? (b) Show that � �� �k n 1Pr {at least k balls fall in the first box} ≤ . k n (c) Let R be the maximum of the numbers of balls that land in each of the boxes. Con-clude from the previous parts that n .Pr {R ≥ k} ≤ k! (d) Conclude that lim Pr {R ≥ n } = 0 n→∞ for all � > 0. Problem 7. (An open-ended discussion question.) Consider a set, S, consisting of 77 twenty-one digit numbers. We can use the pigeonhole principle to prove that two distinct subsets of the numbers in S have the same sum, but actually finding two such sets is can be difficult. Naively, we could sum the elements in all 277 subsets and find two that match, but this is a huge computational task.4 Problem Set 9 Recall the birthday principle: If there are d days in a year and √2d people in a room, then the probability that two share a birthday is about 1 − 1/e = 0.632 . . .. How could the birthday principle help you find two distinct subsets of S with the same sum using significantly fewer than 277 operations —say only a trillion operations? What assumptions must you make?Massachusetts Institute of Technology Solutions cover sheet 6.042J/18.062J, Fall ’05: Mathematics for Computer Science November 21 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld Student’s Solutions to Problem Set 9 Your name: Due date: December 2 Submission date: Circle your TA: David Jelani Sayan Hanson Collaboration statement: Circle one of the two choices and provide all pertinent info. 1. I worked alone and only with course materials. 2. I collaborated on this assignment with: got help from:1 and referred to:2 DO NOT WRITE BELOW THIS LINE Problem Score 1 2 3 4 5 6 7 Total Copyright © 2005, Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld. All rights reserved. 1People other than course staff. 2Give citations to texts and material other than the Fall ’02
View Full Document
Unlocking...