随机算法 (Fall 2011)/Random Walks on Undirected Graphs
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.
- Let be the Markov chain defined as above.
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 .
- The random walk on with has a stationary distribution , where ,
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.