Método de Monte Carlo multinivel

Los métodos de Monte Carlo multinivel (MLMC) en el análisis numérico son algoritmos para calcular las expectativas que surgen en las simulaciones estocásticas . Al igual que los métodos de Monte Carlo , se basan en un muestreo aleatorio repetido , pero estas muestras se toman con diferentes niveles de precisión. Los métodos MLMC pueden reducir en gran medida el costo computacional de los métodos de Monte Carlo estándar al tomar la mayoría de las muestras con una precisión baja y un costo bajo correspondiente, y solo se toman muy pocas muestras con alta precisión y un costo alto correspondiente.

Meta

El objetivo de un método de Monte Carlo multinivel es aproximar el valor esperado de la variable aleatoria que es el resultado de una simulación estocástica . Supongamos que esta variable aleatoria no se puede simular con exactitud, pero existe una secuencia de aproximaciones con una precisión creciente, pero también con un coste creciente, que converge a . La base del método multinivel es la identidad de suma telescópica , ^[1] ${\displaystyle \operatorname {E} [G]}$ ${\displaystyle G}$ ${\displaystyle G_{0},G_{1},\ldots ,G_{L}}$ ${\displaystyle G}$ ${\displaystyle L\rightarrow \infty }$

${\displaystyle \operatorname {E} [G_{L}]=\operatorname {E} [G_{0}]+\sum _{\ell =1}^{L}\operatorname {E} [G_{\ell }-G_{\ell -1}],}$

que se satisface trivialmente debido a la linealidad del operador de expectativa. Luego, cada una de las expectativas se aproxima mediante un método de Monte Carlo, lo que da como resultado el método de Monte Carlo multinivel. Tenga en cuenta que tomar una muestra de la diferencia en el nivel requiere una simulación de y . ${\displaystyle \operatorname {E} [G_{\ell }-G_{\ell -1}]}$ ${\displaystyle G_{\ell }-G_{\ell -1}}$ ${\displaystyle \ell }$ ${\displaystyle G_{\ell }}$ ${\displaystyle G_{\ell -1}}$

El método MLMC funciona si las varianzas son , lo que será el caso si tanto y se aproximan a la misma variable aleatoria . Según el Teorema del Límite Central , esto implica que se necesitan cada vez menos muestras para aproximarse con precisión a la expectativa de la diferencia como . Por lo tanto, la mayoría de las muestras se tomarán en el nivel , donde las muestras son baratas, y solo se requerirán muy pocas muestras en el nivel más fino . En este sentido, MLMC puede considerarse como una estrategia de control de variables recursiva . ${\displaystyle \operatorname {V} [G_{\ell }-G_{\ell -1}]\rightarrow 0}$ ${\displaystyle \ell \rightarrow \infty }$ ${\displaystyle G_{\ell }}$ ${\displaystyle G_{\ell -1}}$ ${\displaystyle G}$ ${\displaystyle G_{\ell }-G_{\ell -1}}$ ${\displaystyle \ell \rightarrow \infty }$ ${\displaystyle 0}$ ${\displaystyle L}$

Aplicaciones

Aproximación de una trayectoria de muestra de una SDE en diferentes niveles.

La primera aplicación de MLMC se atribuye a Mike Giles, ^[2] en el contexto de ecuaciones diferenciales estocásticas (EDEs) para la fijación de precios de opciones , sin embargo, se encuentran rastros anteriores en el trabajo de Heinrich en el contexto de la integración paramétrica. ^[3] Aquí, la variable aleatoria se conoce como la función de pago, y la secuencia de aproximaciones , utiliza una aproximación a la trayectoria de muestra con paso de tiempo . ${\displaystyle G=f(X(T))}$ ${\displaystyle G_{\ell }}$ ${\displaystyle \ell =0,\ldots ,L}$ ${\displaystyle X(t)}$ ${\displaystyle h_{\ell }=2^{-\ell }T}$

La aplicación de MLMC a problemas de cuantificación de incertidumbre (UQ) es un área activa de investigación. ^{[4] [5]} Un ejemplo prototípico importante de estos problemas son las ecuaciones diferenciales parciales (PDE) con coeficientes aleatorios . En este contexto, la variable aleatoria se conoce como la cantidad de interés, y la secuencia de aproximaciones corresponde a una discretización de la PDE con diferentes tamaños de malla. ${\displaystyle G}$

Un algoritmo para la simulación MLMC

A continuación se presenta en pseudocódigo un algoritmo simple de adaptación de niveles para la simulación MLMC.

 ${\displaystyle L\gets 0}$repetir Tomar muestras de calentamiento en el nivel Calcular la varianza de la muestra en todos los niveles Definir el número óptimo de muestras en todos los niveles Tomar muestras adicionales en cada nivel según si entonces ${\displaystyle L}$ ${\displaystyle \ell =0,\ldots ,L}$ ${\displaystyle N_{\ell }}$ ${\displaystyle \ell =0,\ldots ,L}$ ${\displaystyle \ell }$ ${\displaystyle N_{\ell }}$   ${\displaystyle L\geq 2}$  Prueba de convergencia Fin  si no converge entonces  finaliza hasta que converja ${\displaystyle L\gets L+1}$ 

Extensiones de MLMC

Las extensiones recientes del método Monte Carlo multinivel incluyen el Monte Carlo multiíndice, ^[6] donde se considera más de una dirección de refinamiento, y la combinación de MLMC con el método Quasi-Monte Carlo . ^{[7] [8]}

Véase también

• Método de Monte Carlo
• Métodos de Monte Carlo en finanzas
• Métodos cuasi-Monte Carlo en finanzas
• Cuantificación de la incertidumbre
• Ecuaciones diferenciales parciales con coeficientes aleatorios

Referencias

1. Giles, MB (2015). "Métodos de Monte Carlo multinivel". Acta Numerica . 24 : 259–328. arXiv : 1304.5472 . doi :10.1017/s096249291500001x. S2CID  13805654.
2. Giles, MB (2008). "Simulación de trayectorias de Monte Carlo multinivel". Investigación de operaciones . 56 (3): 607–617. CiteSeerX 10.1.1.121.713 . doi :10.1287/opre.1070.0496. S2CID  3000492. 
3. Heinrich, S. (2001). "Métodos de Monte Carlo multinivel". Computación científica a gran escala . Apuntes de clase sobre informática. Vol. 2179. Springer. págs. 58-67. doi :10.1007/3-540-45346-6_5. ISBN . 978-3-540-43043-8.
4. Cliffe, A.; Giles, MB; Scheichl, R.; Teckentrup, A. (2011). "Métodos de Monte Carlo multinivel y aplicaciones a ecuaciones diferenciales parciales elípticas con coeficientes aleatorios" (PDF) . Computing and Visualization in Science . 14 (1): 3–15. doi :10.1007/s00791-011-0160-x. S2CID  1687254.
5. Pisaroni, M.; Nobile, FB; Leyland, P. (2017). "Un método de Monte Carlo de niveles múltiples de continuación para la cuantificación de la incertidumbre en la aerodinámica no viscosa compresible" (PDF) . Métodos informáticos en mecánica aplicada e ingeniería . 326 (C): 20–50. doi :10.1016/j.cma.2017.07.030. S2CID  10379943. Archivado desde el original (PDF) el 14 de febrero de 2018.
6. Haji-Ali, AL; Nobile, F.; Tempone, R. (2016). "Monte Carlo multiíndice: cuando la escasez se encuentra con el muestreo". Matemáticas numéricas . 132 (4): 767–806. arXiv : 1405.3757 . doi :10.1007/s00211-015-0734-5. S2CID  253742676.
7. Giles, MB; Waterhouse, B. (2009). "Simulación de trayectoria cuasi-Monte Carlo multinivel" (PDF) . Modelado financiero avanzado, Serie Radon sobre matemáticas computacionales y aplicadas . De Gruyter: 165–181.
8. Robbe, P.; Nuyens, D.; Vandewalle, S. (2017). "Un algoritmo cuasi-Monte Carlo de índices múltiples para problemas de difusión lognormal". Revista SIAM de Computación Científica . 39 (5): A1811-C392. arXiv : 1608.03157 . Código Bib : 2017SJSC...39S.851R. doi :10.1137/16M1082561. S2CID  42818387.