Mathematics for Computer Science

16.7. The Birthday Principle 559

(a)What is PrŒGPç?.... Pr



OP

ˇ

ˇGP?.

(b)What is PrŒOPç?

(c)LetRbe the number of times the game is restarted before Carol picks a goat.

What is ExŒRç? You may express the answer as a simple closed form in terms of
pWWDPrŒOPç.

(d)What is the probability the game will continue forever?

(e)When Carol finally picks the goat, the contestant has the choice of sticking or
switching. Let’s say that the contestant adopts the strategy of sticking. LetW be
the event that the contestant wins with this strategy, and letwWWDPrŒW ç. Express
the following conditional probabilities as simple closed forms in terms ofw.

i) Pr



W jGP



D

ii) Pr



W

ˇˇ

GP\OP



D

iii) Pr



W

ˇˇ

GP\OP



D

(f)What is PrŒW ç?

(g)For any final outcome where the contestant wins with a “stick” strategy, he
would lose if he had used a “switch” strategy, and vice versa. In the original Monty
Hall game, we concluded immediately that the probability that he would win with
a “switch” strategy was 1 PrŒW ç. Why isn’t this conclusion quite as obvious for
this new, restartable game? Is this conclusion still sound? Briefly explain.

Problem 16.3.
Graphs, Logic & Probability
LetGbe an undirected simple graph withn > 3vertices. LetE.x;y/mean that
Ghas an edge between verticesxandy, and letP.x;y/mean that there is a length
2 path inGbetweenxandy.

(a)Explain whyE.x;y/impliesP.x;x/.

(b)Circle the mathematical formula that best expresses the definition ofP.x;y/.

P.x;y/WWD9z: E.x;z/AND E.y;z/

P.x;y/WWDx¤yAND 9 z: E.x;z/ANDE.y;z/