In the Metropolis-Hastings Algorithm, it is stated that if we have an acceptance ratio $r = \frac{p(\theta^*|y)}{p(\theta^{(s)}|y)}$ where $\theta^*$ is our new point and $\theta^{(s)}$ is our old point, that

$$\theta^{(s+1)} = \theta^* $$ with probability $min(r, 1)$ and $$\theta^{(s+1)} = \theta^{(s)}$$ with probability $1-min(r, 1)$

is the same as sampling $U \sim Uniform(0,1)$ and then setting $$\theta^{(s+1)} = \theta^* $$ if $U < r$ and $$\theta^{(s+1)} = \theta^{s}$$ otherwise.

My question is, is there a rigorous proof why these two are the same? I can see intuitively why by letting $r=0.9$ and then $r=1.1$, but is there a solid proof of this?

My "proof" so far is that $min(r,1) = P(U<r) = r$ but I am not sure if this is on the right track.


Your proof is correct, $min(r,1)=P(U<r)$ which is equal to $r$ when $r$ is less than 1.

This is an example of Inverse transform sampling, which is a general technique to generate a sample $X$ from any distribution (empirical, numerical or analytic) as long as you can get the cumulative distribution function $P(X<x)$.

Take a uniform random sample $U∼Uniform(0,1)$ for $P(X<x)$ (the c.d.f. is always between 0 and 1, and monotonically increasing) and find the corresponding value of $X$ as in the figure below.The way to find the corresponding value $X$ is to plug $U$ into the inverse function of the c.d.f., i.e. $X=f^{-1}(U)$ where $f(x)=P(X<x)$.

How to do inverse transform sampling

| cite | improve this answer | |
  • $\begingroup$ Thanks! My question is also how to obtain $min(r,1)=P(U<r)$ in the first place. Is there a formal way to prove this relation? Thanks! $\endgroup$ – user321627 Feb 16 '17 at 7:44
  • $\begingroup$ Work out what the cumulative distribution function is for a Uniform(0,1) $\endgroup$ – Gordon McDonald Feb 16 '17 at 11:04
  • 1
    $\begingroup$ Actually, this is incorrect! $P(U<r)=\min(r,1)$, not $r$. $\endgroup$ – Xi'an Feb 16 '17 at 19:17

As I understand, your question isn't specific to MCMC. You're asking why we can use Uniform random variates in place of Bernoulli ones, right?

Define $c = \text{Min}(r,1)$ and let $U \sim \text{Uniform}(0,1)$. Define $Y = 1(U < c)$ where $0 < c < 1$. This is an indicator function that equals $1$ when the event is true, and $0$ otherwise. $Y$ is clearly discrete with possible values $0$ and $1$. This is a Bernoulli distribution. Finding its parameter can be done as follows: $$ p := P(Y = 1) = P(U < c) = \int_0^c f(x) dx = \int_0^c1dx = c. $$ Therefore $Y \sim \text{Bernoulli}(p)$. Or $Y \sim \text{Bernoulli}(c)$...whichever you prefer.

Note 1:

$\{Y < c\} = \{Y < r\}$. If $r \le 1$, it's obvious, and if it isn't, then both events have probability $1$. But in your question, when you write $P(U < r) = r$, that's incorrect---you can't have probabilities greater than unity.

Note 2:

Turns out $f_c(x) = 1(x<c)$ is the inverse CDF of a Bernoulli. I didn't know that before writing this answer out and looking at the other answer :)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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