Proof of the Metropolis Algorithm

To prove that the Metropolis algorithm generates a sequence of random numbers distributed according to $w(x)$ consider a large number of walkers starting from different initial points and moving independently. If $N_n(X)$ is the density of those walkers at $X$ after $n$ steps then the net number of walkers moving from point $X$ to point $Y$ in the next step is

$$\Delta N(X) = N_n(X) P( X \to Y ) - N_n(Y) P( Y \to X )$$

$$\Delta N(X) = N_n(Y) P( X \to Y ) \left[ \frac{ N_n(X) }{ N_n(Y) } - \frac{ P( Y \to X ) }{ P( X \to Y ) } \right]$$

Here $P(X \to Y)$ is the probability that the walker will make a transition to $Y$ if he is at $X$, and the inverse for $P(Y \to X)$. The equation shows equilibrium when

$$\frac{ N_n(X) }{ N_n(Y) } = \frac{ N_e(X) }{ N_e(Y) } = \frac{ P( Y \to X ) }{ P( X \to Y ) }$$

Note that $N(X)$ changes when the system is not in equilibrium via the weight that tends to drive it toward equilibrium

To show that the algorithm leads to an equilibrium distribution of walkers proportional to $w(X)$ take the probability of making a step to $Y$ as

$$P( X \to Y ) = T( X \to Y ) A( X \to Y )$$

where $T$ is the probability of making a trial step from $X$ to $Y$ and $A$ is the probability of accepting that step. If $Y$ can be reached from $X$ in a single step, i.e. it is within cube of side $\delta$ centered about $X$, then

$$T( X \to Y ) = T( Y \to X )$$

so that the equilibrium distribution of the metropolis random walkers satisfy.

$$\frac{ N_e(X) }{ N_e(Y) } = \frac{ A( Y \to X ) }{ A( X \to Y ) }$$

From the algorithm,, if $w(X) > w(Y)$, then $A( Y \to X ) = 1$ and

$$A( X \to Y ) = \frac{ w(Y) }{ w(X) }$$

If $w(X) < w(Y)$, then $A( X \to Y ) = 1$ and

$$A( Y \to X ) = \frac{ w(X) }{ w(Y) }$$

Hence,, in either case the equilibrium population of the metropolis random walkers satisfy

$$\frac{ N_e(X) }{ N_e(Y) } = \frac{ w(X) }{ w(Y) }$$

The walkers are distributed with the correct distribution. This proves that the walkers will generate a distribution of points ${X_i}$ in space which will be distributed according to the weight function $w(X)$.