To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

VEGAS algorithm

From Wikipedia, the free encyclopedia

The VEGAS algorithm, due to G. Peter Lepage,[1][2][3] 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. It samples points from the probability distribution described by the function so that the points are concentrated in the regions that make the largest contribution to the integral.

YouTube Encyclopedic

  • 1/3
    Views:
    2 455
    34 843
    20 676
  • Las Vegas Algorithm | Randomized Algorithm
  • Randomized algorithms (intro) | Journey into cryptography | Computer Science | Khan Academy
  • Randomized Quick Sort - Algorithms Design & Analysis

Transcription

Contents

Sampling method

In general, if the Monte Carlo integral of is sampled with points distributed according to a probability distribution described by the function we obtain an estimate

The variance of the new estimate is then

where is the variance of the original estimate,

If the probability distribution is chosen as then it can be shown that the variance 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 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 with dimension d the probability distribution is approximated by a separable function: 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

References

  1. ^ Lepage, G.P. (May 1978). "A New Algorithm for Adaptive Multidimensional Integration". Journal of Computational Physics. 27: 192–203. doi:10.1016/0021-9991(78)90004-9.
  2. ^ Lepage, G.P. (March 1980). "VEGAS: An Adaptive Multi-dimensional Integration Program". Cornell preprint. CLNS 80-447.
  3. ^ Ohl, T. (July 1999). "Vegas revisited: Adaptive Monte Carlo integration beyond factorization". Computer Physics Communications. 120 (1): 13–19. arXiv:hep-ph/9806432. Bibcode:1999CoPhC.120...13O. doi:10.1016/S0010-4655(99)00209-X.
This page was last edited on 4 December 2018, at 19:17
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.