6.042/18.062] Mathematics for Computer Science April 14, 2005 Srini devadas and Eric Lehman Problem set 9 Solutions y, Api 1 25 at 9 PM Problem 1. There are three coins: a penny, a nickel, and a quarter. When these coins are app The penny comes up heads with probability 1 3 and tails with probability 2/3 The nickel comes up heads with probability 3/4 and tails with probability 1/4 The quarter comes up heads with probability 3/5 and tails with probability 2/5 assume that the way one coin lands is unaffected by the way the other coins land. The goal of this problem is to determine the probability that an odd number of coins come up heads. For this first problem, we'll closely follow the four-step procedure for solving probability problems described in lecture. Your solution should include a tree diagram (a) What is the sample space for this experiment? Solution. We can regard each outcome as a triple indicating the orientation of the penny, nickel, and quarter. For example, the triple(, T, H)is the outcome in which the penny is heads, the nickel is tails, and the quarter is heads. The sample space is the set of all such triples: H, TI (b) What subset of the sample space is the event that an odd number of coins come up heads? Solution. The event that an odd number of coins come up heads is the subset {(H,H,H),(H,T,T),(T,H,T),(T,T,H)} (c) What is the probability of each outcome in the sample space? Solution. Edges in the tree diagram are labeled with the probabilities given in the problem statement. The probability of each outcome is the product of the probabil- ities along the corresponding root-to-leaf path. The resulting outcome probabilities are noted in the tree diagram
6.042/18.062J Mathematics for Computer Science April 14, 2005 Srini Devadas and Eric Lehman Problem Set 9 Solutions Due: Monday, April 25 at 9 PM Problem 1. There are three coins: a penny, a nickel, and a quarter. When these coins are flipped: • The penny comes up heads with probability 1/3 and tails with probability 2/3. • The nickel comes up heads with probability 3/4 and tails with probability 1/4. • The quarter comes up heads with probability 3/5 and tails with probability 2/5. Assume that the way one coin lands is unaffected by the way the other coins land. The goal of this problem is to determine the probability that an odd number of coins come up heads. For this first problem, we’ll closely follow the fourstep procedure for solving probability problems described in lecture. Your solution should include a tree diagram. (a) What is the sample space for this experiment? Solution. We can regard each outcome as a triple indicating the orientation of the penny, nickel, and quarter. For example, the triple (H, T, H) is the outcome in which the penny is heads, the nickel is tails, and the quarter is heads. The sample space is the set of all such triples: {H, T}3 . (b) What subset of the sample space is the event that an odd number of coins come up heads? Solution. The event that an odd number of coins come up heads is the subset: {(H, H, H),(H, T, T),(T, H, T),(T, T, H)} (c) What is the probability of each outcome in the sample space? Solution. Edges in the tree diagram are labeled with the probabilities given in the problem statement. The probability of each outcome is the product of the probabilities along the corresponding roottoleaf path. The resulting outcome probabilities are noted in the tree diagram
Problem Set 9 3/5 9/60 3/4 6/60 3/5 2/5 3 3/5 18/60 3/4 penny 3/5B 6/60 nickel 4/60 quarter rob (d) What is the probability that an odd number of coins come up heads? Solution The probability of an event is the sum of the probabilities of the outcomes t. In this Pr(odd number of heads Pr({(H,H,H),(H,T,T),(T,H,T),(T,T,H)} Pr((h, H, H))+Pr(H,T,T))+ Pr((T,H, T))+ Pr(T,T, H)) 92126 Problem 2. 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 opportunit revolver)=4/8 Pr(Green has revolver)=3 /8 Pr(Scarlet has revolver)=1/8
2 Problem Set 9 ❳❳❳ ❳❳❳ ✘✘✘ ✘✘✘ ❳❳ ❳❳❳ ❳ ✘✘ ✘✘✘ ✘ ❳❳ ❳❳❳ ❳ ✘✘ ✘✘✘ ✘ ❳❳❳ ❳❳❳ ✘✘✘ ✘✘✘ ❍❍ ❍ ❍❍ ❍ ✟✟ ✟✟ ✟✟ ❍ ❍❍ ❍ ❍❍ ✟✟ ✟✟ ✟✟ ❅ ❅ ❅ ❅ ❅ ❅ H T H T H T T H T H T H T H penny nickel quarter odd? × × × × prob. 1/3 2/3 3/4 1/4 3/4 1/4 3/5 2/5 3/5 2/5 3/5 2/5 3/5 2/5 9/60 6/60 3/60 2/60 18/60 12/60 6/60 4/60 (d) What is the probability that an odd number of coins come up heads? Solution. The probability of an event is the sum of the probabilities of the outcomes in that event. In this case: Pr (odd number of heads) = Pr ({(H, H, H),(H, T, T),(T, H, T),(T, T, H)}) = Pr ((H, H, H)) + Pr ((H, T, T)) + Pr ((T, H, T)) + Pr ((T, T, H)) = 9 60 + 2 60 + 12 60 + 6 60 = 29 60 Problem 2. 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
Problem Set 9 (a) Draw a tree diagram for this problem Indicate edge and outcome probabilities 4 4/48 3/48 1/8 1/48 4/8 8/48 6/48 2/6 3 1/8 3/6 P 4/8 12/48 9/48 op 3/8 1/8 3/48 revolver (b)What is the probability that colonel Mustard is shot? Solution. Denote each outcome with a pair indicating who has the opportunity and who has the revolver. In this notation the event that Colonel Mustard is shot consists of all outcomes where a single person has both: {(P,P),(G,G),(S,S)} n The probability of this event is the sum of the outcome probabilities Pr((P, P), G, G), (S, S)9=Pr((P, P))+Pr((G, G))+Pr((S, S) 4/48+6/48+3/48 13/48 (c) What is the probability that Colonel Mustard is shot, given that Miss Scarlet does not have the revolver? Solution. Let s be the event that Colonel Mustard is shot and let n be the event
Problem Set 9 3 (a) Draw a tree diagram for this problem. Indicate edge and outcome probabilities. Solution. 4/8 P 4/48 G 3/48 3/8 HHHHHH P 1/8 S 1/48 1/6 4/8 P 8/48 G G 6/48 J 2/6 HHHHHH 3/8 J J J 3/6 1/8 S 2/48 J SJ 4/8 P 12/48 J J G JH 9/48 HHHHH opportunity 3/8 1/8 S 3/48 revolver prob. (b) What is the probability that Colonel Mustard is shot? Solution. Denote each outcome with a pair indicating who has the opportunity and who has the revolver. In this notation, the event that Colonel Mustard is shot consists of all outcomes where a single person has both: {(P, P),(G, G),(S, S)} n The probability of this event is the sum of the outcome probabilities: Pr ({(P, P),(G, G),(S, S)}) = Pr ((P, P)) + Pr ((G, G)) + Pr ((S, S)) = 4/48 + 6/48 + 3/48 = 13/48 (c) What is the probability that Colonel Mustard is shot, given that Miss Scarlet does not have the revolver? Solution. Let S be the event that Colonel Mustard is shot, and let N be the event
Problem Set 9 that Miss scarlet does not have the revolver. The solution is Pr(S|N Pr(S∩N) Pr(n) Pr((P, P), G, G)) Pr(P,P),(P,G),(G,P),(G,G),(S,P),(S,G) +兵 (d) What is the probability that Mr. Green had an opportunity, given that Colonel Mustard was shot? Solution. Let G be the event that mr. green has an opportunity, and again let s be the event that Colonel Mustard is shot. Then the solution is PrG s Pr(G∩S) Pr(S) Pr((G, G) Pr(P,P),(G,G),(S,S)) 13 Problem 3. There are three prisoners in a maximum-security prison for fictional villain the evil wizard voldemort the dark lord nd 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 a guard offers to tell Sauron the name of one of the other prisoners who will be re- leased (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 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 Solution. Sauron has reasoned incorrectly. In order to understand his error, let's be- gin by working out the sample space, noting events of interest, and computing outcome probabilities
4 Problem Set 9 that Miss Scarlet does not have the revolver. The solution is: Pr (S | N) = Pr (S ∩ N) Pr (N) Pr ((P, P),(G, G)) = Pr ((P, P),(P, G),(G, P),(G, G),(S, P),(S, G)) 4 6 48 48 + = 4 3 8 6 12 9 48 48 48 48 48 48 + + + + + 5 = 21 (d) What is the probability that Mr. Green had an opportunity, given that Colonel Mustard was shot? Solution. Let G be the event that Mr. Green has an opportunity, and again let S be the event that Colonel Mustard is shot. Then the solution is: Pr (G | S) = Pr (G ∩ S) Pr (S) Pr ((G, G)) = Pr ((P, P),(G, G),(S, S)) 6 48 = 4 6 3 48 48 48 + + 6 = 13 Problem 3. There are three prisoners in a maximumsecurity prison for fictional villains: the Evil Wizard Voldemort, the Dark Lord Sauron, and Little Bunny FooFoo. 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 FooFoo). However, Sauron declines this offer. He reasons that if the guard says, for example, “Little Bunny FooFoo will be released”, then his own probability of release will drop to 1 . This is because he will then know that either he or 2 Voldemort will also be released, and these two events are equally likely. Using a tree diagram and the fourstep 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 FooFoo (because both are to be released), then he names one of the two uniformly at random. Solution. Sauron has reasoned incorrectly. In order to understand his error, let’s begin by working out the sample space, noting events of interest, and computing outcome probabilities:
Problem set 9 1/3 F S 1/3 1/6 FV 1/3 V. S release ard savs says Foo-foo Sauron Foo-foo"release released Define the events s, f, and"F"as follows F=Guard says Foo-Foo is released F= Foo-Foo is released s=Sauron is released The outcomes in each of these events are noted in the tree diagram Saurons error is in failing to realize that the event F(Foo-foo will be released) is dif Probability that Sauron is released, given that Foo-foo is released, is indeed 1 42 ular, the ferent from the event"F(the guard says Foo-foo will be released ). In partic Pr(S/p)sPr(S∩F Pr(F) ++ But the probability that Sauron is released given that the guard merely says so is still 2 /3 Pr(S"F) Pr(S∩“F Pr("F") 3 So Sauron s probability of release is actually unchanged by the guards statement Problem 4. You shuffle a deck of cards and deal your friend a 5-card hand
Problem Set 9 5 ❅ ❅ ❅ ❅ ❅ ❅ released ✟✟✟ ✟✟✟ ❍❍❍❍❍❍ guard says F, S F, V V, S 1/3 1/3 1/3 F F V V 1 1/2 1/2 1 1/3 1/6 1/6 1/3 prob. × × guard says ”Foo-foo” × × × Foo-foo released × × Sauron released Define the events S, F, and “F” as follows: “F” = Guard says Foo-Foo is released F = Foo-Foo is released S = Sauron is released The outcomes in each of these events are noted in the tree diagram. Sauron’s error is in failing to realize that the event F (Foo-foo will be released) is different from the event “F” (the guard says Foo-foo will be released). In particular, the probability that Sauron is released, given that Foo-foo is released, is indeed 1/2: Pr (S | F) = Pr (S ∩ F) Pr (F) = 1 3 1 3 + 1 6 + 1 6 = 1 2 But the probability that Sauron is released given that the guard merely says so is still 2/3: Pr (S | “F”) = Pr (S ∩ “F”) Pr (“F”) = 1 3 1 3 + 1 6 = 2 3 So Sauron’s probability of release is actually unchanged by the guard’s statement. Problem 4. You shuffle a deck of cards and deal your friend a 5-card hand