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.n 1/-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