Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the following $n \times n$ matrix $$ \left( \begin{matrix} 1/2 & 1/2 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 & 0 \\ \vdots & \ & \ddots & & \ddots & \\ 0 & \cdots & 0 & 1/2 & 0 & 1/2 \\ 0 & \cdots & 0 & 0 & 1/2 & 1/2 \end{matrix} \right) $$

It has its largest eigenvalue at $1$, and the gap between $1$ and the second largest eigenvalue is on the order of $1/n^2$. The other day, someone offered me the following heuristic argument for why, for large $n$, this gap cannot be larger than $c/n^2$ for some constant $c>0$:

This is the transition matrix of a Markov chain on $n$ nodes which, except at the endpoints, moves left and right with equal probability. Its stationary distribution is uniform. Now the second eigenvalue measures the time until you get close to the stationary distribution, and observe that by the central limit theorem, as $n$ gets large, a particle which begins at the midpoint will take on the order of $n^2$ steps until it puts a constant probability on order of $n$ nodes. Consequently, the gap cannot be larger than on the order of $1/n^2$.

Intuitively, this makes sense. I would like to ask:

Question: Is there a way to make the above argument rigorous?

One difficulty is that the smallest eigenvalue also affects mixing time, but we can perhaps get rid of this difficulty by taking a convex combination with the identity. A more serious problem seems to be the boundary effects, but perhaps one can argue that they "go away" as $n \rightarrow \infty$. I'm not sure how to argue any of this, and I'd be very interested in seeing a formalization of this argument.

share|improve this question
    
Sure. Modify the Markov chain so that the endpoints transition to each other, so you can actually apply the central limit theorem, then bound the error in this approximation. –  Qiaochu Yuan Aug 9 '11 at 23:52
    
@Qiaochu Yuan, would you be willing to write this argument down formally for me? I'm not sure a) what happens to the eigenvalues when you make the endpoints transition to each other b) how one can apply the central limit theorem to the random walk on the ring. Thank you! –  robinson Aug 9 '11 at 23:59
    
Sorry, but it sounds like a pain (I don't know enough Markov chain theory to do it elegantly). I would do this problem somewhat differently: the modified Markov chain I describe has nice symmetry properties that allow you to write down its eigenvalues explicitly, and then directly bounding the error in the approximation of eigenvalues (as opposed to bounding the error in the approximation of the mixing time or whatever) seems not so bad. –  Qiaochu Yuan Aug 10 '11 at 0:03
    
As for the central limit theorem, a random walk on a finite circle is just a sum of i.i.d. Bernoulli random variables, except that the output is taken $\bmod n$. –  Qiaochu Yuan Aug 10 '11 at 0:05
    
Right - I am aware that its not hard to prove the gap of $1/n^2$ directly by, e.g., exhibiting an eigenvector with that gap. I'm interested in whether this method can be made to work. –  robinson Aug 10 '11 at 0:06

1 Answer 1

Not an answer to your question, but this Markov chain is analyzed in Example 12.10 (p. 159) of Markov Chains and Mixing Times by Levin, Peres, and Wilmer. The authors show that the eigenvalues are $\cos(\pi j/n)$ for $0\leq j <n$.

Hence the spectral gap is $1-\cos(\pi/n)=\pi^2/2n^2+O(n^{-4})$.

They start with the random walk on the circle, which is regarded as taking values among the $n$th roots of unity in the complex plane. Here it is relatively straightforward to find the eigenfunctions.

The walk with boundary conditions is obtained by a transformation of the walk on the circle, and the eigenfunctions drop out as well.

share|improve this answer
    
thanks for the pointer! –  robinson Aug 10 '11 at 2:11
    
You're welcome; I wish I could have been of more help. The LPW book is excellent and discusses relationships between several metrics for speed of convergence to equilibrium: hitting times, mixing time, relaxation time, spectral gap, etc. Someone who knows this stuff better than me may give you a precise answer. –  Byron Schmuland Aug 10 '11 at 3:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.