Chapter 19 Random Processes676
A directed graph issymmetricif, wheneverhv!wiis an edge, so ishw!vi.
Given any finite, symmetric Google-graph, letd.v/WWDout-degree.v/
e;
whereeis the total number of edges in the graph. Show thatd is a stationary
distribution.
Homework Problems
Problem 19.5.
A digraph isstrongly connectediff there is a directed path between every pair of
distinct vertices. In this problem we consider a finite random walk graph that is
strongly connected.
(a)Letd 1 andd 2 be distinct distributions for the graph, and define themaximum
dilation, , ofd 1 overd 2 to be
WWDmax
x 2 Vd 1 .x/
d 2 .x/:
Call a vertex,x,dilatedifd 1 .x/=d 2 .x/D. Show that there is an edge,hy!zi,
from an undilated vertexyto a dilated vertex,z.Hint:Choose any dilated vertex,
x, and consider the set,D, of dilated vertices connected toxby a directed path
(going tox) that only uses dilated vertices. Explain whyD¤V, and then use the
fact that the graph is strongly connected.
(b)Prove that the graph hasat most onestationary distribution. (There alwaysis
a stationary distribution, but we’re not asking you prove this.) Hint:Letd 1 be a
stationary distribution andd 2 be a different distribution. Letzbe the vertex from
part (a). Show that starting fromd 2 , the probability ofzchanges at the next step.
That is,db 2 .z/¤d 2 .z/.
Exam Problems
Problem 19.6.
For which of the graphs in Figure 19.6 is the uniform distribution over nodes a
stationary distribution? The edges are labeled with transition probabilities. Explain
your reasoning.