Método cuasi-Montecarlo

Proceso de integración numérica

256 puntos de una fuente de números pseudoaleatorios 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 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 subaleatorias) para lograr una reducción de la varianza . 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 Monte Carlo y cuasi Monte Carlo se expresan de manera similar. El problema consiste en aproximar la integral de una función f como la media 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 unitario de s dimensiones, 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 .} Quasi-Monte Carlo utiliza una secuencia de baja discrepancia como la secuencia de Halton , la secuencia de Sobol o la secuencia de Faure, mientras que Monte Carlo utiliza una secuencia pseudoaleatoria. La ventaja de utilizar secuencias de baja discrepancia 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 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 las 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 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-Montecarlo

El error de aproximación del método cuasi-Monte Carlo está acotado 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á limitado 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) ^[2] para definiciones detalladas). D _N es la llamada discrepancia de estrellas del conjunto ( x ₁ ,..., x _N ) y se define como

${\displaystyle D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {{\text{number of points in }}Q}{N}}-\operatorname {volume} (Q)\right|,}$

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 mediante el método cuasi-Monte Carlo es , mientras que el método Monte Carlo tiene un error probabilístico de . Por lo tanto, para , un cuasi-Monte Carlo suficientemente grande siempre superará al Monte Carlo aleatorio. Sin embargo, crece exponencialmente rápidamente con la dimensión, lo que significa que una secuencia mal elegida puede ser mucho peor que 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 adecuada al integrando, para garantizar que cuasi-Monte Carlo funcione al menos tan bien como Monte Carlo (y a menudo mucho mejor). ^[1] ${\displaystyle |\varepsilon |\leq V(f)D_{N}}$ ${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$ ${\displaystyle O\left({\frac {1}{\sqrt {N}}}\right)}$ ${\displaystyle N}$ ${\displaystyle \log(N)^{s}}$

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, se debería utilizar un método que pueda superar esta maldición de la dimensionalidad para las integraciones multidimensionales. El método estándar de Monte Carlo se utiliza frecuentemente cuando los métodos de cuadratura son difíciles o costosos de implementar. ^[2] Los métodos 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 de integración de 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 aproximadamente 6; la secuencia de Sobol funciona mejor para dimensiones superiores; y la secuencia de Faure, aunque superada por las otras dos, todavía funciona mejor que una secuencia pseudoaleatoria.

Sin embargo, Morokoff y Caflisch ^[2] dieron ejemplos en los que la ventaja del cuasi Montecarlo 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 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.

Desventajas del cuasi Montecarlo

Lemieux mencionó los inconvenientes del cuasi Montecarlo: ^[4]

• Para que sea más pequeño que , debe ser pequeño y grande (p. ej. ). Para s grande , dependiendo del valor de N , la discrepancia de un conjunto de puntos de un generador de baja discrepancia podría 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 }$
• Sólo 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 aleatorio cuasi-Monte Carlo.

Aleatorización de cuasi-Monte Carlo

Dado que las secuencias de baja discrepancia no son aleatorias, sino deterministas, el método cuasi-Monte Carlo puede verse como un algoritmo determinista o un algoritmo desaleatorizado. En este caso, sólo tenemos el límite (p. ej., ε ≤ 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 una idea general). El método resultante se denomina método aleatorio cuasi-Monte Carlo y también puede verse como una técnica de reducción de la varianza para el método estándar de Monte Carlo. ^[5] Entre varios métodos, el procedimiento de transformación más simple es mediante desplazamiento aleatorio. Sea { x ₁ ,..., x _N } el punto establecido de la secuencia de baja discrepancia. Tomamos una muestra del vector aleatorio U s -dimensional y lo mezclamos con { x ₁ , ..., x _N }. En detalle, para cada x _j , cree

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

y use la secuencia en lugar de . Si tenemos R replicaciones para Monte Carlo, muestree el vector aleatorio s-dimensional U para cada replicación. La aleatorización permite dar una estimación de la varianza sin dejar de utilizar 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 obtener 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 según los resultados experimentales de Tuffin (2008) ^[6] ${\displaystyle (y_{j})}$ ${\displaystyle (x_{j})}$

Ver también

• Método Monte Carlo  : algoritmo probabilístico de resolución de problemas
• Métodos de Monte Carlo en finanzas  – Métodos de medición probabilística
• Métodos cuasi-Montecarlo en finanzas
• Método de biología Monte Carlo  : método para simular el transporte de iones
• Física computacional  : simulaciones numéricas de problemas físicos a través de computadoras.
• Secuencias de baja discrepancia  – Tipo de secuencia matemáticaPáginas que muestran descripciones breves de los objetivos de redireccionamiento
• Teoría de la discrepancia  – Teoría de las irregularidades de la distribución.
• Cadena de Markov Monte Carlo  : clase de algoritmos de muestreo dependientes

Referencias

1. Søren Asmussen y Peter W. Glynn, Simulación estocástica: algoritmos y análisis , Springer, 2007, 476 páginas
2. William J. Morokoff y Russel E. Caflisch , Integración Cuasi-Monte Carlo , J. Comput. Física. 122 (1995), núm. 2, 218–230. (En CiteSeer : [1])
3. Rudolf Schürer, Una comparación entre (cuasi) Monte Carlo y métodos basados ​​en reglas de cubatura para resolver problemas de integración de alta dimensión , Matemáticas y computadoras en simulación, volumen 62, números 3 a 6, 3 de marzo de 2003, 509–517
4. Christiane Lemieux, Muestreo de Monte Carlo y Quasi-Monte Carlo , Springer, 2009, ISBN  978-1441926760
5. Moshe Dror, Pierre L'Ecuyer y Ferenc Szidarovszky, Modelado de la incertidumbre: un examen de la teoría, los métodos y las aplicaciones estocásticas , Springer 2002, págs.
6. Bruno Tuffin, Aleatorización de métodos cuasi-Monte Carlo para la estimación de errores: encuesta y aproximación normal , Métodos y aplicaciones de Monte Carlo mcma. Volumen 10, números 3 y 4, páginas 617–628, ISSN (en línea) 1569-3961, ISSN (impreso) 0929-9629, doi :10.1515/mcma.2004.10.3-4.617, mayo de 2008

• RE Caflisch , Métodos Monte Carlo y cuasi-Monte Carlo , Acta Numerica vol. 7, Cambridge University Press, 1998, págs. 1–49.
• Josef Dick y Friedrich Pillichshammer, Redes y secuencias digitales. 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 de 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. Computadora. 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-Montecarlo y números pseudoaleatorios , Bull. América. Matemáticas. Soc. 84 (1978), núm. 6, 957–1041
• Oto Strauch y Štefan Porubský, Distribución de secuencias: una muestra , Editorial Peter Lang, Frankfurt am Main 2005, ISBN 3-631-54013-2 

enlaces externos

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