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) 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.