Computational Physics

302 The Monte Carlo method

In the first stage, given a stateX, we propose a new stateX′with a probability given
byωXX′. In the second stage, we compare the weights of the old and the new one,
ρ(X)andρ(X′).AXX′is chosen equal to 1 ifρ(X′)>ρ(X), and it is chosen equal
toρ(X′)/ρ(X)ifρ(X′)<ρ(X). ObviouslyAXX′satisfies condition (10.16). We
accept the new stateX′with a probabilityAXX′, and we reject it with a probability
1 −AXX′. If the stateX′is accepted, it replacesX; if it is not accepted, the system
remains in the stateX. Note that ifρ(X′)>ρ(X), the stateX′is always accepted.
We can summarise the Metropolis algorithm as follows:

T(X→X′)=ωXX′AXX′; (10.17a)

∑

X′

ωXX′=1; ωXX′=ωX′X; (10.17b)

ωXX′>0, for allX,X′; (10.17c)

ifρ(X′)<ρ(X): AXX′=

ρ(X′)

ρ(X)

; (10.17d)

ifρ(X′)≥ρ(X): AXX′=1. (10.17e)
The question now arises as to how we can accept a state with a probability
AXX′ ≤1, and reject it with probability 1−AXX′. This is done by generating a
random numberruniformly between 0 and 1. Ifr<AXX′, the state is accepted,
otherwise it is rejected. It is clear that if this procedure is carried out many times
with the same probabilityAXX′, the state will be accepted a fractionAXX′of the total
number of trials.
Note that because the configurations are generated in a Markov chain, they have
correlations inherent to them. The theory of Markov chains guarantees that we
arrive at the invariant distributionρfor long times; however, it may take much
longer than the available computer time to reach this distribution.
The total number of statistically independent configurations is given by the total
number of steps divided by the correlation ‘time’, measured in Monte Carlo steps.
Note that the number of steps is thetotalnumber of trials: do not fall into the trap of
counting only thesuccessfultrials as MC steps. As we have generated a sequence of
configurationsXwith a statistical distribution exp[−βE(X)], the ensemble average
of a physical quantityAis given by the ‘time average’

A=

1

n−n 0

∑n

ν>n 0

Aν (10.18)

wheren 0 is the number of steps used for equilibration. Note that the ‘time’nis not
physical time. This average is exactly the same as for MD simulations discussed
near the end of Section 8.2. For the determination of statistical errors in the resulting
averages we refer to the discussion in Section 7.4.