随机算法 (Fall 2011)/Random Walk on Expander Graph

From EtoneWiki
Jump to: navigation, search

Spectral approach for symmetric chain

We consider the symmetric Markov chains defined on the state space , where the transition matrix is symmetric.

We have the following powerful spectral theorem for symmetric matrices.

Theorem (Spectral theorem)
Let be a symmetric matrix, whose eigenvalues are . There exist eigenvectors such that for all and are orthonormal.

A set of orthonormal vectors satisfy that

  • for any , is orthogonal to , which means that , denoted ;
  • all have unit length, i.e., .

Since the eigenvectors are orthonormal, we can use them as orthogonal basis, so that any vector can be expressed as where , therefore

So multiplying by corresponds to multiplying the length of along the direction of every eigenvector by a factor of the corresponding eigenvalue.


Back to the symmetric Markov chain. Let be a finite state space of size , and be a symmetric transition matrix, whose eigenvalues are . The followings hold for a symmetric transition matrix :

  • Due to the spectral theorem, there exist orthonormal eigenvectors such that for and any distribution over can be expressed as where .
  • A symmetric must be double stochastic, thus the stationary distribution is the uniform distribution.

Recall that due to Perron-Frobenius theorem, . And since is double stochastic, thus .

When is a distribution, i.e., is a nonnegative vector and , it holds that and , thus

and the distribution at time when the initial distribution is , is given by

It is easy to see that this distribution converges to when the absolute values of are all less than 1. And the rate at which it converges to , namely the mixing rate, is determined by the quantity , which is the largest absolute eigenvalues other than .

Theorem
Let be the transition matrix for a symmetric Markov chain on state space where . Let be the spectrum of and . The mixing rate of the Markov chain is
.
Proof.

As analysed above, if is symmetric, it has orthonormal eigenvectors such that any distribution over can be expressed as

with , and

Thus,

The last inequality is due to a universal relation and the fact that is a distribution.

Then for any , denoted by the indicator vector for such that and for , we have

Therefore, we have

for any , thus the bound holds for .

Rapid mixing of expander walk

Let be a -regular graph on vertices. Let be its adjacency matrix. The transition matrix of the lazy random walk on is given by . Specifically,

Obviously is symmetric.

Let be the eigenvalues of , and be the eigenvalues of . It is easy to verify that

.

We know that , thus . Therefore, . Due to the above analysis of symmetric Markov chain,

.

Thus we prove the following theorem for lazy random walk on -regular graphs.

Theorem
Let be a -regular graph on vertices, with spectrum . The mixing rate of lazy random walk on is
.

Due to Cheeger's inequality, the spectral gap is bounded by expansion ratio as

where is the expansion ratio of the graph . Therefore, we have the following corollary which bounds the mixing time by graph expansion.

Corollary
Let be a -regular graph on vertices, whose expansion ratio is . The mixing rate of lazy random walk on is
.
In particular, the mixing time is
.

For expander graphs, both and are constants. The mixing time of lazy random walk is so the random walk is rapidly mixing.