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

4

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 .

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.

  • 0
    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.2011-08-10