# Show that the total variation distance of the Metropolis kernel to its proposal kernel is equal to the rejection probability

Furthermore, let

• $$(E,\mathcal E,\lambda)$$ be a $$\sigma$$-finite measure space;
• $$Q$$ be a Markov kernel on $$(E,\mathcal E)$$ with density $$q$$ with respect to $$\lambda$$;
• $$\mu$$ be a probability measure on $$(E,\mathcal E)$$ with density $$p$$ with respect to $$\lambda$$
• $$\alpha(x,y):=\left.\begin{cases}\min\left(1,\displaystyle\frac{p(y)q(y,x)}{p(x)q(x,y)}\right)&\text{, if }p(x)q(x,y)>0\\1&\text{, otherwise}\end{cases}\right\}\;\;\;\text{for }x,y\in E$$
• $$r(x):=1-\int Q(x,{\rm d}y)\alpha(x,y)\;\;\;\text{for }x\in E;$$
• $$\kappa$$ denote the transition kernel of the Metropolis-Hastings algorithm with proposal kernel $$Q$$ and target distribution $$\mu$$; i.e. $$\kappa(x,B)=\underbrace{\int_BQ(x,{\rm d}y)\alpha(x,y)}_{=:\;\pi(x,\;B)}+r(x)1_B(x)\;\;\;\text{for all }(x,B)\in E\times\mathcal E.$$

In Proposition 5.6.3 of this paper, it is claimed that, if $$x\in E$$ with $$p(x)>0$$, then $$\left\|\kappa(x,\;\cdot\;)-Q(x,\;\cdot\;)\right\|=r(x),\tag1$$ where $$\|\;\cdot\|$$ denotes the total variation norm. How do we proof this result?

A proof is given, but I don't understand it. The paper is considering MALA, instead of the general setup here, but I don't think this is crucial. I'm willing to impose further assumptions on $$Q$$, if necessary.

If $$\nu_i$$ is a probability measure on $$(E,\mathcal E)$$, the total variation distance between $$\nu_1$$ and $$\nu_2$$ is defined as $$\|\nu_1-\nu_2\|:=\sup_{B\in\mathcal E}(\nu_1-\nu_2)(B).$$

Now, what I get is that $$\kappa(x,B)-Q(x,B)=\begin{cases}Q(x,B^c)-\pi(x,B^c)&\text{, if }x\in B;\\\pi(x,B)-Q(x,B)&\text{, otherwise}\end{cases}\tag2$$ for all $$B\in\mathcal E$$.

For $$B=\{x\}$$, we obtain $$\kappa(x,B)-Q(x,B)=r(x)\tag3.$$ So, the question reduces to why we maximize $$(2)$$ by choosing $$B=\{x\}$$?

For this $$B$$, we clearly got $$x\in B$$ and hence $$\kappa(x,B)-Q(x,B)=Q(x,B^c)-\pi(x,B^c)$$. Clearly, the first summand $$Q(x,B^c)$$ will increase when we reduce $$B$$. But it's not clear to me, why this increase is larger than the decrease from $$\pi(x,B^c)$$. Seems like we need some kind of monotonicity between $$Q$$ and $$\pi$$ here ...

• The (coupling) inequality$$\left\|\kappa(x,\;\cdot\;)-Q(x,\;\cdot\;)\right\|\le r(x),\tag1$$is straightforward as the proposal from $Q(x,\cdot)$ is accepted on average with probability $1-r(x)$. Apr 15 at 7:39
• @Xi'an Wouldn't your $(1)$ and my $(3)$ together already imply $(1)$? But I don't get your argument. I know what "the" coupling inequality is and I also know that the proposals from $Q(x,\;\cdot\;)$ are accepted on average with probability $1-r(x)$. Apr 15 at 8:37

Conditional on $$x$$, the "coupling" interpretation is to start with the move attached to $$Q(x,\cdot)$$ and to propose to couple the output with $$\kappa(x,\cdot)$$, a coupling that is accepted with probability $$1-r(x)$$. Hence the total variation distance between $$Q(x,\cdot)$$ and $$\kappa(x,\cdot)$$ is zero with probability $$1-r(x)$$. And $$1$$ (i.e., one) with probability $$r(x)$$ since $$\mathbb I_{\{x\}^c}(x) - Q(x,\{x\}^c)=1$$ if one assumes that $$Q$$ is free of atoms.
• I see. The coupling inequality makes it really straightforward, while I was struggling to show it directly from the definition of the total variation norm. Do you think a similar result can be obtained for the difference $$\langle f,f-Qf\rangle_{L^2(\mu)}-\langle f,f-\kappa f\rangle_{L^2(\mu)}$$ for $f\in L^2(\mu)$? Apr 16 at 15:11
• From the variational characterization of the total variation I only get $$|(\kappa(x,\;\cdot\;)-Q(x,\;\cdot\;))f|\le2\|f\|_\infty\|\kappa(x,\;\cdot\;)-Q(x,\;\cdot\;)\|\tag1,$$ which requires $f$ to be bounded. What I get from this is $$\left|\langle f,(\kappa-Q)f\rangle_{L^2(\mu)}\right|\le2\|f\|^2_\infty\mu r.$$ Is there a nice expression for $\mu r$? In any case, maybe this bound is not really sharp. Would it be better to consider $\chi^2$-distance? Apr 16 at 19:23