next up previous contents
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 tex2html_wrap_inline6125 , where tex2html_wrap_inline6125 defines the positions of all the electrons in the system

equation737

and that the move, chosen randomly, would make the new position the point tex2html_wrap_inline6129 . Each of these points has a number density associated with it, tex2html_wrap_inline6131 and tex2html_wrap_inline6133 . 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 tex2html_wrap_inline6125 and tex2html_wrap_inline6129 , tex2html_wrap_inline6131 and tex2html_wrap_inline6133 , should be constant. That means that the probability of making a transition from tex2html_wrap_inline6125 to tex2html_wrap_inline6129 has to be equal to the probability of making a transition in the opposite direction, from tex2html_wrap_inline6129 to tex2html_wrap_inline6125 . The transition probability of a trial move being made from tex2html_wrap_inline6125 to tex2html_wrap_inline6129 is denoted by tex2html_wrap_inline6155 and the transition probability of a trial move being made from tex2html_wrap_inline6129 to tex2html_wrap_inline6125 by tex2html_wrap_inline6161 . The trial moves are chosen from a fixed probability distribution around the current position and since there is nothing special about the points tex2html_wrap_inline6125 or tex2html_wrap_inline6129 ,

equation767

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

eqnarray783

and the equilibrium condition implies that

equation801

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

equation812

This satisfies the equilibrium conditions for the distribution. The mechanism for accepting a move with probability tex2html_wrap_inline6177 , within the QMC code, is to generate a random number in the range [0,1]. If this random number is less than tex2html_wrap_inline6177 then the move is accepted. If this random number is greater than tex2html_wrap_inline6177 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 up previous contents
Next: Variational Quantum Monte Carlo Up: Importance Sampling Previous: Importance Sampling

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