6.042/18.062J Mathematics for Computer Science April 22,2005
Srini Devadas and Eric Lehman
Notes for Recitation 18
The Law of Total Probability is a handy tool for breaking down the computation of a prob-
ability into distinct cases,More precisely,suppose we are interested in the probability of
an event E,Pr (E),Suppose also that the random experiment can evolve in two different
ways; that is,two different cases X and X are possible,Suppose also that
it is easy to?nd the probability of each case,Pr (X) and Pr X,
it easy to?nd the probability of the event in each case,Pr (E | X) and Pr E X,|
Then?nding the probability of E is only two multiplications and an addition away,
Theorem 1 (Law of Total Probability),Let E and X be events,and 0 < Pr (X) < 1,Then
Pr (E) = Pr (X) · Pr (E | X) + Pr X Pr E | X·
Proof,Let’s simplify the right-hand side,
Pr (E | X) · Pr (X) + Pr E X Pr X| ·

Pr E ∩ X?
=
Pr (E ∩ X)
· Pr (X) + Pr
X
Pr (X)
Pr X
·
= Pr (E ∩ X) + Pr E ∩ X
= Pr (E)
The?rst step uses the de?nition of conditional probability,On the next-to-last line,we’re
adding the probabilities of all outcomes in E and X to the probabilities of all outcomes in
E and not in X,Since every outcome in E is either in X or not in X,this is the sum of the
probabilities of all outcomes in E,which equals Pr (E),
What happens if the experiment can evolve in more than two different ways? That is,
what if there are n cases,X
1
,...,X
n
,which are mutually exclusive (no two cases can hap-
pen simultaneously) and collectively exhaustive (at least one case must happen)? If it is still
easy to?nd the probability of each case and the probability of the event in each case,then
again?nding Pr (E) is trivial,
Theorem 2,Let E be an event and let X
1
,...,X
n
be disjoint events whose union exhausts the
sample space,Then
n
Pr (E) = Pr (E | X
i
) · Pr (X
i
)
i=1
provided that Pr (X
i
) =? 0,

2 Recitation 18
Problem 1,There is a rare and deadly disease called Nerditosis which af?icts about 1 per-
son in 1000,On symption is a compulsion to refer to everything—?elds of study,classes,
buildings,etc.— using numbers,It’s horrible,As victims enter their?nal,downward
spiral,they’re awarded a degree from MIT,Two doctors claim that they can diagnose
Nerditosis,
(a) Doctor X received his degree from Harvard Medical School,He practices at Mas-
sachusetts General Hospital and has access to the latest scanners,lab tests,and re-
search,Suppose you ask Doctor X whether you have the disease,
If you have Nerditosis,he says,yes” with probability 0.99,
If you don’t have it,he says,no” with probability 0.97,
Let D be the event that you have the disease,and let E be the event that the diag-
nosis is erroneous,Use the Total Probability Law to compute Pr (E),the probability
that Doctor X makes a mistake,
Solution,By the Total Probability Law,
Pr (E) = Pr (E | D) · Pr (D) + Pr E D Pr D| ·
= 0.01 · 0.001 + 0.03 · 0.999
= 0.02998
(b) ,Doctor” Y received his genuine degree from a fully-accredited university for $49.95
via a special internet offer,He knows that Nerditosis stikes 1 person in 1000,but is
a little shakey on how to interpret this,So if you ask him whether you have the
disease,he’ll helpfully say,yes” with probability 1 in 1000 regardless of whether
you actually do or not,
Let D be the event that you have the disease,and let F be the event that the diag-
nosis is faulty,Use the Total Probability Law to compute Pr (F),the probability that
Doctor Y made a mistake,
Solution,By the Total Probability Law,
Pr (F) = Pr (F D) · Pr (D) + Pr F | D Pr D| ·
= 0.999 · 0.001 + 0.001 · 0.999
= 0.001998
(c) Which doctor is more reliable?
Solution,Doctor X makes more than 15 times as many errors as Doctor Y,

3 Recitation 18
Problem 2,A Barglesnort makes its lair in one of three caves,
1 2 3
The Barglesnort inhabits cave 1 with probability
1
2
,cave 2 with probability
1
,and cave 3
4
with probability
1
,A rabbit subsequently moves into one of the two unoccupied caves,
4
selected with equal probability,With probability
1
,the rabbit leaves tracks at the entrance
3
to its cave,(Barglesnorts are much too clever to leave tracks.) What is the probability that
the Barglesnort lives in cave 3,given that there are no tracks in front of cave 2?
Use a tree diagram and the four-step method,
Solution,A tree diagram is given below,Let B
3
be the event that the Barglesnort
inhabits cave 3,and let T
2
be the event that there are tracks in front of cave 2,Taking data
from the tree diagram,we can compute the desired probability as follows,
Pr B
3
| T
2
=
Pr B
3
∩
T
2
Pr T
2
1 1 1
+ +
24 12 12
=
1 1
1?
12
24
5
=
21
In the denominator,we apply the formula Pr T
2
= 1? Pr (T
2
) for convenience,
1
2
3
1
3
3
2
12
Bargle’slair
Rabbit’sholerabbittracks?
noyes
1/2
1/2
1/4
1/4
1/2
1/21/2
1/2
1/2
1/3
1/3
1/3
1/3
1/3
1/32/32/3
2/3
2/3
2/3
2/3
prob.
1/12
1/12
1/6
1/6
1/241/12
1/241/12
1/241/12
1/241/12
Bargle
yesyes
yesyes
in 3?Tracksat 2?yes
yes




4 Recitation 18
Problem 3,There is a deck of cards on the table,Either John or Mary shuf?ed it and we
have no reason to believe in one case more than the other,Now,John is a well-known
cheater with well-known preferences,he always steals the ace of diamonds while shuf-
ing,Mary,on the other hand,is a very honest girl,a deck suf?ed by her is always a full
52-card deck,
(a) You pick the topmost card on the deck and you see a queen of hearts,Before you
do any calculations,Who is more likely to have shuf?ed the deck? Explain,
Solution,A shuf?ing by John strictly increases the fraction of non-aces in the deck,
Hence,between the two worlds,
(1) the world where John has shuf?ed the deck and
(2) the world where Mary has shuf?ed the deck
it is the?rst world rather than the second one that favors the event of the topmost
card being a non-ace,Since we know this event is a fact and the two worlds are
otherwise equally likely,we should bet we live in world (1),
(b) Now calculate,What is the probability that John has shuf?ed the deck? What is
the probability that it has been Mary?
Solution,Let J be the event that John shuf?es the deck and A that the topmost card
is an ace,We want the probabilities
Pr J | A and Pr M | A
Clearly,M = J and therefore Pr M | A = Pr J | A = 1? Pr J A,so that |
we need only calculate the probability about John,By the de?nition of conditional
probability (?rst equation) and then the product rule (on the enumerator) and the
law of total probability (on the denominator),we know

Pr (J)
· Pr A | J
Pr J | A =
Pr J
∩
A
=
Pr (J) Pr A | J + Pr (M) Pr
A M
Pr A · · |
and everything in this last fraction is known,
1 48
1
51
1
51
+
1
52
52 52
= =
52 + 51 103
51
·
2
Pr J | A =
=
1 48 1 48
+
· ·
2 51 2 52
1
2
which is (slightly,but) strictly greater than,as expected,
Like John,Peter is also a well-known cheater,when he shuf?es the deck,he also steals a
card from it; but (unlike John) he steals a random card,That is,every card is equally likely
to be stolen when Peter is shuf?ing,

Recitation 18 5
(c) Suppose you know that Mary shuf?ed the deck and you are about to pick the
topmost card,What is the probability that you will see an ace?
Solution,If we know Mary shuf?ed the deck,we know the deck if a full 52-card
4
deck,So,easily,the probability is,
52
(d) Suppose you know that Peter shuf?ed the deck and you are about to pick the
topmost card,What is the probability that you will see an ace? (Hint,What is this
probability if Peter steals an ace? What if Peter steals a non-ace?)
Solution,Suppose Peter shuf?es the deck,Then there are two cases about what
card he steals,it’s either an ace or a non-ace,Let S
A
be the event that he steals an
ace,Since he steals a card at random,we know he steals an ace with probability
4 48
Pr (S
A
) =
52
and a non-ace with probability Pr S
A
=,
52
Now,as before,let A be the event that the topmost card is an ace,If we know what
case we are in with respect to the stolen card,it is easy to calculate the probability
of A,
3

4
Pr (A | S
A
) = and Pr A | S
A
=
51 51
So,we know the probability in each case and we also know the probability of each
case,This rings the bell of the law of total probability,
4 3 4
4·(3+48)
=
4
Pr (A) = Pr (S
A
)· Pr (A | S
A
)+ Pr S
A
Pr A | S
A
=
52
·
51
+
48
=,
52
·
51 52·51 52
·
4
So the probability that the topmost card is an ace is,
52
(e) Anything strange with the answers to parts (c) and (d)?
Solution,The two answers are identical,In other words,whether the deck is miss-
ing a card or not does not affect the probability that the topmost card is an ace! How
can that be?
Here is an explanation,The situation of part (c) is identical to the following,
we pick the top two cards of a well-shuf?ed 52-card deck;
what is the probability that the?rst card is an ace?
(because the selection of the second card is irrelevant),Similarly,the situation of
part (d) is identical to the following,
we pick the top two cards of a well-shuf?ed 52-card deck;
what is the probability that the second card is an ace?
(because the effect of Peter stealing a card at random and shuf?ing is identical to
the effect of us drawing the topmost card),Now the two situations we have just
introduced are identical,because the number of pairs where the?rst card is an ace
is equal to the number of pairs where the second card is an ace,for obvious reasons
of symmetry,