I will review some of the mathematical theory behind several Monte Carlo Markov chain (MCMC) algorithms used by experimental physicists to simulate models at their critical temperatures. The two models of interest will be the Ising model and percolation (no prior knowledge of these models will be assumed).
At the non-critical temperatures, these algorithms perform well
and good sampling can be obtained after log n steps
(n stands for the number of particles, or number of
vertices in the underlying graph). At the critical temperature,
however, random fluctuations cause these algorithms to slow down,
and only after some power law of n number of steps can one
achieve good sampling. This behavior is sometimes
called critical slowing down.
Theoretical physicists
strongly believe it; experimental physicists casually ignore it
and do whatever they feel like.
Based on a FOCS'07 abstract written jointly with Yuval Peres and Yun Long.