Mathematics for Computer Science

20.2. Random Walks on Graphs 857

Problem 20.6.
Asinkin a digraph is a vertex with no edges leaving it. Circle whichever of the
following assertions are true of stable distributions on finite digraphs with exactly
two sinks:

 there may not be any

 there may be a unique one

 there are exactly two

 there may be a countably infinite number

 there may be a uncountable number

 there always is an uncountable number

Problem 20.7.
Explain why there are an uncountable number of stationary distributions for the
following random walk graph.

1 a b c

1/2

1/2

1/2

d^1

1/2

Class Problems

Problem 20.8. (a)Find a stationary distribution for the random walk graph in Fig-
ure 20.6.

x y

1

1

Figure 20.6