Summer School on Computational Materials
Science:
Basic Simulation
Techniques
Lecture 3: Markov Chain Monte Carlo
Today we discuss the Monte
Carlo method. In statistical physics what is usually meant by Monte Carlo is not
direct Monte Carlo sampling but random walks, or more specifically, Metropolis
Monte Carlo. The random walk algorithm is one of the most important and
pervasive numerical algorithm to be used on computers. The random walk or
Metropolis algorithm was first used by Metropolis, Rosenbluth and Teller in 1953
though it is based on much earlier ideas of Markov. In statistics it is known as
MCMC (Markov Chain Monte Carlo.) It is a general method of sampling arbitrary
highly-dimensional probability distributions by taking a random walk through
configuration space. One changes the state of the system randomly according to a
fixed transition rule, thus generating a random walk through state space,
s0,s1,s2, .... The definition of a Markov process is that the next step is
chosen from a probability distribution that depends only on the present
position. This makes it very easy to describe mathematically. The process is
often called the drunkard's walk.
The pdf file contains a
description of Markov Chain Monte Carlo.
Comparison between MC and MD
Which is better for simulations, Monte Carlo or Molecular Dynamics?
- MD can compute Newtonian dynamics. MC has a dynamics (often called
kinetics) under user control, through the transition probability but
does not necessarily correspond to a physical dynamics. MC dynamics is useful
for studying long-term diffusive process, if one sticks to local transition
rules.
- MC is simpler: no forces, no time step errors and is a direct simulation
of the canonical ensemble. It relies on a good source of pseudorandom numbers.
Luckily this has not been a major problem.
- MC is more general. In MD you can only work on how to make the CPU
time/physical time faster. If the system remains in a metastable state for a
long physical time you are stuck. In MC you can invent better transition
rules. Hence ergodicity is less of a problem in MC.
- MD is sometimes very effective in highly constrained systems compared with
classic Metropolis.
- MD requires some extra effort for constant temperature and that messes up
the dynamics. MC is naturally formulated at constant T.
- MC can handle discrete degrees of freedom (e. g. spin models) while MD is
limited to models that only have continuous degrees of freedom.
So you
need both! The best is to have both in the same code so you can use MC to warm
up the dynamics.
David Ceperley, University of Illinois May 2001