<p>Roughly speaking, the <em>mixing time</em> is the worst-case hitting time of the half the vertices.  <em>Cover time</em> is a stopping time when ALL subsets of vertices are hit.  In other words, it is always larger than the the mixing time.  Thus is your example one cannot have mixing time $n^{1000}$ and cover time $n^2$.  </p>

<p>Making this intuition precise requires a bit of care since we need to relate mixing times to eigenvalue gap, take not half the vertices but half the stationary distribution $\pi$, etc.  None of this is difficult.  Start with <a href="http://www.cs.elte.hu/~lovasz/mixtimes.ps" rel="nofollow">this paper</a> by Lovasz and Winkler, which gives the above version of the mixing time and relates it to more standard mixing time in total variation.  </p>

CC BY-SA 3.0
2013-07-02T10:12:12.947Z
2013-07-02T10:12:12.947Z
Igor Pak
<p>I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, we ignore the smallest eigenvalue of the chain. </p>

<p>The only result I was able to find in this direction is from <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1988.21964">Bounds on the Cover Time</a>, Broder and Karlin, FOCS 88. There it is assumed that the transition matrix of the chain is doubly stochastic (but not necessarily reversible) and aperiodic; roughly speaking, the paper shows that under these assumptions if the cover time is $O(n \log n)$, then $1-\max(|\lambda_2|, |\lambda_n|)$ is at least $n^{-1}$. </p>

<p>Intuitively, it seems very plausible that if you can cover all the vertices of a graph quickly, then mixing time ought to be small. In particular, if you can cover all the vertices of a graph in $n^2$ time, surely you should be able to rule out a spectral gap of, say, $n^{-1000}$? </p>

<p>One possible obstacle that would break the implication between small cover time and large spectral gap is bipartiteness: on a bipartite graph, you can have a small cover time with an eigenvalue of $-1$. By in my question, I am bypassing this issue by ignoring the smallest eigenvalue. </p>

<ds.algorithms><pr.probability><random-walks>
Cover time and spectral gap for reversible random walks
robinson
# Cover time and spectral gap for reversible random walks

(Asked by: username_0 on 2012-05-14)

I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda\_2|$, that is, we ignore the smallest eigenvalue of the chain.

The only result I was able to find in this direction is from [Bounds on the Cover Time](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1988.21964), Broder and Karlin, FOCS 88. There it is assumed that the transition matrix of the chain is doubly stochastic (but not necessarily reversible) and aperiodic; roughly speaking, the paper shows that under these assumptions if the cover time is $O(n \log n)$, then $1-\max(|\lambda\_2|, |\lambda\_n|)$ is at least $n^{-1}$.

Intuitively, it seems very plausible that if you can cover all the vertices of a graph quickly, then mixing time ought to be small. In particular, if you can cover all the vertices of a graph in $n^2$ time, surely you should be able to rule out a spectral gap of, say, $n^{-1000}$?

One possible obstacle that would break the implication between small cover time and large spectral gap is bipartiteness: on a bipartite graph, you can have a small cover time with an eigenvalue of $-1$. By in my question, I am bypassing this issue by ignoring the smallest eigenvalue.

**Tags:** ds.algorithms, pr.probability, random-walks


---

## 1 answers

### Answer by username_1 on 2013-07-02. Score: 4

Roughly speaking, the *mixing time* is the worst-case hitting time of the half the vertices. *Cover time* is a stopping time when ALL subsets of vertices are hit. In other words, it is always larger than the the mixing time. Thus is your example one cannot have mixing time $n^{1000}$ and cover time $n^2$.

Making this intuition precise requires a bit of care since we need to relate mixing times to eigenvalue gap, take not half the vertices but half the stationary distribution $\pi$, etc. None of this is difficult. Start with [this paper](http://www.cs.elte.hu/~lovasz/mixtimes.ps) by Lovasz and Winkler, which gives the above version of the mixing time and relates it to more standard mixing time in total variation.


---

