Mathematics for Computer Science

Chapter 16 Events and Probability Spaces546

Theorem 16.5.2(Bayes’ Rule).IfPrŒAçandPrŒBçare nonzero, then:

Pr



BjA



D

Pr



AjB



PrŒBç

PrŒAç

(16.5)

Proof. When PrŒAçand PrŒBçare nonzero, we have

Pr



AjB



PrŒBçDPrŒA\BçDPr



BjA



PrŒAç

by definition of conditional probability. Dividing by PrŒAçgives (16.5). 

16.5.6 The Law of Total Probability

Breaking a probability calculation into cases simplifies many problems. The idea
is to calculate the probability of an eventAby splitting into two cases based on
whether or not another eventEoccurs. That is, calculate the probability ofA\E
andA\E. By the Sum Rule, the sum of these probabilities equals PrŒAç. Express-
ing the intersection probabilities as conditional probabilities yields:

Rule 16.5.3(Law of Total Probability, single event).IfPrŒEçandPrŒEçare nonzero,
then
PrŒAçDPr



AjE



PrŒEçCPr



A

ˇ

ˇE



PrŒEç:

For example, suppose we conduct the following experiment. First, we flip a fair
coin. If heads comes up, then we roll one die and take the result. If tails comes up,
then we roll two dice and take the sum of the two results. What is the probability
that this process yields a 2? LetEbe the event that the coin comes up heads,
and letAbe the event that we get a 2 overall. Assuming that the coin is fair,
PrŒEçDPrŒEçD1=2. There are now two cases. If we flip heads, then we roll
a 2 on a single die with probability Pr



AjE



D1=6. On the other hand, if we
flip tails, then we get a sum of 2 on two dice with probability Pr



A

ˇ

ˇED1=36.

Therefore, the probability that the whole process yields a 2 is

PrŒAçD

1

2

1

6

C

1

2

1

36

D

7

72

:

There is also a form of the rule to handle more than two cases.

Rule 16.5.4(Law of Total Probability).IfE 1 ;:::;Enare disjoint events whose
union is the whole sample space, then:

PrŒAçD

Xn

iD 1

Pr



AjEi



PrŒEiç: