1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.