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. 



Comparing mixing time of lazy and non-lazy Markov chains
**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](https://en.wikipedia.org/wiki/Hoeffding%27s_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$


