Robert_V._Hogg,_Joseph_W._McKean,_Allen_T._Craig

20 Probability and Distributions

Theorem 1.3.5 gave a general additive law of probability for the union of two
events. As the next remark shows, this can be extended to an additive law for an
arbitrary union.

Remark 1.3.2(Inclusion Exclusion Formula).It is easy to show (Exercise 1.3.9)
that
P(C 1 ∪C 2 ∪C 3 )=p 1 −p 2 +p 3 ,

where

p 1 = P(C 1 )+P(C 2 )+P(C 3 )

p 2 = P(C 1 ∩C 2 )+P(C 1 ∩C 3 )+P(C 2 ∩C 3 )

p 3 = P(C 1 ∩C 2 ∩C 3 ). (1.3.12)

This can be generalized to theinclusion exclusion formula:

P(C 1 ∪C 2 ∪···∪Ck)=p 1 −p 2 +p 3 −···+(−1)k+1pk, (1.3.13)

wherepiequals the sum of the probabilities of all possible intersections involvingi
sets.
Whenk= 3, it follows thatp 1 ≥p 2 ≥p 3 , but more generallyp 1 ≥p 2 ≥···≥pk.
As shown in Theorem 1.3.7,

p 1 =P(C 1 )+P(C 2 )+···+P(Ck)≥P(C 1 ∪C 2 ∪···∪Ck).

Fork=2,wehave

1 ≥P(C 1 ∪C 2 )=P(C 1 )+P(C 2 )−P(C 1 ∩C 2 ),

which givesBonferroni’s inequality,

P(C 1 ∩C 2 )≥P(C 1 )+P(C 2 )− 1 , (1.3.14)

that is only useful whenP(C 1 )andP(C 2 ) are large. The inclusion exclusion formula
provides other inequalities that are useful, such as

p 1 ≥P(C 1 ∪C 2 ∪···∪Ck)≥p 1 −p 2

and
p 1 −p 2 +p 3 ≥P(C 1 ∪C 2 ∪···∪Ck)≥p 1 −p 2 +p 3 −p 4.

EXERCISES

1.3.1.A positive integer from one to six is to be chosen by casting a die. Thus the

elementscof the sample spaceCare 1, 2 , 3 , 4 , 5 ,6. SupposeC 1 ={ 1 , 2 , 3 , 4 }and

C 2 ={ 3 , 4 , 5 , 6 }. If the probability set functionPassigns a probability of^16 to each

of the elements ofC, computeP(C 1 ),P(C 2 ),P(C 1 ∩C 2 ), andP(C 1 ∪C 2 ).