<p>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}}.$</p>

<p><a href="http://arxiv.org/abs/1310.8021" rel="nofollow">http://arxiv.org/abs/1310.8021</a></p>

CC BY-SA 3.0
2016-01-02T21:08:18.743Z
2016-01-02T21:08:18.743Z
user7823
<p>The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.</p>

<p>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:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.$</p>

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

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

<p>Any proofs or counterexamples?</p>

CC BY-SA 3.0
2015-08-04T16:11:35.763Z
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.
Sasho Nikolov
<markov-chains>
How much larger than the relaxation time can the mixing time be?
user7823
# How much larger than the relaxation time can the mixing time be?

(Asked by: username_0 on 2015-08-04)

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?

**Tags:** markov-chains
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2016-01-02. Score: 1

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>


---

