6.042/18.062J 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 ——-?”
Intuition will mislead you,but this formal approach gives the right answer every time,
1,Find the sample space,(Use a tree diagram.)
2,De?ne 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.)
4,Compute event probabilities,(Sum the probabilities of all outcomes in the event.)
2 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
with probability 3/5,regardless of the outcomes of previous games,
Answer the questions below using the four-step 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?rst game?
(c) What is the probability that the correct team wins the series?
Solution,A tree diagram is worked out below,
1st gamewinner
2nd gamewinner 3rd gamewinner 3 gamesplayed? winner lostfirst game?correctteamwins?
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?rst game) = + =
125 125 25
18 18 9 81
Pr (correct team wins) = + + =
125 125 25 125
3 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 in?nite 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
full-expanded 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 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,
locationof prize
player’sinitial
guess
player’sfinal 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/21/2
1/2
1/2
1/2
1/2
1/21/2
1/21/2
1/21/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
1/64X
X
1/961/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
5 Recitation 17
Mergatroid the Engineering student
Problem 3,Let’s consider another variation of the four-doors problem,Suppose that
Carol always opens the lowest-numbered 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 lowest-numbered door,excluding his initial pick and the one Carol
opened,What is the probability that he wins the prize?
(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,
prizelocation
player'sinitial guessdooropenedMergatroidwins?
A
B
C
D
A
A
A
A
B
B
B
BC
C
C
D
D
DC
D
1/4
1/4
1/4
1/4
1/4
1/41/4
1/4
probability
BC
C
BB
AA
AB
B
AA
A
AA
A
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
X
XX
X
XX
XX
The probability that Mergatroid wins is,
1 1
Pr (win) = 8 = ·
16 2
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 ——-?”
Intuition will mislead you,but this formal approach gives the right answer every time,
1,Find the sample space,(Use a tree diagram.)
2,De?ne 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.)
4,Compute event probabilities,(Sum the probabilities of all outcomes in the event.)
2 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
with probability 3/5,regardless of the outcomes of previous games,
Answer the questions below using the four-step 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?rst game?
(c) What is the probability that the correct team wins the series?
Solution,A tree diagram is worked out below,
1st gamewinner
2nd gamewinner 3rd gamewinner 3 gamesplayed? winner lostfirst game?correctteamwins?
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?rst game) = + =
125 125 25
18 18 9 81
Pr (correct team wins) = + + =
125 125 25 125
3 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 in?nite 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
full-expanded 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 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,
locationof prize
player’sinitial
guess
player’sfinal 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/21/2
1/2
1/2
1/2
1/2
1/21/2
1/21/2
1/21/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
1/64X
X
1/961/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
5 Recitation 17
Mergatroid the Engineering student
Problem 3,Let’s consider another variation of the four-doors problem,Suppose that
Carol always opens the lowest-numbered 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 lowest-numbered door,excluding his initial pick and the one Carol
opened,What is the probability that he wins the prize?
(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,
prizelocation
player'sinitial guessdooropenedMergatroidwins?
A
B
C
D
A
A
A
A
B
B
B
BC
C
C
D
D
DC
D
1/4
1/4
1/4
1/4
1/4
1/41/4
1/4
probability
BC
C
BB
AA
AB
B
AA
A
AA
A
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
1/161/16
X
XX
X
XX
XX
The probability that Mergatroid wins is,
1 1
Pr (win) = 8 = ·
16 2
