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. [19] 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*) *d*x, 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.

Tue Nov 19 17:11:34 GMT 1996