Mathematics for Computer Science

Chapter 16 Events and Probability Spaces534

An immediate consequence of the definition of event probability is that fordis-
jointeventsEandF,

PrŒE[FçDPrŒEçCPrŒFç:

This generalizes to a countable number of events, as follows.

Rule 16.4.3(Sum Rule).IffE 0 ;E 1 ;:::gis collection of disjoint events, then

Pr

"

[

n 2 N

En

D

X

n 2 N

PrŒEnç:

The Sum Rule lets us analyze a complicated event by breaking it down into
simpler cases. For example, if the probability that a randomly chosen MIT student
is native to the United States is 60%, to Canada is 5%, and to Mexico is 5%, then
the probability that a random MIT student is native to North America is 70%.
Another consequence of the Sum Rule is that PrŒAçCPrŒAçD 1 , which follows
because PrŒSçD 1 andSis the union of the disjoint setsAandA. This equation
often comes up in the form:

PrŒAçD 1 PrŒAç: (Complement Rule)

Sometimes the easiest way to compute the probability of an event is to compute the
probability of its complement and then apply this formula.
Some further basic facts about probability parallel facts about cardinalities of
finite sets. In particular:

PrŒBAçDPrŒBçPrŒA\Bç, (Difference Rule)

PrŒA[BçDPrŒAçCPrŒBçPrŒA\Bç, (Inclusion-Exclusion)

PrŒA[BçPrŒAçCPrŒBç, (Boole’s Inequality)

IfAB, then PrŒAçPrŒBç. (Monotonicity Rule)

The Difference Rule follows from the Sum Rule becauseBis the union of the
disjoint setsBAandA\B. Inclusion-Exclusion then follows from the Sum
and Difference Rules, becauseA[Bis the union of the disjoint setsAandB
A. Boole’s inequality is an immediate consequence of Inclusion-Exclusion since
probabilities are nonnegative. Monotonicity follows from the definition of event
probability and the fact that outcome probabilities are nonnegative.
The two-event Inclusion-Exclusion equation above generalizes tonevents in
the same way as the corresponding Inclusion-Exclusion rule fornsets. Boole’s
inequality also generalizes to