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

# 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**.

- Let be a symmetric matrix, whose eigenvalues are . There exist eigenvectors such that for all and are

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
- .

- 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
- .

- 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
- .

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

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