En el análisis numérico , el método cuasi-Monte Carlo es un método de integración numérica y resolución de otros problemas que utiliza secuencias de baja discrepancia (también llamadas secuencias cuasi-aleatorias o secuencias subaleatorias) para lograr la reducción de la varianza . Esto contrasta con el método Monte Carlo regular o la integración Monte Carlo , que se basan en secuencias de números pseudoaleatorios .
Los métodos de Monte Carlo y cuasi-Monte Carlo se plantean de manera similar. El problema consiste en aproximar la integral de una función f como el promedio de la función evaluada en un conjunto de puntos x 1 , ..., x N :
Como estamos integrando sobre el cubo unitario de dimensión s , cada x i es un vector de elementos s . La diferencia entre el método cuasi-Monte Carlo y el método Monte Carlo es la forma en que se eligen los x i . El método cuasi-Monte Carlo utiliza una secuencia de baja discrepancia, como la secuencia de Halton , la secuencia de Sobol o la secuencia de Faure, mientras que el método Monte Carlo utiliza una secuencia pseudoaleatoria. La ventaja de utilizar secuencias de baja discrepancia es una tasa de convergencia más rápida. El método cuasi-Monte Carlo tiene una tasa de convergencia cercana a O(1/ N ), mientras que la tasa del método Monte Carlo es O( N −0,5 ). [1]
El método Quasi-Monte Carlo se ha vuelto popular recientemente en el área de finanzas matemáticas o finanzas computacionales . [1] En estas áreas, las integrales numéricas de alta dimensión, donde la integral debe evaluarse dentro de un umbral ε, ocurren con frecuencia. Por lo tanto, el método Monte Carlo y el método Quasi-Monte Carlo son beneficiosos en estas situaciones.
El error de aproximación del método cuasi-Monte Carlo está limitado por un término proporcional a la discrepancia del conjunto x 1 , ..., x N . Específicamente, la desigualdad de Koksma-Hlawka establece que el error
está delimitado por
donde V ( f ) es la variación de Hardy–Krause de la función f (ver Morokoff y Caflisch (1995) [2] para las definiciones detalladas). D N es la llamada discrepancia en estrella del conjunto ( x 1 ,..., x N ) y se define como
donde Q es un sólido rectangular en [0,1] s con lados paralelos a los ejes de coordenadas. [2] La desigualdad se puede utilizar para mostrar que el error de la aproximación por el método cuasi-Monte Carlo es , mientras que el método de Monte Carlo tiene un error probabilístico de . Por lo tanto, para , suficientemente grande , el cuasi-Monte Carlo siempre superará al Monte Carlo aleatorio. Sin embargo, crece exponencialmente rápido con la dimensión, lo que significa que una secuencia mal elegida puede ser mucho peor que el Monte Carlo en dimensiones altas. En la práctica, casi siempre es posible seleccionar una secuencia apropiada de baja discrepancia, o aplicar una transformación apropiada al integrando, para garantizar que el cuasi-Monte Carlo funcione al menos tan bien como el Monte Carlo (y a menudo mucho mejor). [1]
Para la integración unidimensional, se sabe que los métodos de cuadratura como la regla trapezoidal , la regla de Simpson o las fórmulas de Newton-Cotes son eficientes si la función es suave. Estos enfoques también se pueden utilizar para integraciones multidimensionales repitiendo las integrales unidimensionales en múltiples dimensiones. Sin embargo, el número de evaluaciones de funciones crece exponencialmente a medida que s , el número de dimensiones, aumenta. Por lo tanto, se debe utilizar un método que pueda superar esta maldición de la dimensionalidad para integraciones multidimensionales. El método estándar de Monte Carlo se utiliza con frecuencia cuando los métodos de cuadratura son difíciles o costosos de implementar. [2] Los métodos de Monte Carlo y cuasi-Monte Carlo son precisos y relativamente rápidos cuando la dimensión es alta, hasta 300 o más. [3]
Morokoff y Caflisch [2] estudiaron el desempeño de los métodos Monte Carlo y cuasi-Monte Carlo para la integración. En el artículo, se comparan las secuencias de Halton, Sobol y Faure para cuasi-Monte Carlo con el método Monte Carlo estándar que utiliza secuencias pseudoaleatorias. Encontraron que la secuencia de Halton tiene el mejor desempeño para dimensiones de hasta aproximadamente 6; la secuencia de Sobol tiene el mejor desempeño para dimensiones superiores; y la secuencia de Faure, si bien es superada por las otras dos, todavía tiene un mejor desempeño que una secuencia pseudoaleatoria.
Sin embargo, Morokoff y Caflisch [2] dieron ejemplos en los que la ventaja del método cuasi-Monte Carlo es menor que la esperada teóricamente. Aún así, en los ejemplos estudiados por Morokoff y Caflisch, el método cuasi-Monte Carlo arrojó un resultado más preciso que el método Monte Carlo con el mismo número de puntos. Morokoff y Caflisch señalan que la ventaja del método cuasi-Monte Carlo es mayor si el integrando es suave y el número de dimensiones s de la integral es pequeño.
Lemieux mencionó los inconvenientes del cuasi-Monte Carlo: [4]
Para superar algunas de estas dificultades, podemos utilizar un método cuasi-Monte Carlo aleatorio.
Dado que la secuencia de baja discrepancia no es aleatoria, sino determinista, el método cuasi-Monte Carlo puede verse como un algoritmo determinista o un algoritmo desaleatorizado. En este caso, solo tenemos el límite (por ejemplo, ε ≤ V ( f ) D N ) para el error, y el error es difícil de estimar. Para recuperar nuestra capacidad de analizar y estimar la varianza, podemos aleatorizar el método (ver aleatorización para la idea general). El método resultante se llama método cuasi-Monte Carlo aleatorio y también puede verse como una técnica de reducción de varianza para el método estándar de Monte Carlo. [5] Entre varios métodos, el procedimiento de transformación más simple es a través del desplazamiento aleatorio. Sea { x 1 ,..., x N } el conjunto de puntos de la secuencia de baja discrepancia. Muestreamos el vector aleatorio s -dimensional U y lo mezclamos con { x 1 ,..., x N }. En detalle, para cada x j , creamos
y utilizar la secuencia en lugar de . Si tenemos R réplicas para Monte Carlo, muestreamos un vector aleatorio s-dimensional U para cada réplica. La aleatorización permite dar una estimación de la varianza mientras se siguen utilizando secuencias cuasi aleatorias. En comparación con el cuasi Monte Carlo puro, el número de muestras de la secuencia cuasi aleatoria se dividirá por R para un costo computacional equivalente, lo que reduce la tasa de convergencia teórica. En comparación con el Monte Carlo estándar, la varianza y la velocidad de cálculo son ligeramente mejores a partir de los resultados experimentales en Tuffin (2008) [6].
![{\displaystyle \int _{[0,1]^{s}}f(u)\,{\rm {d}}u\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28359218161a6c30086f6a1bf782ec52f6afedee)
![{\displaystyle \varepsilon =\left|\int _{[0,1]^{s}}f(u)\,{\rm {d}}u-{\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i})\right|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50a4320dba9be1ede6df887d6fe89c52bff6f7a9)
![{\displaystyle D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {{\text{número de puntos en }}Q}{N}}-\operatorname {volumen} (Q)\right|,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64cb617a944c49e0f04f654b13bbc65e2781f176)
