6.042/18.] Mathematics for Computer Science April 15, 2005 Srini devadas and Eric Lehman Notes for Recitation 17 The Four-Step method This is a good approach to questions of the form, What is the probability that ntuition will mislead you, but this formal approach gives the right answer every time 1. Find the sample space. ( Use a tree diagram. 2. Define events of interest. Mark leaves corresponding to these events 3. Determine outcome probabilities (a) Assign edge probabilities (b) Compute outcome probabilities. Multiply along root-to-leaf paths. Compute event probabilities. (Sum the probabilities of all outcomes in the event
6.042/18.062J Mathematics for Computer Science April 15, 2005 Srini Devadas and Eric Lehman Notes for Recitation 17 The FourStep Method This is a good approach to questions of the form, “What is the probability that ——?” Intuition will mislead you, but this formal approach gives the right answer every time. 1. Find the sample space. (Use a tree diagram.) 2. Define events of interest. (Mark leaves corresponding to these events.) 3. Determine outcome probabilities: (a) Assign edge probabilities. (b) Compute outcome probabilities. (Multiply along roottoleaf paths.) 4. Compute event probabilities. (Sum the probabilities of all outcomes in the event.)
Recitation 17 a Baseball series Problem 1. The New York Yankees and the Boston Red Sox are playing a two-out-of-three series.(In other words, they play until one team has won two games. Then that team is declared the overall winner and the series ends. Assume that the Red Sox win each game pability 3/5, regardless of the outcomes of previous games Answer the questions below using the four-step method. You can use the sa me tree diagram for all three problems (a) What is the probability that a total of 3 games are played? (b) What is the probability that the winner of the series loses the first game? (c) What is the probability that the correct team wins the series? Solution a tree diagram is worked out below 3rd game outcome played? first Probability 4/25 YRY 12/125 YRR 18/125 12/25 From the tree diagram, we get Pr(3 games played) 12 18 12 12 25125125125-25 18126 r(winner lost first game)=125 25 1818981 Pr(correct team wins) 125+125+25=12
Recitation 17 2 A Baseball Series Problem 1. The New York Yankees and the Boston Red Sox are playing a twooutofthree series. (In other words, they play until one team has won two games. Then that team is declared the overall winner and the series ends.) Assume that the Red Sox win each game with probability 3/5, regardless of the outcomes of previous games. Answer the questions below using the fourstep method. You can use the same tree diagram for all three problems. (a) What is the probability that a total of 3 games are played? (b) What is the probability that the winner of the series loses the first game? (c) What is the probability that the correct team wins the series? Solution. A tree diagram is worked out below. 1st game winner 2nd game winner 3rd game winner 3 games played? winner lost first game? correct team wins? Y R 3/5 2/5 2/5 3/5 R 3/5 Y 2/5 B 3/5 Y 2/5 Y R 3/5 R Y 2/5 outcome YY YRY YRR RYY RYR RR Probability X X X X X X 12/125 18/125 X 9/25 X X 12/125 4/25 18/125 From the tree diagram, we get: 12 18 12 18 12 Pr (3 games played) = + + + = 125 125 125 125 25 18 12 6 Pr (winner lost first game) = + = 125 125 25 18 18 9 81 Pr (correct team wins) = + + = 125 125 25 125
Recitation 17 The Four-Door deal Problem 2. Suppose that Let's Make a Deal is played according to different rules. Now there are four doors, with a prize hidden behind one of them. The contestant is allowed to pick a door. The host must then reveal a different door that has no prize behind it. The contestant is allowed to stay with his or her original door or to pick one of the other two that are still closed. If the contestant chooses the door concealing the prize in this second stage, then he or she wins (a)Contestant Stu, a sanitation engineer from Trenton, New Jersey, stays with his original door. What is the probability that he wins the prize? The tree diagram is awkwardly large. This often happens; in fact, sometimes you'll encounter infinite tree diagrams! Try to draw enough of the diagram so that you understand the structure of the remainder Solution Let's make the same assumptions as in the original problem 1. The prize is equally likely to be behind each door 2. The contestant is equally likely to pick each door initially, regardless of the prizes location 3. The host is equally likely to reveal each door that does not conceal the prize and was not selected by the player A partial tree diagram is shown below. The remaining subtrees are symmetric to the full-expanded subtree door revealed Stu wins? AAB 1l48 Ac 1/48 AAD 1/48 ABC 1/32 ABD location of priz ACD ADB ADC
Recitation 17 3 The FourDoor Deal Problem 2. Suppose that Let’s Make a Deal is played according to different rules. Now there are four doors, with a prize hidden behind one of them. The contestant is allowed to pick a door. The host must then reveal a different door that has no prize behind it. The contestant is allowed to stay with his or her original door or to pick one of the other two that are still closed. If the contestant chooses the door concealing the prize in this second stage, then he or she wins. (a) Contestant Stu, a sanitation engineer from Trenton, New Jersey, stays with his original door. What is the probability that he wins the prize? The tree diagram is awkwardly large. This often happens; in fact, sometimes you’ll encounter infinite tree diagrams! Try to draw enough of the diagram so that you understand the structure of the remainder. Solution. Let’s make the same assumptions as in the original problem: 1. The prize is equally likely to be behind each door. 2. The contestant is equally likely to pick each door initially, regardless of the prize’s location. 3. The host is equally likely to reveal each door that does not conceal the prize and was not selected by the player. A partial tree diagram is shown below. The remaining subtrees are symmetric to the fullexpanded subtree. location of prize player’s initial guess B C D A A B C D B C D C D B D C B 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/3 1/3 1/3 1/2 1/2 1/2 1/2 1/2 1/2 door revealed outcome AAB AAC AAD ABC ABD ACB ACD ADB ADC Stu wins? X X X probability 1/48 1/48 1/48 1/32 1/32 1/32 1/32 1/32 1/32
Recitation 17 The probability that Stu wins the prize is We multiply by 4 to account for the four subtrees of which weve only drawn one (b) Contestant Zelda, an alien abduction researcher from Helena, montana, switches to one of the remaining two doors with equal probability. What is the probability that she wins the prize? Solution a partial tree diagram is worked out below final guess Zelda wins? probability door revealed 12c 1/64 1/64 X The probability that Zelda wins the prize is Pr (Zelda wins)=4 6464646464648
� � Recitation 17 4 The probability that Stu wins the prize is: � � Pr (Stu wins) = 4 · 1 48 + 1 48 + 1 48 = 1 4 We multiply by 4 to account for the four subtrees of which we’ve only drawn one. (b) Contestant Zelda, an alien abduction researcher from Helena, Montana, switches to one of the remaining two doors with equal probability. What is the probability that she wins the prize? Solution. A partial tree diagram is worked out below. location of prize player’s initial guess player’s final guess B C D A A B C D B C D C D B D C B 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/3 1/3 1/3 1/2 1/2 1/2 1/2 1/2 1/2 door revealed 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 A B A C A B D A C A D A C B D B D C Zelda wins? X X X X probability 1/64 1/96 1/96 1/96 1/96 1/96 1/64 X 1/64 X 1/96 1/64 1/64 1/64 1/64 1/64 1/64 1/64 1/64 1/64 The probability that Zelda wins the prize is: 1 1 1 1 1 1 3 Pr (Zelda wins) = 4 + + + + + = · 64 64 64 64 64 64 8
Recitation 17 Mergatroid the Engineering student Problem 3. Let's consider another variation of the four-doors problem. Suppose that neither reveal the prize nor open the door that the player picked estriction that she can Carol always opens the lowest-numbered door possible with the re This gives contestant Mergatroid- an engineering student from Cambridge, MA just a little more information about the location of the prize. Suppose that Mergatroid always switches to the lowest-numbered door, excluding his initial pick and the one Carol opened. What is the probability that he wins the priz (Interestingly, in the three-door problem, the contestant gains no advantage if carol always opens the lowest-numbered door available. Solution. A tree diagram is worked out below initial guess probability X 1/16 -C B 1/16 X 1/16 1/16 1/16 1/16 1/16 The probability that Mergatroid wins is
Recitation 17 5 Mergatroid the Engineering student Problem 3. Let’s consider another variation of the fourdoors problem. Suppose that Carol always opens the lowestnumbered door possible with the restriction that she can neither reveal the prize nor open the door that the player picked. This gives contestant Mergatroid— an engineering student from Cambridge, MA— just a little more information about the location of the prize. Suppose that Mergatroid always switches to the lowestnumbered door, excluding his initial pick and the one Carol opened. What is the probability that he wins the prize? (Interestingly, in the threedoor problem, the contestant gains no advantage if Carol always opens the lowestnumbered door available.) Solution. A tree diagram is worked out below. prize location player's initial guess door opened Mergatroid wins? A B C D A A A A B B B B C C C D D D C D 1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 probability B C C B B A A A B B A A A A A A 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 X X X X X X X X The probability that Mergatroid wins is: 1 1 Pr (win) = 8 = · 16 2