Context is 1D Ising model. Metropolis algorithm is used for simulate that model. Among all possible spins configurations (states) that algorithm generates only states with the desired Boltzmann probability.
Algorithm chooses spin at random and makes a trial flip. If trial satisfies certain conditions related to Boltzmann probability, flip is accepted. Otherwise flip is rejected and system is unchanged.
Define "acceptance ratio" as a percentage of accepted trials. Simulation shows that acceptance ratio is higher on higher temperature (behave as increasing function of temperature).
Questions:
-
Why Metropolis algorithm is not efficient at low temperatures?
-
Is efficiency of algorithm related to acceptance ratio?
Best Answer
There are two problems at low temperatures. One is intrinsic to the Ising model, the other to the Metropolis algorithm. The Ising one is a bit more serious.
Problem with the Ising Model at low temperatures
The Ising model of ferromagnetism posits that the electrons in a model can be modeled as little magnetic dipoles, confined to only two quantized spin states, up and down, and that all the electrons in the metal have the same two possible orientations. The Metropolis algorithm counts up the quanta of energy to be gained if a particular dipole were flipped over by counting up the states of the dipole's neighbors and comparing it to the dipole itself. It compares the number it gets with the thermal energy from the Boltzmann distribution to determine whether or not the metal is cool enough that flipping to join the neighbors' alignments is energetically favorable.
Even if the dipoles have more possible orientations than this (ie if their spins don't really all align on the same plane), that's not the big problem at low temperatures. The real issue is that quantum mechanics is more subtle than this. In reality, it isn't the orientation of each individual which is quantized, but the sum of their magnetic moments which is quantized. At very low temperatures, this becomes an important failure in the Ising model, and the relevant states of a true ferromagnet are "magnons" in which all dipoles are nearly parallel and a single unit of opposite alignment is spread across many dipoles. So, we really shouldn't be comparing the dipole to its neighbors individually at very low temperatures.
Problem with the Metropolis algorithm at low temperatures
The problem here is also subtle. The Metropolis algorithm works by randomly picking a single dipole out of the whole magnet, checking it as described above, then checking another - it's just a Monte Carlo method. Now, theoretically, there should be a "critical temperature," below which it is energetically favorable for the dipoles to side with magnetism instead of temperature. But check out the following plots, which came from a simulation I did of a Metropolis-algorithm Ising magnet in C a while ago. In the units I used, the critical temperature happened to be $T_c=2.27$:
The lowest temperature systems converge much more quickly to a homogeneous magnetization, but even at $T=1.5$ you still see "meta-stable states." In these cases, large sections of the magnet are commonly aligned, but the entire magnet isn't. Change can only occur along the border region - and since you are using a random choice of dipoles, the chance that you randomly select one of those dipoles on the border region is pretty small, so you need a very long timeframe for the system to reach equilibrium using this Monte-Carlo scheme.
Since the efficiency is worse close to the critical point of temperature, you could say that the algorithm's efficiency is worse near the critical point of the acceptance ratio, since the acceptance is related to the temperature.