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?



How much larger than the relaxation time can the mixing time be?
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)$.


