Next: Variational Quantum Monte Carlo Up: Importance Sampling Previous: Importance Sampling

## The Metropolis Algorithm

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 3N-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.

Next: Variational Quantum Monte Carlo Up: Importance Sampling Previous: Importance Sampling

Andrew Williamson
Tue Nov 19 17:11:34 GMT 1996