Bayes In the Real World: The Metropolis-Hastings Algorithm

This lets us do the algebra on the right. I'm interested in the last equation: it establishes the property known as detailed balance.

Let's imagine for a moment that we really have achieved equilibrium, so $x_t$ is distributed exactly according to $P^*$. What's the distribution of $x_{t + 1}$? Well, we can compute the chance that we arrive from a random point to a specific $x$, which we can denote $\Pr(\rightarrow x)$.

$$\begin{aligned} \Pr(\rightarrow x) &= \int_{y} P^*(y) \Pr(y \rightarrow x) \ dy \\ &= \int_{y} P^*(x) \Pr(x \rightarrow y)\ dy \\ &= \Pr(x \rightarrow) \end{aligned}$$

In English, the chance that we just went away from $x$ is the same as the chance that we just went to $x$, so the probability of $x_{t + 1} = x$ is the same as it was for $x_t$, which is exactly what we want: once it reaches equilibrium, it stays there forever. Roughly, this is why detailed balance ensures that this algorithm converges to the correct distribution.

Let's see this bad boy in action, shall we?