Editing Monte Carlo integration (section)

== Importance sampling ==
{{Main|Importance sampling}}

There are a variety of importance sampling algorithms, such as 
=== Importance sampling algorithm ===

Importance sampling provides a very important tool to perform Monte-Carlo integration.<ref name="newman1999ch2">{{harvnb|Newman|Barkema|1999|loc=Chap. 2}}</ref><ref name="kr11">{{harvnb|Kroese|Taimre|Botev|2011}}</ref> The main result of importance sampling to this method is that the uniform sampling of <math>\overline{\mathbf{x}}</math> is a particular case of a more generic choice, on which the samples are drawn from any distribution <math>p(\overline{\mathbf{x}})</math>. The idea is that <math>p(\overline{\mathbf{x}})</math> can be chosen to decrease the variance of the measurement ''Q<sub>N</sub>''.

Consider the following example where one would like to numerically integrate a gaussian function, centered at 0, with σ = 1, from −1000 to 1000. Naturally, if the samples are drawn uniformly on the interval [−1000, 1000], only a very small part of them would be significant to the integral. This can be improved by choosing a different distribution from where the samples are chosen, for instance by sampling according to a gaussian distribution centered at 0, with σ = 1. Of course the "right" choice strongly depends on the integrand.

Formally, given a set of samples chosen from a distribution
<math display="block">p(\overline{\mathbf{x}}) : \qquad \overline{\mathbf{x}}_1, \cdots, \overline{\mathbf{x}}_N \in V, </math>
the estimator for ''I'' is given by<ref name="newman1999ch2" />
<math display="block"> Q_N \equiv \frac{1}{N} \sum_{i=1}^N \frac{f(\overline{\mathbf{x}}_i)}{p(\overline{\mathbf{x}}_i)}</math>

Intuitively, this says that if we pick a particular sample twice as much as other samples, we weight it half as much as the other samples. This estimator is naturally valid for uniform sampling, the case where <math>p(\overline{\mathbf{x}})</math> is constant.

The [[Metropolis–Hastings algorithm]] is one of the most used algorithms to generate <math>\overline{\mathbf{x}}</math> from <math>p(\overline{\mathbf{x}})</math>,<ref name="newman1999ch2" /> thus providing an efficient way of computing integrals.

=== 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"/>