Mathematics for Computer Science

17.8. Mutual Independence 723

Hint:Define the eventsS,F, and “F” as follows:

“F”DGuard says Foo-Foo is released

FDFoo-Foo is released

SDSauron is released

Problem 17.8.
Every Skywalker serves either thelight sideor thedark side.

 The first Skywalker serves the dark side.

 Forn 2 , then-th Skywalker serves the same side as the.n1/-st Sky-

walker with probability1=4, and the opposite side with probability3=4.

Letdnbe the probability that then-th Skywalker serves the dark side.

(a)Expressdnwith a recurrence equation and sufficient base cases.

(b)Derive a simple expression for the generating functionD.x/WWD

P 1

1 dnx

n.

(c)Give a simple closed formula fordn.

Problem 17.9. (a)For the directed acyclic graph (DAG)G 0 in Figure 17.3, a
minimum-edge DAG with the same walk relation can be obtained by removing
some edges. List these edges (use notationhu!vifor an edge fromutov):

(b)List the vertices in a maximal chain inG 0.

LetGbe the simple graph shown in Figure 17.4.

A directed graph

!

Gcan be randomly constructed fromGby assigning a direction
to each edge independently with equal likelihood.