2
$\begingroup$

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 ...

$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – Xi'an
    Apr 15 at 7:39
  • $\begingroup$ @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)$. $\endgroup$
    – 0xbadf00d
    Apr 15 at 8:37

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)$? $\endgroup$
    – 0xbadf00d
    Apr 16 at 15:11
  • $\begingroup$ 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? $\endgroup$
    – 0xbadf00d
    Apr 16 at 19:23
  • $\begingroup$ I would still be interested in your thoughts on this. $\endgroup$
    – 0xbadf00d
    Apr 24 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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