# VEGAS algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/VEGAS_algorithm
> Markdown URL: https://mediated.wiki/source/VEGAS_algorithm.md
> Source: https://en.wikipedia.org/wiki/VEGAS_algorithm
> Source revision: 1099310946
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Algorithm}}
The '''VEGAS algorithm''', due to [G. Peter Lepage](/source/G._Peter_Lepage),<ref name=Lepage1978>{{cite journal|last=Lepage|first=G.P.|title=A New Algorithm for Adaptive Multidimensional Integration|journal=Journal of Computational Physics|date=May 1978|volume=27|issue=2|pages=192–203|doi=10.1016/0021-9991(78)90004-9|bibcode=1978JCoPh..27..192L}}</ref><ref name=Lepage1980>{{cite journal|last=Lepage|first=G.P.|title=VEGAS: An Adaptive Multi-dimensional Integration Program|journal=Cornell Preprint|volume=CLNS 80-447|date=March 1980}}</ref><ref name=Ohl1999>{{cite journal|last=Ohl|first=T.|title=Vegas revisited: Adaptive Monte Carlo integration beyond factorization|journal=Computer Physics Communications|date=July 1999|volume=120|issue=1|pages=13–19|doi=10.1016/S0010-4655(99)00209-X|arxiv=hep-ph/9806432|bibcode=1999CoPhC.120...13O|s2cid=18194240}}</ref> is a method for [reducing error](/source/variance_reduction) in [Monte Carlo simulation](/source/Monte_Carlo_simulation)s by using a known or approximate [probability distribution](/source/probability_distribution) function to concentrate the search in those areas of the [integrand](/source/integrand) that make the greatest contribution to the final [integral](/source/integral).

The VEGAS algorithm is based on [importance sampling](/source/importance_sampling). It samples points from the probability distribution described by the function <math>|f|,</math> so that the points are concentrated in the regions that make the largest contribution to the integral. The [GNU Scientific Library](/source/GNU_Scientific_Library) (GSL) provides a VEGAS routine.

==Sampling method==
{{Further|Importance sampling}}
In general, if the Monte Carlo integral of <math>f</math> over a volume <math>\Omega</math> is sampled with points distributed according to a probability distribution described by the function <math>g,</math> we obtain an estimate <math>\mathrm{E}_g(f; N),</math>

:<math>\mathrm{E}_g(f; N) = {1 \over N } \sum_i^N { f(x_i)} / g(x_i) .</math>

The [variance](/source/variance) of the new estimate is then

:<math>\mathrm{Var}_g(f; N) = \mathrm{Var}(f/g; N)</math>

where <math>\mathrm{Var}(f;N)</math> is the variance of the original estimate, <math>\mathrm{Var}(f; N) = \mathrm{E}(f^2; N) - (\mathrm{E}(f; N))^2.</math>

If the probability distribution is chosen as <math>g = |f|/\textstyle \int_\Omega |f(x)|dx </math> then it can be shown that the variance <math>\mathrm{Var}_g(f; N)</math> 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 [histogram](/source/histogram)ming 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 <math>K^d</math> with dimension ''d'' the probability distribution is approximated by a separable function: <math>g(x_1, x_2, \ldots) = g_1(x_1) g_2(x_2) \cdots</math> so that the number of bins required is only ''Kd''. This is equivalent to locating the peaks of the function from the [projection](/source/projection_(mathematics))s 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](/source/Las_Vegas_algorithm)
* [Monte Carlo integration](/source/Monte_Carlo_integration)
* [Importance sampling](/source/Importance_sampling)

==References==
{{reflist}}<br />

Category:Monte Carlo methods
Category:Computational physics
Category:Statistical algorithms
Category:Variance reduction

{{compu-physics-stub}}

---
Adapted from the Wikipedia article [VEGAS algorithm](https://en.wikipedia.org/wiki/VEGAS_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/VEGAS_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.