1
$\begingroup$

It is known fact that for a finite-state, reversible and ergodic Markov chain with transition matrix $M$, the following control on the mixing time holds

$$\left( \frac{1}{\gamma_\star - 1}\right)\ln{2} \leq t_{mix} \leq \frac{\ln(4/\pi_\star)}{\gamma_\star}$$

where $\pi$ is the stationary distribution $\pi M = \pi$, $$\pi_\star = \min_i \pi(i),$$ the mixing time is defined by $$t_{mix} = \min \{t \geq 1 : \sup_{\mu} \|\mu M^{t-1} - \pi\|_{TV} \leq 1/4\},$$ and the absolute spectral gap $$\gamma_\star = 1 - \max \{\lambda_2(M), |\lambda_d(M)|\}.$$

Is the upper bound tight on all the parameters ? Specifically, is the dependence on $\pi_\star$ generally known to be necessary ?

$\endgroup$
1

0

You must log in to answer this question.

Browse other questions tagged .