Mathematics for Computer Science

16.7. The Birthday Principle 565

be an event such that PrŒBç > 0. Define a function PrBf
gon outcomesw 2 Sby
the rule:

PrBf!gWWD

(

PrŒ!ç=PrŒBç if! 2 B;

0 if!...B:

(16.12)

(a)Prove that PrBf
gis also a probability function onSaccording to Defini-
tion 16.4.2.

(b)Prove that

PrBfAgD

PrŒA\Bç

PrŒBç

for allAS.

Homework Problems

Problem 16.12.
Prove the following probabilistic identity, referred to as theUnion Bound. You
may assume the theorem that the probability of a union ofdisjointsets is the sum
of their probabilities.
LetA 1 ;:::;Anbe a collection of events. Then

PrŒA 1 [A 2 [


[Anç

Xn

iD 1

PrŒAiç:

Hint:Induction.

Problems for Section 16.5

Exam Problems

Problem 16.13.
There are two decks of cards, the red deck and the blue deck. They differ slightly
in a way that makes drawing the eight of hearts slightly more likely from the red
deck than from the blue deck.
One of the decks is randomly chosen and hidden in a box. You reach in the
box and randomly pick a card that turns out to be the eight of hearts. You believe
intuitively that this makes the red deck more likely to be in the box than the blue
deck.
Your intuitive judgment about the red deck can be formalized and verified using
some inequalities between probabilities and conditional probabilities involving the