# How to prove that in the Metropolis Hastings Algorithm that accepting a point with probability $min(r,1)$ is the same as using a uniform?

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

• 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! – user321627 Feb 16 '17 at 7:44
• Work out what the cumulative distribution function is for a Uniform(0,1) – Gordon McDonald Feb 16 '17 at 11:04
• Actually, this is incorrect! $P(U<r)=\min(r,1)$, not $r$. – 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 :)