Monte Carlo method

The Monte Carlo method computes averages by random sampling rather than exhaustive summation. In statistical physics the problem it solves is stark: a 32×32 Ising lattice has 2^1024 configurations, more than there are atoms in any universe, so summing over them is not merely slow but impossible. The Boltzmann factor rescues the situation, because almost all of those configurations have negligible weight; only states near the typical energy contribute. Importance sampling exploits this by visiting states with probability proportional to exp(−E/k_BT), after which a plain unweighted average over the visited states is the thermodynamic average.

The standard implementation is a Markov chain. Propose a small change — flipping one spin — compute the energy cost ΔE, which is local and therefore cheap, and accept with a probability chosen so that the chain's equilibrium distribution is the Boltzmann one. The Metropolis rule accepts with min(1, exp(−ΔE/k_BT)); the Glauber rule uses 1/(1 + exp(ΔE/k_BT)). Both satisfy detailed balance and so sample the same ensemble, differing only in how quickly they equilibrate. Occasional uphill moves are essential: they are what keeps the walk exploring rather than freezing into the first local minimum it meets.

Monte Carlo is the principal tool for systems with no exact solution, the three-dimensional Ising model among them, where it gives critical exponents to several decimal places. Its limitations are equally characteristic: statistical error falls only as 1/√(samples), and near a critical point the correlation time diverges — critical slowing down — so the very region of most interest is the most expensive to sample. Cluster algorithms, which flip whole correlated regions at once, were invented to defeat exactly that problem.

Devised at Los Alamos in the 1940s by Stanisław Ulam and John von Neumann, and named by Nicholas Metropolis after the casino where Ulam's uncle gambled. The Metropolis algorithm was published in 1953 with Rosenbluth and Teller; Roy Glauber's dynamics followed in 1963. It is routinely listed among the most influential algorithms of the twentieth century.