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$?


1 Answer 1


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:

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:

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.

  • 1
    $\begingroup$ 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 $\endgroup$
    – wd violet
    Sep 17, 2022 at 9:10

Your Answer

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

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