Algoritmo VEGAS

El algoritmo VEGAS , debido a G. Peter Lepage , ^{[ 1 ] [ 2 ] [ 3 ]} es un método para reducir el error en simulaciones de Monte Carlo mediante el uso de una función de distribución de probabilidad conocida o aproximada para concentrar la búsqueda en aquellas áreas del integrando que hacen la mayor contribución a la integral final .

El algoritmo VEGAS se basa en el muestreo de importancia . Toma muestras de puntos de la distribución de probabilidad descrita por la función${\displaystyle |f|,}$de modo que los puntos se concentren en las regiones que más contribuyen a la integral. La Biblioteca Científica GNU (GSL) proporciona una rutina VEGAS.

En general, si la integral de Monte Carlo de${\displaystyle f}$sobre un volumen${\displaystyle \Omega }$se muestrea con puntos distribuidos según una distribución de probabilidad descrita por la función${\displaystyle g,}$obtenemos una estimación${\displaystyle \mathrm {E} _ {g}(f;N),}$

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

La varianza de la nueva estimación es entonces

${\displaystyle \mathrm {Var} _ {g}(f;N)=\mathrm {Var} (f/g;N)}$

dónde${\displaystyle \mathrm {Var} (f;N)}$es la varianza de la estimación original,${\displaystyle \mathrm {Var} (f;N)=\mathrm {E} (f^{2};N)-(\mathrm {E} (f;N))^{2}.}$

Si se elige la distribución de probabilidad como${\displaystyle g=|f|/\textstyle \int _{\Omega }|f(x)|dx}$entonces se puede demostrar que la varianza${\displaystyle \mathrm {Var} _ {g}(f;N)}$Se desvanece y el error en la estimación será cero. En la práctica, no es posible muestrear a partir de la distribución exacta g para una función arbitraria, por lo que los algoritmos de muestreo por importancia buscan producir aproximaciones eficientes a la distribución deseada.

El algoritmo VEGAS aproxima la distribución exacta realizando varias pasadas sobre la región de integración mientras genera un histograma de la función f. Cada histograma se utiliza para definir una distribución de muestreo para la siguiente pasada. Asintóticamente, este procedimiento converge a la distribución deseada. Para evitar que el número de intervalos del histograma crezca como${\displaystyle K^{d}}$Con dimensión d, la distribución de probabilidad se aproxima mediante una función separable:${\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\cdots }$De esta forma, el número de intervalos requeridos es solo Kd . Esto equivale a localizar los picos de la función a partir de las proyecciones del integrando sobre los ejes de coordenadas. La eficiencia de VEGAS depende de la validez de esta suposición. Es más eficiente cuando los picos del integrando están bien localizados. Si un integrando puede reescribirse en una forma aproximadamente separable, esto aumentará la eficiencia de la integración con VEGAS.

• Algoritmo de Las Vegas
• Integración de Monte Carlo
• Muestreo de importancia