# Comparing mixing time of lazy and non-lazy Markov chains

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.

• Why do you claim that the stationary distributions are the same? They are not, generally speaking!
– R W
Apr 26 '19 at 22:05
• @RW: As the OP pointed out, if $\pi$ is reversible for the original kernel, it is also reversible for the "non-lazy" version. Apr 27 '19 at 19:29
• @JoshR: with your definition, for $t>t_x(Q,\varepsilon)$, the distribution $Q^t(x,\cdot)$ may again be far from $\pi$, which I guess is not what you want. Note that $\|Q^t(x,\cdot)-\pi\|$ is not monotonic. Apr 27 '19 at 20:25
• @Algernon - This is precisely what is false. The new chain has the transition probabilities $\tilde Q(x,y)=Q(x,y)/(1-Q(x,x))$, and it is reversible with respect to $\pi$ if and only if $Q(x,x)$ is the same for all $x\in X$.
– R W
Apr 28 '19 at 0:39
• @RW: You are right, I was too hasty. And of course it makes sense: if we remove $p$ from $Q(x,x)$ and remove $q<p$ from $Q(y,y)$, we are favoring $y$ over $x$, which means in the long run the chain will spend more time in $y$, hence a bias towards $y$ in the stationary distribution. Apr 28 '19 at 7:33

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. 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 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 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 This proves the claim. $$\quad\square$$

• Thanks for the answer, that certainly helps! Apr 28 '19 at 18:08