Discrete Mathematics for Computer Science

512 CHAPTER 8 Discrete Probability

In other words, the probability of B is not affected by the fact that A has occurred. In

fact, the satisfaction of the condition P(A I B) = P(A) can be regarded as an alternate

definition for the independence of a pair of non-empty events A and B.

To further our understanding of the connections between conditional probability and

the independence of events, let us revisit the notion of nonempty disjoint events. Con-

sider two such events A and B on the same sample space 02. We known P (A) > 0 and

P(B) > 0. It follows immediately from the definition of independence that A and B are

not independent, because

0 = P(A n B) # P(A) .P(B) > 0

We can look at this a second way. Learning that event B, say, occurred tells us a lot about

A-namely, that A definitely did not occur (the events are disjoint after all). This phe-

nomenon can be expressed as

P(A nB)

P(AIB) = P(B)

8.5.3 Exploring Conditional Probability

Note that the expression in Definition 3 for conditional probability can be rearranged to the

form

P(B n A) = P(A) .P(B I A)

In this subsection, we take advantage of this observation to obtain two further results, called

Bayes' Rule and the Theorem of Total Probability. These two results, which are often used

together, provide powerful tools for computing probabilities, as we shall see.

Let us begin with the Theorem of Total Probability, which is perhaps the easier result

to understand.

Theorem 1. (Total Probability) Let sample space 0 be the disjoint union of events

E ..... E with positive probabilities, and let A C Q2. Then,

n

P(A)=E P(A I Ei) .P(E)

i=1

Proof. Event A can be expressed as a union of disjoint events as follows:

A=(A n E 1 )U ... U (A n E,)

Hence,

n

P(A) - E P(A n Ei)

i=1

From the definition of conditional probability,

P(A n Ei) = P(A I Ei) " P(Ei)

Substituting the right side of this expression for P(A n Ei) in the expression for P(A)

gives the result. 0