# Expression for the mean acceptance rate of the Metropolis-Hastings algorithm

Let

• $$(E,\mathcal E,\lambda)$$ be a measure space
• $$p:E\to[0,\infty)$$ be $$\mathcal E$$-measurable with $$c:=\int p\:{\rm d}\lambda\in(0,\infty)$$ and $$\mu:=\underbrace{\frac1cp}_{=:\:\tilde p}\lambda$$
• $$q:E^2\to[0,\infty)$$ be $${\mathcal E}^{\otimes2}$$-measurable and $$Q(x,\;\cdot\;)=q(x,\;\cdot\;)\lambda\;\;\;\text{for }x\in E$$
• $$(\Omega,\mathcal A,\operatorname P)$$ be a probability space
• $$X$$ be an $$(E,\mathcal E)$$-valued random variable on $$(\Omega,\mathcal A,\operatorname P)$$ with $$X\sim\mu$$
• $$Y$$ be an $$(E,\mathcal E)$$-valued random variable on $$(\Omega,\mathcal A,\operatorname P)$$ with$$^1$$ $$(X,Y)\sim\mu\otimes Q$$

Note that $$\xi:=\frac{p(Y)q(Y,X)}{p(X)q(X,Y)}$$ is almost surely well-defined. How can we show that $$\operatorname E\left[\xi\right]=1$$?

Let $$B:=\left\{(x,y)\in E^2:p(x)q(x,y)>0\right\}$$ and $$N:=E^2\setminus B$$. Note that $$N$$ is a $$\mu\otimes Q$$-null set and

$$$$\begin{split} \operatorname E\left[\xi\right]&=\int\mu({\rm d}x)\int Q(x,{\rm d}y)1_B(x,y)\frac{p(y)q(y,x)}{p(x)q(x,y)}\\&=\int\lambda({\rm d}x)\lambda({\rm d}y)1_B(x,y)\tilde p(y)q(y,x)\\&=\int\mu({\rm d}y)\int Q(y,{\rm d}x)1_B(x,y). \end{split}\tag1$$$$

However, $$(1)$$ is not equal to $$1$$ (unless there is some kind of "reversibility" allowing us to swap the arguments of $$1_B$$). So, is the claim wrong as stated?

The claim can be found inside the proof of Theorem 1 on page 13 here: https://arxiv.org/pdf/1810.07151.pdf. (The proof itself is too complicated. I guess the author missed the point that $$2(a\wedge b)=a+b-|a-b|$$ for all $$a,b\in\mathbb R$$.)

EDIT: If the claim is wrong, what I really want to show is the claim about the total variation distance in Theorem 1.

$$^1$$ see https://en.wikipedia.org/wiki/Transition_kernel#Product_of_kernels.

• $\left\{(x,y)\in E^2:p(x)q(x,y)>0\right\}$ and $\left\{(y,x)\in E^2:p(x)q(x,y)>0\right\}$ are usually the same set – Taylor Aug 26 '19 at 15:35
• @Taylor Sorry I cannot follow. How does this help unless $q$ is symmetric? And I don't see why your sets are equal? – 0xbadf00d Aug 26 '19 at 15:53
• Isn't it a violation of your agreement as a reviewer to provide a link to a paper that is under "double blind review"? – whuber Aug 27 '19 at 12:19
• Thank you for clarifying the status: your post was being flagged based on that concern. But since the paper has been published, is there some reason you are linking to a review copy? – whuber Aug 27 '19 at 12:22
• @whuber Yes, I've seen that the paper has been published after I saw it first on openreview. But I can exchange the link. – 0xbadf00d Aug 27 '19 at 12:23

## 1 Answer

When the support of $$q(x,\cdot)$$ differs from the support of $$p(\cdot)$$ then the expectation of the ratio is not necessarily one. As an illustration, take \begin{align} p(x) &= \frac{1}{3}\Bbb I_{(1,4)}(x)\\ q(x,y) &= \frac{1}{3}\Bbb I_{(x-1,x+2)}(y) \end{align} Then the expectation of $$\Bbb I_{(1,4)}(x) \Bbb I_{(x-1,x+2)}(y)$$ under the density $$p(y)q(y,x)$$ is 5/9.

• Thank you for your answer. Can we fixed the claim somehow such that it remains true in the general case? – 0xbadf00d Aug 27 '19 at 12:09
• Does defining $$r(x,y):=\left.\begin{cases}\displaystyle\frac{p(y)q(y,x)}{p(x)q(x,y)}&\text{, if }p(x)q(x,y)\ne0\\1&\text{, otherwise}\end{cases}\right\}\;\;\;\text{for }x,y\in E$$ and $\xi:=r(X,Y)$ help? With this definition, I've observed that $$\operatorname E\left[|1-\xi|\right]=\frac1c\int\lambda({\rm d}x)\int\lambda({\rm d}y)|p(x)q(x,y)-p(y)q(y,x)|\tag2$$ which might help to solve my total variation question. – 0xbadf00d Aug 27 '19 at 12:40
• Hi. Sorry, I can't follow. What exactly does not work? Actually, I think this is the way we should have defined $\xi$ in the first place. Before this definition was hidden behind the "almost surely well-defined" claim. But clearly, the set on which it is defined to be $1$ is a null set with respect to the distribution of $(X,Y)$. Please note that my main concern is to prove the total variation claim in Theorem 1 (which might hold even though $\operatorname E\left[\xi\right]\ne1$). – 0xbadf00d Aug 27 '19 at 14:03
• I checked the paper and think the Total Variation identity suffers from the same difficulty. A sufficient condition for it to hold is that the support of $p(x)q(x,y)$ is the same as the support of $p(y)q(y,x)$. – Xi'an Aug 27 '19 at 19:13
• I've accepted your answer, since I initially asked for showing that $\operatorname E\left[\xi\right]=1$. I've asked a separate question for the total variation thing I'm still interested in and included some observations I've made meanwhile: stats.stackexchange.com/q/423913/222528. Would be great if you could take look. – 0xbadf00d Aug 27 '19 at 19:27