Editing VEGAS algorithm

{{short description|Algorithm}}
The '''VEGAS algorithm''', due to [[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 [[variance reduction|reducing error]] in [[Monte Carlo simulation]]s 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]]. 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]] (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]] 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]]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 (mathematics)|projection]]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]]
* [[Monte Carlo integration]]
* [[Importance sampling]]

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

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


{{compu-physics-stub}}