The VEGAS algorithm, due to G. Peter Lepage, is a method for reducing error in Monte Carlo simulations by using a known or approximate probability distribution function to concentrate the search in those areas of the integrand that make the greatest contribution to the final integral.

The VEGAS algorithm is based on importance sampling so that the points are concentrated in the regions that make the largest contribution to the integral. The GNU Scientific Library (GSL) provides a VEGAS routine.

Sampling method

The variance of the new estimate is then

vanishes, and the error in the estimate will be zero. In practice it is not possible to sample from the exact distribution g for an arbitrary function, so importance sampling algorithms aim to produce efficient approximations to the desired distribution.

Approximation of probability distribution

The VEGAS algorithm approximates the exact distribution by making a number of passes over the integration region while histogramming with dimension d so that the number of bins required is only Kd. This is equivalent to locating the peaks of the function from the projectionss of the integrand onto the coordinate axes. The efficiency of VEGAS depends on the validity of this assumption. It is most efficient when the peaks of the integrand are well-localized. If an integrand can be rewritten in a form which is approximately separable this will increase the efficiency of integration with VEGAS.

See also

• Las Vegas algorithm

• Monte Carlo integration

• Importance sampling

References