Método cuasi-Monte Carlo - Quasi-Monte Carlo method

Secuencia pseudoaleatoria

Una secuencia de Sobol de números cuasialeatorios de baja discrepancia , que muestra los primeros 10 (rojo), 100 (rojo + azul) y 256 (rojo + azul + verde) puntos de la secuencia.

256 puntos de una fuente de números pseudoaleatorios, secuencia de Halton y secuencia de Sobol (rojo = 1, .., 10, azul = 11, .., 100, verde = 101, .., 256). Los puntos de la secuencia de Sobol se distribuyen de manera más uniforme.

En el análisis numérico , el método cuasi-Monte Carlo es un método para la integración numérica y la resolución de algunos otros problemas utilizando secuencias de baja discrepancia (también llamadas secuencias cuasi-aleatorias o secuencias sub-aleatorias). Esto contrasta con el método de Monte Carlo normal o la integración de Monte Carlo , que se basan en secuencias de números pseudoaleatorios .

Los métodos de Monte Carlo y cuasi-Monte Carlo se expresan de manera similar. El problema es aproximar la integral de una función f como el promedio de la función evaluada en un conjunto de puntos x ₁ , ..., x _N :

${\ Displaystyle \ int _ {[0,1] ^ {s}} f (u) \, {\ rm {d}} u \ approx {\ frac {1} {N}} \, \ sum _ {i = 1} ^ {N} f (x_ {i}).}$

Dado que estamos integrando sobre el cubo de la unidad s -dimensional, cada x _i es un vector de s elementos. La diferencia entre cuasi-Monte Carlo y Monte Carlo es la forma en que se eligen las x _i . Cuasi-Monte Carlo usa una secuencia de discrepancia baja, como la secuencia de Halton , la secuencia de Sobol o la secuencia de Faure, mientras que Monte Carlo usa una secuencia pseudoaleatoria. La ventaja de utilizar secuencias de discrepancia baja es una tasa de convergencia más rápida. Cuasi-Monte Carlo tiene una tasa de convergencia cercana a O (1 / N ), mientras que la tasa para el método de Monte Carlo es O ( N ^−0,5 ).

El método Quasi-Monte Carlo se hizo popular recientemente en el área de finanzas matemáticas o finanzas computacionales . 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 cuasi Monte Carlo son beneficiosos en estas situaciones.

Límites de error de aproximación de cuasi-Monte Carlo

El error de aproximación del método cuasi-Monte Carlo está delimitada por un término proporcional a la discrepancia del conjunto x ₁ , ..., x _N . Específicamente, la desigualdad de Koksma-Hlawka establece que el error

${\ Displaystyle \ varepsilon = \ left | \ int _ {[0,1] ^ {s}} f (u) \, {\ rm {d}} u - {\ frac {1} {N}} \, \ sum _ {i = 1} ^ {N} f (x_ {i}) \ right |}$

está delimitado por

${\ Displaystyle | \ varepsilon | \ leq V (f) D_ {N},}$

donde V ( f ) es la variación de Hardy-Krause de la función f (ver Morokoff y Caflisch (1995) para las definiciones detalladas). D _N es la denominada discrepancia en estrella del conjunto ( x ₁ , ..., x _N ) y se define como

${\ displaystyle D_ {N} = \ sup _ {Q \ subset [0,1] ^ {s}} \ left | {\ frac {{\ text {número de puntos en}} Q} {N}} - \ nombre de operador {volumen} (Q) \ right |,}$

donde Q es un sólido rectangular en [0,1] ^s con lados paralelos a los ejes de coordenadas. 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 Monte Carlo tiene un error probabilístico de . Aunque solo podemos establecer el límite superior del error de aproximación, la tasa de convergencia del método cuasi-Monte Carlo en la práctica suele ser mucho más rápida que su límite teórico. Por tanto, en general, la precisión del método cuasi-Monte Carlo aumenta más rápidamente que la del método Monte Carlo. Sin embargo, esta ventaja solo está garantizada si N es lo suficientemente grande y si la variación es finita. ${\ Displaystyle | \ varepsilon | \ leq V (f) D_ {N}}$${\ Displaystyle O \ left ({\ frac {(\ log N) ^ {s}} {N}} \ right)}$${\ Displaystyle O \ left ({\ frac {1} {\ sqrt {N}}} \ right)}$

Monte Carlo y cuasi-Monte Carlo para integraciones multidimensionales

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 aumenta  s , el número de dimensiones. Por lo tanto, un método que pueda superar esta maldición de dimensionalidad debería usarse 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. Los métodos Monte Carlo y cuasi Monte Carlo son precisos y relativamente rápidos cuando la dimensión es alta, hasta 300 o superior.

Morokoff y Caflisch estudiaron el desempeño de los métodos de integración Monte Carlo y cuasi Monte Carlo. En el artículo, las secuencias de Halton, Sobol y Faure para cuasi-Monte Carlo se comparan con el método estándar de Monte Carlo utilizando secuencias pseudoaleatorias. Descubrieron que la secuencia de Halton funciona mejor para dimensiones de hasta alrededor de 6; la secuencia de Sobol funciona mejor para dimensiones más altas; y la secuencia de Faure, aunque superada por las otras dos, todavía funciona mejor que una secuencia pseudoaleatoria.

Sin embargo, Morokoff y Caflisch dieron ejemplos en los que la ventaja del cuasi-Monte Carlo es menor de lo esperado 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 comentan 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.

Inconvenientes de cuasi-Monte Carlo

Lemieux mencionó los inconvenientes de cuasi-Monte Carlo:

• Para que sea más pequeño que , debe ser pequeño y debe ser grande (p . Ej .). Para valores grandes de sy prácticos N , la discrepancia de un conjunto de puntos de un generador de discrepancia baja puede no ser menor que para un conjunto aleatorio. ${\ Displaystyle O \ left ({\ frac {(\ log N) ^ {s}} {N}} \ right)}$${\ Displaystyle O \ left ({\ frac {1} {\ sqrt {N}}} \ right)}$${\ Displaystyle s}$${\ Displaystyle N}$${\ Displaystyle N> 2 ^ {s}}$
• Para muchas funciones que surgen en la práctica (por ejemplo, si se utilizan variables gaussianas). ${\ Displaystyle V (f) = \ infty}$
• Solo conocemos un límite superior del error (es decir, ε ≤ V ( f ) D _N ) y es difícil calcular y . ${\ Displaystyle D_ {N} ^ {*}}$${\ Displaystyle V (f)}$

Para superar algunas de estas dificultades, podemos utilizar un método cuasi-Monte Carlo aleatorio.

Aleatorización de cuasi-Monte Carlo

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 denomina método cuasi-Monte Carlo aleatorizado y también puede verse como una técnica de reducción de la varianza para el método Monte Carlo estándar. Entre varios métodos, el procedimiento de transformación más simple es mediante desplazamiento aleatorio. Sea { x ₁ , ..., x _N } el conjunto de puntos de la secuencia de discrepancia baja. Tomamos una muestra del vector aleatorio U de dimensión s y lo mezclamos con { x ₁ , ..., x _N }. En detalle, para cada x _j , cree

${\ Displaystyle y_ {j} = x_ {j} + U {\ pmod {1}}}$

y usa la secuencia en lugar de . Si tenemos réplicas de R para Monte Carlo, muestree el vector aleatorio U de dimensión s para cada réplica. La aleatorización permite dar una estimación de la varianza sin dejar de utilizar secuencias cuasialeatorios. En comparación con el cuasi Monte-Carlo puro, el número de muestras de la secuencia cuasi aleatoria se dividirá por R para obtener un costo computacional equivalente, que reduce la tasa de convergencia teórica. En comparación con el estándar Monte-Carlo, la varianza y la velocidad de cálculo son ligeramente mejores a partir de los resultados experimentales de Tuffin (2008). ${\ Displaystyle (y_ {j})}$${\ Displaystyle (x_ {j})}$

Ver también

• Método de Montecarlo
• Métodos de Monte Carlo en finanzas
• Métodos cuasi-Monte Carlo en finanzas
• Método de biología Monte Carlo
• Física computacional
• Secuencias de baja discrepancia
• Teoría de la discrepancia
• Cadena de Markov Monte Carlo

Referencias

• RE Caflisch , métodos de Monte Carlo y cuasi-Monte Carlo , Acta Numerica vol. 7, Cambridge University Press, 1998, págs. 1-49.
• Josef Dick y Friedrich Pillichshammer, Redes digitales y secuencias. Teoría de la discrepancia e integración cuasi-Monte Carlo , Cambridge University Press, Cambridge, 2010, ISBN   978-0-521-19159-3
• Gunther Leobacher y Friedrich Pillichshammer, Introducción a la integración y aplicaciones cuasi-Monte Carlo , Libros de texto compactos en matemáticas, Birkhäuser, 2014, ISBN   978-3-319-03424-9
• Michael Drmota y Robert F. Tichy, Secuencias, discrepancias y aplicaciones , Lecture Notes in Math., 1651 , Springer, Berlín, 1997, ISBN   3-540-62606-9
• William J. Morokoff y Russel E. Caflisch , Secuencias cuasi-aleatorias y sus discrepancias , SIAM J. Sci. Computación. 15 (1994), núm. 6, 1251-1279 (en CiteSeer : [2] )
• Harald Niederreiter . Métodos de generación de números aleatorios y cuasi-Monte Carlo. Sociedad de Matemáticas Industriales y Aplicadas, 1992. ISBN   0-89871-295-5
• Harald G. Niederreiter , Métodos cuasi-Monte Carlo y números pseudoaleatorios , Bull. Amer. Matemáticas. Soc. 84 (1978), núm. 6, 957–1041
• Oto Strauch y Štefan Porubský, Distribución de secuencias: una muestra , Peter Lang Publishing House, Frankfurt am Main 2005, ISBN   3-631-54013-2

enlaces externos

• La página Wiki de MCQMC contiene una gran cantidad de material en línea gratuito sobre los métodos Monte Carlo y cuasi Monte Carlo.
• Una introducción muy intuitiva y completa a los métodos Cuasi-Monte Carlo.