6
$\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$
  • $\begingroup$ You can probably assume that $\pi(x) \ge \varepsilon/n$, because the probability mass of $\{x: \pi(x) \le \varepsilon/n\}$ is at most $\varepsilon$. So there should be some argument that allows you to ignore that part of the probability space, although I haven't thought about the details. $\endgroup$ – Sasho Nikolov Aug 4 '15 at 16:11
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, privacy policy and cookie policy

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