Metropolis method

The Metropolis method is a rejection sampling Markov chain Monte Carlo technique for drawing samples from a probability distribution. It draws its name from Nicholas Metropolis, who first published the algorithm in 1953, proposing it as a technique for evaluating equations of state using the Los Alamos MANIAC I. The algorithm has since been generalized to the Metropolis-Hastings algorithm.

Originally the technique was described for producing a sequence of samples from the Boltzmann distribution, where the probability of each state $x$ was given by $P(x)\propto {\exp({-E(x)/kT})}$ where $kT$ is taken to be a constant and $E(x)$ is a function, called the "energy," which has a minimum to be approximated.

The algorithm

1. start with an initially random state $x_{0}$
2. consider a next sample at $x_{1}=x_{0}+\delta$
3. compare the energy of the new state to the old state by evaluating $\Delta E=E(x_{1})-E(x_{0})$
4. If $\Delta E<0$, (the new sample has a higher probability) always accept $x_{1}$ as the new sample.
5. If $\Delta E>0$, (the new sample is in fact less probable) accept $x_{1}$ with a probability of $\exp(-\Delta E/kT)$.

The stationary distribution of this Markov chain has probabilities proportional to $\exp(-E(x)/kT)$.

References

• N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller (1953). ""Equations of State Calculations by Fast Computing Machines"". Journal of Chemical Physics. 21(6): 1087-1092.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• W.K. Hastings (1970). Biometrika. 57(1): 97-109. {{cite journal}}: Missing or empty |title= (help); Unknown parameter |Title= ignored (|title= suggested) (help)