Algorisme VEGAS

LPlantilla:'algorisme VEGAS, proposat pel físic G. Peter Lepage, és un mètode per a reduir l'error en simulacions Monte Carlo utilitzant una funció de distribució de probabilitat coneguda o aproximada per tal de concentrar la cerca en aquelles àrees de l'integrand que contribueixen més a la integral final.

L'algorisme VEGAS es basa en l'anomenat "mostreig d'importància". Mostreja punts de la distribució de probabilitat descrita per la funció $|f|,$ de manera que els punts es concentren en aquelles regions que contribueixen més a la integral. La biblioteca científica de GNU (GSL) proporciona una rutina VEGAS.

Mètode de mostreig

En general, si la integral de Montecarlo de $f$ sobre un volum $\mathrm{\Omega }$ es mostreja amb punts distribuïts segons una distribució de probabilitat descrita per la funció $g,$ obtenim un estimador ${\mathrm{E}}_g(f;N),$

${\mathrm{E}}_g(f;N)=\frac{1}{N}\sum _i^{N}f(x_i)/g(x_i).$

La variància de la nova estimació és aleshores

${\mathrm{V}\mathrm{a}\mathrm{r}}_g(f;N)=\mathrm{V}\mathrm{a}\mathrm{r}(f/g;N)$

on $\mathrm{V}\mathrm{a}\mathrm{r}(f;N)$ és la variància de l'estimador original, $\mathrm{V}\mathrm{a}\mathrm{r}(f;N)=\mathrm{E}(f^2;N)-(\mathrm{E}(f;N){)}^2.$

Si s'escull la distribució de probabilitat com a $g=|f|/\underset{\mathrm{\Omega }}{\int }|f(x)|dx$, aleshores es pot demostrar que la variància ${\mathrm{V}\mathrm{a}\mathrm{r}}_g(f;N)$ desapareix i l'error en l'estimador serà zero.

A la pràctica, no és possible de fer mostreigs de la distribució exacta g per a una funció arbitrària, de manera que els algorismes de mostreig d'importància tenen com a objectiu produir aproximacions eficients a la distribució desitjada.

Aproximació de la distribució de probabilitat

L'algorisme VEGAS aproxima la distribució exacta fent un nombre de passades per la regió d'integració tot histogramant la funció f. Cada histograma s'utilitza per a definir una distribució de mostreig per al següent pas. Asimptòticament aquest procediment convergeix a la distribució desitjada. Per tal d'evitar que el nombre de bins de l'histograma creixi com $K^d$ amb dimensió d, la distribució de probabilitat s'aproxima mitjançant una funció separable: $g(x_1,x_2,\dots )=g_1(x_1)g_2(x_2)\cdots$ de manera que el nombre de contenidors necessaris sigui només Kd. Això equival a localitzar els pics de la funció a partir de les projeccions de l'integrand sobre els eixos de coordenades. L'eficiència de VEGAS depèn de la validesa d'aquesta hipòtesi. És més eficient quan els pics de l'integrand estan ben localitzats. Si un integrand es pot reescriure en una forma que sigui aproximadament separable, això augmenta l'eficiència de la integració amb VEGAS.

Vegeu també

• Algorisme de Las Vegas
• Integració de Montecarlo