    Next: The Metropolis Algorithm Up: Quantum Monte Carlo Methods Previous: Monte Carlo Methods

# Importance Sampling

Monte Carlo calculations can be carried out using sets of random points picked from any arbitrary probability distribution. The choice of distribution obviously makes a difference to the efficiency of the method. In most cases, Monte Carlo calculations carried out using uniform probability distributions give very poor estimates of high-dimensional integrals and are not a useful method of approximation. In 1953, however, Metropolis et. al.  introduced a new algorithm for sampling points from a given probability function. This algorithm enabled the incorporation of ``importance sampling'' into Monte Carlo integration. Instead of choosing points from a uniform distribution, they are now chosen from a distribution which concentrates the points where the function being integrated is large. Eq.( ) can then be rewritten as where the function g(x) is chosen to be a reasonable approximation to f(x). The integral can be calculated by choosing the random points from the probability distribution g(x) and evaluating at these points. To enable g(x) to be act as a distribution function it must be of one sign everywhere, and the best possible choice is g(x)=|f(x)|. The average of these evaluations gives an estimate of I. Another way of looking at this new integral is to define dy = g(x) dx, in which case where the limits of integration are changed to correspond to the change of variable. In this case, random points are chosen from a uniform distribution in the domain A < y < B. The new integrand, f/g, is close to unity and so the variance (i.e. the value of as defined in Eq.( )) for this function is much smaller than that obtained when evaluating the function by sampling from a uniform distribution. Sampling from a non-uniform distribution for this function should therefore be more efficient than doing a crude Monte Carlo calculation without importance sampling.    Next: The Metropolis Algorithm Up: Quantum Monte Carlo Methods Previous: Monte Carlo Methods

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