Mathematics for Computer Science

Chapter 20 Random Walks856

x y

1

1

Figure 20.3

w z

1

0.9

0.1

Figure 20.4

1 a b c

1/2

1/2

1/2

d^1

1/2

Figure 20.5

(a)Findd.x/for a stationary distribution for graph 20.3.

(b)Findd.y/for a stationary distribution for graph 20.3.

(c)If you start at nodexin graph 20.3 and take a (long) random walk, does the
distribution over nodes ever get close to the stationary distribution?

(d)Findd.w/for a stationary distribution for graph 20.4.

(e)Findd.z/for a stationary distribution for graph 20.4.

(f)If you start at nodewin graph 20.4 and take a (long) random walk, does the
distribution over nodes ever get close to the stationary distribution? (Hint:try a
few steps and watch what is happening.)

(g)How many stationary distributions are there for graph 20.5?

(h)If you start at nodebin graph 20.5 and take a (long) random walk, what will
be the approximate probability that you are at noded?