# Why do we sample from the uniform distribution in Metropolis-Hastings for acceptance?

For each iteration of the MH, sample $$x'=q(x|x')$$, then the acceptance probability is computed:$$A=\min(1,a)$$ where $$\alpha=\frac{p(x')q(x|x')}{p(x)q(x'|x)}$$ Now, I've seen that the algorithm samples from a uniform distribution $$u\sim U(0,1)$$to set the new sample as$$x=x'$$if $$u≤A$$, retain $$x=x$$ otherwise.

I have seen some derivation on how the MH algorithm samples from the target distribution $$p$$ as the stationary distribution of the Markov chain: $$p(x'|x)=q(x'|x)A$$ if $$x'≠x$$, otherwise$$p(x'|x)=q(x|x)+\sum_{x≠x'}q(x'|x)A$$ Now what does the sampling from the uniform distribution have to do with deciding whether to accept the proposal $$x'$$ or retain $$x$$?

Isn't it sufficient to accept the proposal if $$A>0.5$$?

The (simplest) validation of the Metropolis-(Rosenbluth-)Hastings algorithm is that the associated Markov kernel $$K$$ satisfies the so-called detailed balance equation $$\forall\ x,x^\prime,\quad p(x)K(x,x^\prime)=p(x^\prime)K(x^\prime,x)\tag{1}$$ since (1) implies that $$p(\cdot)$$ is stationary. This Markov kernel measure writes as the mixture $$K(x,\text dx^\prime)=q(x^\prime|x)\alpha(x,x^\prime)\,\text dx+\int\{1-\alpha(x,y)\}q(y|x)\,\text dy\,\delta_x(dx^\prime)\tag{2}$$ where $$\delta_x(dx^\prime)$$ denotes the Dirac measure at $$x$$. This representation means that the acceptance probability $$\alpha(x,x^\prime)$$ is crucial for the stationarity property (1) and cannot be replaced with $$\displaystyle{\mathbb I_{\displaystyle\alpha(x,x^\prime)>0.5}}$$ which would lead to another stationary distribution, as can be checked on a simple example.

Here is for instance a Binomial target $$\mathcal B(.1)$$ and a Uniform $$\mathcal U(\{0,1\})$$ proposal, where the $$\displaystyle{\mathbb I_{\displaystyle p(x^\prime)>0.5p(x)}}$$ acceptance step is failing to recover the target:

p=function(x)ifelse(x,.1,.9)
x=y=sample(0:1,N<-1e3,rep=TRUE)
for(t in 2:N)x[t]=ifelse(p(y[t])>.5*p(x[t-1]),y[t],x[t-1])


since it returns a point mass at zero instead:

summary(x)
Min.   Median  Mean   Max.
0.000  0.000   0.001  1.000


the explanation being that $$0$$ is a fixed (or cemetery) state, $$1$$ being transient.

In practice, implementing a simulation from the kernel $$K$$ means

1. selecting between the Dirac (reject) and the non-Dirac (accept) parts of the kernel in (2), and then
2. simulating from the selected part (which is immediate when the Dirac part is selected).

The non-Dirac part is selected with probability $$\int \alpha(x,x^\prime)\, q(x^\prime|x)\,\text dx\tag{3}$$ whose unbiased estimator is $$\mathbb I_{\displaystyle U<\alpha(x,X^\prime)}\qquad \text{when}\ U\sim\mathcal U(0,1)\,,\ X^\prime\sim q(x^\prime|x)$$ Hence simulating the Uniform variate $$U$$ is a practical (and standard) way to achieve the realisation of an event with probability (3). In simulation terms, $$U$$ is called an auxiliary variable in the sense that it is not connected with the original problem of generating a Markov chain from the kernel $$K$$.

Note that the above explanation inverts the usual steps of a Metropolis-(Rosenbluth-)Hastings algorithm, where $$X^\prime$$ is first generated, then used to decide between the Dirac (reject) and the non-Dirac (accept) parts of the kernel. This double use of $$X^\prime$$ is both correct and more efficient than generating an independent $$X^\prime$$ from $$q(x^\prime|x)\alpha(x,x^\prime)\Big/ \int \alpha(x,y)\, q(y|x)\,\text dy$$ which most often multiple rejections.

• Accepting the kernel measure part for now, they now makes sense to me. I will take my time understanding this answer particularly the formalism involved in the kernel measure (which was not introduced in my book) thank you very much Sep 17, 2022 at 9:10