1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why do you claim that the stationary distributions are the same? They are not, generally speaking! $\endgroup$ – R W Apr 26 at 22:05
  • $\begingroup$ @RW: As the OP pointed out, if $\pi$ is reversible for the original kernel, it is also reversible for the "non-lazy" version. $\endgroup$ – Algernon Apr 27 at 19:29
  • $\begingroup$ @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. $\endgroup$ – Algernon Apr 27 at 20:25
  • 2
    $\begingroup$ @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$. $\endgroup$ – R W Apr 28 at 0:39
  • $\begingroup$ @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. $\endgroup$ – Algernon Apr 28 at 7:33
1
$\begingroup$

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) &= \varepsilon\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$

$\endgroup$
  • $\begingroup$ Thanks for the answer, that certainly helps! $\endgroup$ – Josh R Apr 28 at 18:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.