Bayes In the Real World: The Metropolis-Hastings Algorithm

Now we compute $\frac{P(x')}{P(x)}$, which is also $\frac{P^*(x')}{P^*(x)}$ because the constants cancel. This is where the magic happens: computing ratios to cancel out the constant is the core idea of the algorithm and the part to remember. Call this ratio $\alpha$. If $\alpha \ge 1$, then the new point is as likely or more likely than the old one.

We compute a random number between 0 and 1 and call it $r$.

• If $r \le \alpha$, then $x'$ gets "accepted" and becomes our next sample $x_1$.
• If $r > \alpha$, then we use our old $x_0$ as our next sample $x_1$ and try again.