Mathematics for Computer Science

17.8. Mutual Independence 737

 satisfy the “product rule.” That is,

PrŒA\B\CçDPrŒAç
PrŒBç
PrŒCç;

 but arenotmutually independent.

(a)Describe a trivial example of this by choosingAwith probability zero.

(b)Describe three such events that have nonzero probabilities.

Hint:It may be helpful to draw a Venn diagram forScontaining the three events,
and then incrementally fill in the probabilities of the disjoint regions.

Problem 17.29.
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 walk inGbetweenxandy.

(a)Write a predicate-logic formula definingP.x;y/in terms ofE.x;y/.

For the following parts (b)–(d), letVbe a fixed set ofn > 3vertices, and letGbe a
graph with these vertices constructed randomly as follows: for all distinct vertices
x;y 2 V, independently include edgehx—yias an edge ofGwith probabilityp.
In particular, PrŒE.x;y/çDpfor allx¤y.

(b)For distinct verticesw,x,yandzinV, circle the event pairs that are indepen-
dent.

1.E.w;x/versusE.x;y/

2.ŒE.w;x/AND E.w;y/çversusŒE.z;x/AND E.z;y/ç

3.E.x;y/versusP.x;y/

4.P.w;x/versusP.x;y/

5.P.w;x/versusP.y;z/

(c)Write a simple formula in terms ofnandpfor PrŒNOTP.x;y/ç, for distinct
verticesxandyinV.

Hint:Use part (b), item 2.