Comparing mixing time of lazy and non-lazy Markov chains

Question

Suppose we have a probability distribution $\pi : X \rightarrow [0,1]$ where $X$ is finite and let $Q : X \times X \rightarrow [0,1]$ be a Markov kernel that is reversible with respect to $\pi$. That is,

$$\pi(x) Q(x,y) = \pi(y) Q (y,x) $$

for all $x,y \in X$. Suppose we know the mixing time $t_x(Q, \varepsilon)$ of $Q$ to $\pi$ when started at $x$, defined as

$$ t_x(Q, \varepsilon) = \min \{ t \in \mathbb{N} : || Q^t(x, \cdot) - \pi ||_1 \leq \varepsilon \}. $$

Question: what can be said about the mixing time of the non-lazy version of this kernel?

That is, we can define $\tilde{Q}(x,y) = 0$ if $x=y$, and $\tilde{Q}(x,y)\propto Q(x,y)$ otherwise. Clearly $\tilde{Q}$ is still reversible with respect to $\pi$ and so has the same stationary distribution. So we can consider $t_x(\tilde{Q}, \varepsilon)$ and ask whether it is smaller (and by how much) than $t_x(Q, \varepsilon)$.

If anyone knew how to compare the two chains spectral gaps or log-Sobolev constants I would be particularly interested in that.

Motivation: I have a distribution $\pi$ and a Markov kernel $Q$ that mixes to $\pi$ quite slowly. However $Q $ is very often lazy, i.e. $Q(x,x)$ is close to $1$ for most $x$'s. I was hoping that there might be a way to show that the non-lazy version of my kernel mixes faster.

Answer 1

Edit [following the comment by R W]: As R W pointed out, the stationary distribution may change if you remove the laziness as you suggested. Still your motivation makes sense: can making the chain less lazy reduce the mixing significantly faster? What I wrote below answers that.

---

The "non-lazy version" of an aperiodic Markov kernel is not always aperiodic, so the convergence may fail.

Still for your motivation, you could ask whether "less-lazy versions" of $Q$ mix significantly faster. I don't have a general answer, but I argue that at least the simplest form of "non-lazification" does not help beyond the obvious linear speed-up. Below, I use the better definition \begin{align*} t_x(Q,\varepsilon) &:= \min\{t_0\in\mathbb{N}: \text{$\|Q^t(x,\cdot)-\pi\|<\varepsilon$ for all $t\geq t_0$} \} \;. \end{align*}

Let $\hat{Q}$ be another irreducible and aperiodic Markov kernel with the property that \begin{align*} Q(x,y) &= p\hat{Q}(x,y)+(1-p)1_x(y) \end{align*} for some $0<p<1$. This is a simple "less-lazy version" of $Q$. The evolutions of $Q$ and $\hat{Q}$ can be coupled in a natural way as follows: let $\hat{Z}_0,\hat{Z}_1,\ldots$ be a Markov chain with kernel $\hat{Q}$ and let $B_1,B_2,\ldots$ be a sequence of independent Bernoulli random variables with $\mathbb{P}(B_k=1)=p$ and independent of $\hat{Z}_0,\hat{Z}_1,\ldots$. Let $N_t:=B_1+B_2+\cdots+B_t$. Define $Z_t:= \hat{Z}_{N_t}$. It is clear that $Z_0,Z_1,\ldots$ is a Markov chain with kernel $Q$.

Lemma. Let $0<\varepsilon,\delta<1$ be arbitrary. Then, for $t\geq\frac{1}{2\delta^2}\log\frac{1}{\varepsilon}$, we have $\mathbb{P}\big(N_t<(p-\delta)t\big)<\varepsilon$.

Proof. This is just rewriting Hoeffding's inequality. $\quad\square$.

Proposition. Let $0<\delta<p$ and $0<\gamma<1$ be arbitrary. Then, for every $0<\varepsilon<1$, we have \begin{align*} t_x(Q,(1+\gamma)\varepsilon) &\leq \max\left(\frac{1}{p-\delta}t_x(\hat{Q},\varepsilon), \frac{1}{2\delta^2}\log\frac{1}{\gamma\varepsilon}\right) \;. \end{align*} So, choosing $\delta$ and $\gamma$ to be small, and ignoring the second term on the right-hand side (which is independent of the size of the state space), we find that the mixing time of $\hat{Q}$ is no less than about $p$ times the mixing time of $Q$. This is the linear speed-up one would expect.

Proof. Let $n_0$ be such that \begin{align*} \|\hat{Q}^n(x,\cdot)-\pi\| &< \varepsilon \end{align*} for every $n\geq n_0$. Let $t_0:=\max(\frac{n_0}{p-\delta}, \frac{1}{2\delta^2}\log\frac{1}{\gamma\varepsilon})$. According to the above lemma, $\mathbb{P}(N_t<n_0)\leq\gamma\varepsilon$ for all $t\geq t_0$. Note that \begin{align*} Q^t(x,y) &= \sum_{n=0}^\infty\mathbb{P}(N_t=n)\hat{Q}^n(x,y) \;. \end{align*} Therefore, for every $t\geq t_0$, \begin{align*} \|Q^t(x,\cdot)-\pi\| &< \|\sum_n\mathbb{P}(N_t=n)\hat{Q}^n(x,\cdot) - \pi\| \\ &\leq \sum_{n<n_0}\mathbb{P}(N_t=n)\underbrace{\|\hat{Q}^n(x,\cdot) - \pi\|}_{\leq 1} + \sum_{n\geq n_0}\mathbb{P}(N_t=n)\underbrace{\|\hat{Q}^n(x,\cdot) - \pi\|}_{\leq\varepsilon} \\ &\leq \mathbb{P}(N_t<n_0) + \varepsilon \\ &\leq (1+\gamma)\varepsilon \;. \end{align*} This proves the claim. $\quad\square$