Mathematics for Computer Science

Chapter 19 Random Processes674

1 a b c

1/2

1/2

1/2

d^1

1/2

Figure 19.5

The student comes out of the final exam located on a particular node of the
graph, corresponding to the exam room. What happens next is unpredictable, as
the student is in a total haze. At each step of the walk, if the student is at node
uat the end of the previous step, they pick one of the edgeshu!viuniformly at
random from the set of all edges directed out ofu, and then walk to the nodev.
LetnWWDjV.G/jand define the vectorP.j/to be

P.j/WWD.p.j/ 1 ;:::;pn.j//

wherepi.j/is the probability of being at nodeiafterjsteps.

(a)We will start by looking at a simple graph. If the student starts at node 1 (the
top node) in the following graph, what isP.0/;P.1/;P.2/? Give a nice expression
forP.n/.

1/2

1/2

1

(b)Given an arbitrary graph, show how to write an expression forp.j/i in terms

of thep.jk1/’s.

(c)Does your answer to the last part look like any other system of equations
you’ve seen in this course?

(d)Let thelimiting distributionvector,, be

lim

k!1

Pk

iD 1 P

.i/

k

: