5
$\begingroup$

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.

  • 0
    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.2011-08-09
  • 0
    @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!2011-08-09
  • 0
    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.2011-08-10
  • 0
    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$.2011-08-10
  • 0
    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.2011-08-10
  • 0
    Out of curiosity, how would you bound the error in the approximation of eigenvalues introduced by going from line to ring?2011-08-10
  • 0
    I don't know, but I'm pretty sure it's possible. There ought to be results along the following lines: if $A$ is a matrix and $B$ is a matrix small in some appropriate norm, then the largest eigenvalues of $A + B$ are close to the largest eigenvalues of $A$.2011-08-10
  • 0
    I agree that such results exist; however, the problem is that changing even one entry from $0$ to $1/2$ cannot be small in any "appropriate norm." This is because the lower shift - with all eigenvalues of zero - can be changed into a circular shift by changing a single entry from $0$ to $1$ - changing all eigenvalues to roots of unity.2011-08-10
  • 0
    Hmm. Okay, how about a symmetry argument? Let's look at the original Markov chain, except that whenever we hit an end and stay there, we have to reflect the chain across the center. That's equivalent to looking at the modified Markov chain. After $n^2$ steps, the parity of the number of reflections should be evenly distributed.2011-08-10
  • 0
    Would you mind giving a more detailed sketch? I've tried to reconstruct your argument, and here is where I am. So you can argue that after $o(n^2)$ steps, the markov chain on the ring is too concentrated around its starting point to be close to the stationary distribution. This means the modified markov chain you describe has the same property. Now we want to argue this for the markov chain on the line. Unfortunately, the line includes some sample paths that the others do not (and vice versa) - for example, reaching the endpoint, staying there for two steps, then coming back to the start...2011-08-10
  • 0
    ...and i think yo uwant to argue that after, say, $n^{1.99}$ steps, the number of reflections is as likely to be odd as even. But I don't see what the next step is.2011-08-10
  • 0
    I don't have an argument! Just tossing out ideas. I guess what I'm saying is that the symmetry argument strongly suggests that the two graphs have the same mixing time, and you can apply CLT to the circle graph, but I don't know much about the rate of convergence of CLT.2011-08-10

1 Answers 1