Mathematics for Computer Science

16.6. References 695

of exactly those components that fail within one year. For example,f2;5gis the
outcome that the second and fifth components failed within a year and none of the
other components failed. So the outcome that the system did not fail corresponds
to the empty set,;.

(a)Show that the probability that the system fails could be as small aspby de-
scribing appropriate probabilities for the outcomes. Make sure to verify that the
sum of your outcome probabilities is 1.

(b)Show that the probability that the system fails could actually be as large asnp
by describing appropriate probabilities for the outcomes. Make sure to verify that
the sum of your outcome probabilities is 1.

(c)Prove inequality (16.8).

Problem 16.9.
Here are some handy rules for reasoning about probabilities that all follow directly
from the Disjoint Sum Rule. Prove them.

PrŒABçDPrŒAçPrŒA\Bç (Difference Rule)

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

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

PrŒA[BçPrŒAçCPrŒBç (2-event Union Bound)

IfAB;then PrŒAçPrŒBç (Monotonicity)

Homework Problems

Problem 16.10.
Prove the following probabilistic inequality, referred to as theUnion Bound.
LetA 1 ;A 2 ;:::;An;:::be events. Then

Pr

"

[

n 2 N

An



X

n 2 N

PrŒAnç:

Hint:Replace theAn’s by pairwise disjoint events and use the Sum Rule.