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?
