Relaxation time and Mixing time of Markov chains

1.8k Views Asked by At

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 $S$ whose Markov kernel is $K$ and unique stationary distribution is $\pi.$ Then, reversibility means $\pi(x)K(x,y) = \pi(y)K(y,x)$ for all $x,y\in S.$ The Markov kernel $K$ has real eigenvalues given by:

$$-1\leq \beta_{|S|-1}\leq \ldots \leq \beta_1 \leq \beta_0 = 1.$$

Define the spectral gap as $\gamma(K):=1-\max\{\beta_1,|\beta_{|S|-1}|\}.$

The relaxation time of the Markov chain is defined as: $t_{\mathrm{rel}}:=\frac{1}{\gamma}.$

Let $d(t) = \sup_\mu ||\mu K^t - \pi||_{\mathrm{TV}}$ where $\mathrm{TV}$ is the total variation distance. Then, the mixing time is defined as

$$t_{\mathrm{mix}}(\epsilon):=\min\{t: d(t)\leq \epsilon\}.$$

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)}~.$$

Observe that if $K(x,y) = \pi(y)$ for all $x,y,$ we have the lower bound almost tight since $t_{\mathrm{rel}}=t_{\mathrm{mix}}(\epsilon)=1.$ Note that this is true no matter how small $\min_x\pi(x)$ is.

Also, observe that if the Markov chain is simply a random walk on a 3-regular expander graph, then $t_{\mathrm{rel}}$ is a constant, but $t_{\mathrm{mix}}$ is $\Theta(\log|S|)$ since $\Theta(\log|S|)$ is the diameter of the graph. In this case, $\min_x\pi(x) = \frac{1}{|S|}$ and so, the upper bound gives the right behavior of $t_{\mathrm{mix}}(\epsilon).$

My question is the following:

For a fixed size of state space $|S|,$ and a fixed value of spectral gap $\gamma,$ hence also a fixed value of $t_{\mathrm{rel}},$ can we have the upper bound on $t_{\mathrm{mix}}(\epsilon)$ close to being tight for arbitrarily small values of $\min_x\pi(x)$?

Intuitively, I expect the answer to be No. If a chain has a fixed positive spectral gap, I expect the chain to mix quickly. But if $\min_x\pi(x)$ is very tiny, the upper bound suggests a potentially large mixing time.