My watch list
my.chemeurope.com  
Login  

VEGAS algorithm



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

The VEGAS algorithm is based on importance sampling. It samples points from the probability distribution described by the function |f|, so that the points are concentrated in the regions that make the largest contribution to the integral.

In general, if the Monte Carlo integral of f is sampled with points distributed according to a probability distribution described by the function g, we obtain an estimate Eg(f;N),

E_g(f; N) = E(f/g; N)\,

where E(f,N) is the Monte Carlo estimate of the integral of f,

E(f; N) = {1 \over N } \sum_i^N f(x_i)

for N randomly distributed points xi. The variance of the new estimate is then

Varg(f;N) = Var(f / g;N)

where Var(f;N) is the variance of the original estimate, Var(f;N) = E(f2;N) − (E(f;N))2.

If the probability distribution is chosen as g = | f | / I( | f | ) then it can be shown that the variance Varg(f;N) 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.

The VEGAS algorithm approximates the exact distribution by making a number of passes over the integration region while histogramming the function f. Each histogram is used to define a sampling distribution for the next pass. Asymptotically this procedure converges to the desired distribution. In order to avoid the number of histogram bins growing like Kd the probability distribution is approximated by a separable function: g(x_1, x_2, \ldots) = g_1(x_1) g_2(x_2) \cdots so that the number of bins required is only Kd. This is equivalent to locating the peaks of the function from the projections 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

References

  • G.P. Lepage, A New Algorithm for Adaptive Multidimensional Integration, Journal of Computational Physics 27, 192-203, (1978)
  • G.P. Lepage, VEGAS: An Adaptive Multi-dimensional Integration Program, Cornell preprint CLNS 80-447, March 1980
  • The GNU Scientific Library provides VEGAS routines
 
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "VEGAS_algorithm". A list of authors is available in Wikipedia.
Your browser is not current. Microsoft Internet Explorer 6.0 does not support some functions on Chemie.DE