The method we have used to sample points from the chosen probability
distribution, *g*(*x*), is the Metropolis algorithm[19]. In
this algorithm, a random walk is performed through the configuration
space of interest. The walk is designed so that the points on the
walk are distributed according to the required probability
distribution. At each point on the walk a random trial move from the
current position in configuration space is selected. This trial move
is then either accepted or rejected according to a simple
probabilistic rule. If the move is accepted then the ``walker'' moves
to the new position in configuration space; otherwise the ``walker''
remains where it is. (By a ``walker'' we mean a point in the
3*N*-dimensional configuration space of the problem.) Another trial
step is then chosen, either from the new accepted position or from the
old position if the first move was rejected, and the process is
repeated. In this way it should be possible for the ``walker'' to
explore the whole configuration space of the problem. The Metropolis
algorithm provides a prescription for choosing which moves in
configuration space to accept or reject. Suppose that the current
position on the random walk is , where defines the
positions of all the electrons in the system

and that the move, chosen randomly, would make the new position the point . Each of these points has a number density associated with it, and . The number density is simply proportional to the probability distribution of that point in configuration space. If the average over many steps of the random walk follows the specified probability distribution then the walk is said to have reached equilibrium. In this case, the average number densities of points on the walk at and , and , should be constant. That means that the probability of making a transition from to has to be equal to the probability of making a transition in the opposite direction, from to . The transition probability of a trial move being made from to is denoted by and the transition probability of a trial move being made from to by . The trial moves are chosen from a fixed probability distribution around the current position and since there is nothing special about the points or ,

The probability of a trial move from to being accepted is and the probability of accepting the reverse move is . Total probabilities for moves occurring in either direction are then

and the equilibrium condition implies that

In the Metropolis algorithm the probability of accepting the random move, , is chosen to be

This satisfies the equilibrium conditions for the distribution. The mechanism for accepting a move with probability , within the QMC code, is to generate a random number in the range [0,1]. If this random number is less than then the move is accepted. If this random number is greater than then the move is rejected.

The above description was for a configuration space in which any one
point could be reached from any other point in one move. If the
configuration space is very large, then if small moves are made it is
not possible to reach any other point in one move. As long as any one
point can be reached from any other point the random walk is said to
be *ergodic* and the Metropolis algorithm is still valid. A
straightforward extension of the above argument can be made to justify
the use of the Metropolis algorithm in this situation. To ensure that
points are sampled correctly from the probability distribution, the
random walk has to be allowed to proceed from some arbitrary initial
starting point until the average over an ensemble of moves represents
the distribution to be sampled. At this point equilibrium has been
reached. It is only at this point that the importance sampling Monte
Carlo calculation can be carried out. It should be noted that the
Metropolis algorithm is just one of a large number of such algorithms,
but we have not found any reason to choose a different algorithm.

Tue Nov 19 17:11:34 GMT 1996