The Metropolis Algorithm

In statistical mechanics we commonly want to evaluate thermodynamic averages of the form

$$\left<y\right> = {\sum_i y_i e^{-\beta E_i}\over \sum_i e^{-\beta E_i}}$$ (4.10)

where $E_i$ is the energy of the system in state i and $\beta = 1/k_{\rm B} T$. Such problems can be solved using the Metropolis et al. (1953) algorithm.

Let us suppose the system is initially in a particular state $i$ and we change it to another state $j$. The detailed balance condition demands that in equilibrium the flow from $i$ to $j$ must be balanced by the flow from $j$ to $i$. This can be expressed as

$$p_i T_{i\to j} = p_j T_{j\to i}$$ (4.11)

where $p_i$ is the probability of finding the system in state i and $T_{i\to j}$ is the probability (or rate) that a system in state i will make a transition to state j. (4.11) can be rearranged to read

$${T_{i\to j}\over T_{j\to i}} = {p_j\over p_i}$$ (4.12)

$$= e^{-\beta\left(E_j - E_i\right)}.$$ (4.13)

Generally the right-hand-side of (4.3) is known and we want to generate a set of states which obey the distribution $p_i$. This can be achieved by choosing the transition rates such that

$$T_{i\to j} = \begin{cases} 1&if $p_j > p_i$\ or $E_j < E_i$... ..._j - E_i\right)} &if $p_j < p_i$\ or $E_j > E_i$ \end{cases}.$$ (4.14)

In practice if $p_j < p_i$ a random number, $r$, is chosen between $0$ and $1$ and the system is moved to state $j$ only if $r$ is less than $p_j/p_i$ or $e^{-\beta\left(E_j - E_i\right)}$.

This method is not the only way in which the condition can be fulfilled, but it is by far the most commonly used.

An important feature of the procedure is that it is never necessary to evaluate the partition function, the denominator in (4.10) but only the relative probabilities of the different states. This is usually much easier to achieve as it only requires the calculation of the change of energy from one state to another.

Note that, although we have derived the algorithm in the context of thermodynamics, its use is by no means confined to that case. See for example the quantum Monte-Carlo methods.