3
$\begingroup$

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.

Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite state space. The relaxation time $t_{\mathrm{rel}}$ is the reciprocal of the absolute spectral gap. The $\epsilon$-mixing time $t_{\mathrm{mix}}(\epsilon)$ is the shortest time in which, regardless of any initialization, the state becomes $\epsilon$-close to the stationary distribution in the total variation sense. The two are related as:

Levin-Peres-Wilmer (Theorem 12.3, 12.4) $$(t_{\mathrm{rel}}-1)\log\frac{1}{2\epsilon}\leq t_{\mathrm{mix}}(\epsilon)\leq t_{\mathrm{rel}}\log\frac{1}{\epsilon\min_x\pi(x)}~,$$ where $\min_x\pi(x)$ is the smallest atom of the stationary distribution.

If the Markov chain is a random walk on a 3-regular expander graph, then $t_{\mathrm{rel}}$ is a constant, but $t_{\mathrm{mix}} = \Theta(\log n)$ if the graph has $n$ vertices. Thus, the upper bound here better describes the behavior of the mixing time relative to the relaxation time, since $\pi(x) = \frac 1n$ for all $x.$

My question is: How large can the ratio $\frac{t_{\mathrm{mix}}(1/8)}{t_{\mathrm{rel}}}$ be? From above theorem, it is at most $\log\frac{8}{\min_x\pi(x)},$ but can it indeed be as large as this when $\min_x \pi(x)$ may be very very tiny? I conjecture that

$$\frac{t_{\mathrm{mix}}(1/8)}{t_{\mathrm{rel}}}\leq O(\log n)~.$$

Any proofs or counterexamples?

$\endgroup$

2 Answers 2

4
$\begingroup$

The conjecture fails even in the simple case of biased random walk on a path of length $n$. Suppose that the probabilities to go right and left are $1/4$ and $1/2$ respectively; with the remaining probability the particle stays in place (At the endpoints the probability to stay in place is larger, as moves outside the path are not permitted.) Then this Markov chain is a (weighted) expander, the relaxation time is $O(1)$, yet the mixing time is $\Theta (n)$.

$\endgroup$
1
$\begingroup$

This paper shows that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}}\log t_{\mathrm{rel}})$ for all Markov chains and that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}})$ for reversible chains. The conjecture in the question is false since it's shown that $t_{\mathrm{mix}}$ can be as large as $kt_{\mathrm{rel}}.$

http://arxiv.org/abs/1310.8021

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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