So I have seen the Metropolis Hastings algorithm written 2 ways, and I don't quite understand how they can be equivalent:
The first way is by defining the 'acceptance probability' as:
min(1, alpha(x',x))
and the second is by taking a single random sample
u ~ U(0,1)
and accepting the proposed move if alpha(x',x) is known to be less than one and if:
u<=alpha(x',x)
How can these both represent different ways of writing the same algorithm?
Consider, for simplicity, the Metropolis algorithm. Then $\alpha(x',x)=\frac{P(x')}{P(x)}$ is the probability ratio between proposal $x'$ and $x$. Now consider the following two cases.
First, suppose that $\alpha(x',x)\geq 1$. Then $\min\{1,\alpha(x',x)\}=1$ - we accept $x'$ for sure because it is more likely than $x$. On the other hand, since $u\sim U(0,1)$, we have $P(u\leq \alpha(x',x))=1$ - also a guaranteed acceptance.
Now assume that $0\leq \alpha(x',x)<1$. Then the acceptance probability is $\min\{1,\alpha(x',x\}=\alpha(x',x)$, and, probably the most important part of the answer: $$P(u\leq \alpha(x',x))=\frac{\alpha(x',x)-0}{1-0}=\alpha(x',x).$$
That is, the condition $u\leq \alpha(x',x)$ is also satisfied with probability $\alpha(x',x)$. Thus, no matter what $\alpha(x',x)$ is, both definitions lead to the same result.