随机算法 (Fall 2011)/Random Walks on Undirected Graphs

From EtoneWiki
Jump to: navigation, search

A walk on a graph is a sequence of vertices such that is a neighbor of for every index . When is selected uniformly at random from among ’s neighbors, independently for every , this is called a random walk on .

We consider the special case that is an undirected graph, and denote that and .

A Markov chain is defined by this random walk, with the vertex set as the state space, and the transition matrix , which is defined as follows:

where denotes the degree of vertex .

Note that unlike the PageRank example, now the probability depends on instead of . This is because the graph is undirected.

Proposition
Let be the Markov chain defined as above.
  • is irreducible if and only if is connected.
  • is aperiodic if and only if is non-bipartite.

We leave the proof as an exercise.

We can just assume is connected, so we do not have to worry about the reducibility any more.

The periodicity of a random walk on a undirected bipartite graph is usually dealt with by the following trick of "lazy" random walk.

Lazy random walk
Given an undirected graph , a random walk is defined by the transition matrix
For this random walk, at each step, we first flip a fair coin to decide whether to move or to stay, and if the coin told us to move, we pick a uniform edge and move to the adjacent vertex. It is easy to see that the resulting Markov chain is aperiodic for any .

We consider the non-lazy version of random walk. We observe that the random walk has the following stationary distribution.

Theorem
The random walk on with has a stationary distribution , where ,
for .
Proof.
First, since , it follows that

thus is a well-defined distribution. And let denote the set of neighbors of . Then for any ,

Thus , and is stationary.

For connected and non-bipartite , the random walk converges to this stationary distribution. Note that the stationary distribution is proportional to the degrees of the vertices, therefore, if is a regular graph, that is, is the same for all , the stationary distribution is the uniform distribution.

The following parameters of random walks are closely related to the performances of randomized algorithms based on random walks:

  • Hitting time: It takes how long for a random walk to visit some specific vertex.
  • Cover time: It takes how long for a random walk to visit all vertices.
  • Mixing time: It takes how long for a random walk to be close enough to the stationary distribution.