# Efficiency of Metropolis algorithm

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:

1. Why Metropolis algorithm is not efficient at low temperatures?

2. Is efficiency of algorithm related to acceptance ratio?

-

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.

-
The question was about 1D, so the critical temperature should be at zero. This would explain why the OP found the efficiency drop as they lowered the temperature. –  genneth Feb 24 '11 at 8:37
@genneth: Thanks for answers. But in literature I exactly found that algorithm is not efficient at low temperatures, not near critical temperature (although same thing in 1D). Gould and Tobochnik maybe gives an explanation in their "Computer simulation methods" on page 652.: "Monte Carlo simulations become very inefficient at low temperatures because almost all trial configurations will be rejected. For example consider an Ising model (not only 1D) for which all spins are up, but a small magnetic field is applied in the negative direction... –  multipole Mar 12 '11 at 10:35
(continued).. The equilibrium state will have most spins pointing down. Nevertheless, if the magnetic field is small and the temperature is low enough, equilibrium will take a very long time to occur. What we need is a more efficient way of sampling configurations if the acceptance probability is low." (end of quote). –  multipole Mar 12 '11 at 10:39
It seems that main problem is with low acceptance ratio which grows with temperature, so is small on low temperatures. Can I conclude that short answer on both of my qeustions could be: Metropolis algorithm is not efficient at low tmperatures because of low accceptance ratio on that temperatures? And acceptance ratio is low because of low/narrow accptance probability (as thoroughly explained in answers). –  multipole Mar 12 '11 at 10:40

1) The Metropolis algorithm is more general than just the sampling scheme used: the sampling scheme that you describe is a "local update," however there exist more general sampling schemes ("cluster updates" like Wolff algorithm, Swendsen-Wang, etc.). The point is that local update sampling isn't inefficient at low temperatures, per se, it's inefficient near phase transitions, since the correlation length diverges (however cluster algorithms do just fine).

2) A low acceptance ratio can mean that your algorithm is inefficient, but it can also mean that the probability distribution you'd like to sample is very very narrow. Strictly speaking the 1D Ising model doesn't order at any $T\neq 0$, but that doesn't mean the correlation length can't get larger than the sample on your computer! In this case Metropolis will quickly anneal to the ferromagnetic state, and the acceptance probability of any change will be $\mbox{exp}(-2J/T)$, quite narrow indeed.

-
I deleted my comment because I just understand things for which I asked clarification. Now I need confirmation please: Suppose 1) $T\neq 0$, 2) correlation length is larger than the sample (and model quickly anneal to ferromagnetic state), 3) external magnetic field $H =0$. Does that mean that average magnetisation of the sample in equilibrium doesn't have to be 0? I am asking that because in 1d simulation model which I investigate I got average magnetisation to not be zero for all $T\leq0.2$ . Thanks –  multipole Mar 8 '11 at 23:14