Editing Monte Carlo integration (section)

=== VEGAS Monte Carlo ===
{{Main|VEGAS algorithm}}

The VEGAS algorithm approximates the exact distribution by making a number of passes over the integration region which creates the histogram of the function ''f''. Each histogram is used to define a sampling distribution for the next pass. Asymptotically this procedure converges to the desired distribution.<ref name="Lepage, 1978">{{harvnb|Lepage|1978}}</ref> In order to avoid the number of histogram bins growing like ''K<sup>d</sup>'', the probability distribution is approximated by a separable function:
<math display="block">g(x_1, x_2, \ldots) = g_1(x_1) g_2(x_2) \ldots </math>
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. VEGAS incorporates a number of additional features, and combines both stratified sampling and importance sampling.<ref name="Lepage, 1978"/>