VEGAS algorithm

<h2 id="sampling-method">Sampling method</h2>
<p class="note">Further information: <a href="/facts/Importance_sampling/jrbUnMXa">Importance sampling</a></p>
<p>In general, if the Monte Carlo integral of 
  
    
      
        f
      
    
    {\displaystyle f}
  
 over a volume 
  
    
      
        Ω
      
    
    {\displaystyle \Omega }
  
 is sampled with points distributed according to a probability distribution described by the function 
  
    
      
        g
        ,
      
    
    {\displaystyle g,}
  
 we obtain an estimate 
  
    
      
        
          
            E
          
          
            g
          
        
        (
        f
        ;
        N
        )
        ,
      
    
    {\displaystyle \mathrm {E} _{g}(f;N),}

</p>

E
          
          
            g
          
        
        (
        f
        ;
        N
        )
        =
        
          
            1
            N
          
        
        
          ∑
          
            i
          
          
            N
          
        
        
          f
          (
          
            x
            
              i
            
          
          )
        
        
          /
        
        g
        (
        
          x
          
            i
          
        
        )
        .
      
    
    {\displaystyle \mathrm {E} _{g}(f;N)={1 \over N}\sum _{i}^{N}{f(x_{i})}/g(x_{i}).}

<p>The <a href="/facts/Variance/ULBJKXD1">variance</a> of the new estimate is then
</p>

V
            a
            r
          
          
            g
          
        
        (
        f
        ;
        N
        )
        =
        
          V
          a
          r
        
        (
        f
        
          /
        
        g
        ;
        N
        )
      
    
    {\displaystyle \mathrm {Var} _{g}(f;N)=\mathrm {Var} (f/g;N)}

<p>where 
  
    
      
        
          V
          a
          r
        
        (
        f
        ;
        N
        )
      
    
    {\displaystyle \mathrm {Var} (f;N)}
  
 is the variance of the original estimate, 
  
    
      
        
          V
          a
          r
        
        (
        f
        ;
        N
        )
        =
        
          E
        
        (
        
          f
          
            2
          
        
        ;
        N
        )
        −
        (
        
          E
        
        (
        f
        ;
        N
        )
        
          )
          
            2
          
        
        .
      
    
    {\displaystyle \mathrm {Var} (f;N)=\mathrm {E} (f^{2};N)-(\mathrm {E} (f;N))^{2}.}

</p><p>If the probability distribution is chosen as 
  
    
      
        g
        =
        
          |
        
        f
        
          |
        
        
          /
        
        
          
            ∫
            
              Ω
            
          
          
            |
          
          f
          (
          x
          )
          
            |
          
          d
          x
        
      
    
    {\displaystyle g=|f|/\textstyle \int _{\Omega }|f(x)|dx}
  
 then it can be shown that the variance 
  
    
      
        
          
            V
            a
            r
          
          
            g
          
        
        (
        f
        ;
        N
        )
      
    
    {\displaystyle \mathrm {Var} _{g}(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.
</p>
<h2 id="approximation-of-probability-distribution">Approximation of probability distribution</h2>
<p>The VEGAS algorithm approximates the exact distribution by making a number of passes over the integration region while <a href="/facts/Histogram/oMmvqGEA">histogramming</a> 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 
  
    
      
        
          K
          
            d
          
        
      
    
    {\displaystyle K^{d}}
  
 with dimension <i>d</i> the probability distribution is approximated by a separable function: 
  
    
      
        g
        (
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        ,
        …
        )
        =
        
          g
          
            1
          
        
        (
        
          x
          
            1
          
        
        )
        
          g
          
            2
          
        
        (
        
          x
          
            2
          
        
        )
        ⋯
      
    
    {\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\cdots }
  
 so that the number of bins required is only <i>Kd</i>. This is equivalent to locating the peaks of the function from the <a href="/facts/Projection_(mathematics)/QxxC9XTp">projections</a> 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.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Las_Vegas_algorithm/K43MRwQz">Las Vegas algorithm</a></li>
<li><a href="/facts/Monte_Carlo_integration/YefNEuUg">Monte Carlo integration</a></li>
<li><a href="/facts/Importance_sampling/jrbUnMXa">Importance sampling</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Lepage, G.P. (May 1978). "A New Algorithm for Adaptive Multidimensional Integration". Journal of Computational Physics. 27 (2): 192–203. Bibcode:1978JCoPh..27..192L. doi:10.1016/0021-9991(78)90004-9. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Lepage, G.P. (March 1980). "VEGAS: An Adaptive Multi-dimensional Integration Program". Cornell Preprint. CLNS 80-447. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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. S2CID 18194240. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

VEGAS algorithm open-in-new

VEGAS algorithm