Monte Carlo-metoden på flera nivåer

Multilevel Monte Carlo (MLMC) metoder i numerisk analys är algoritmer för att beräkna förväntningar som uppstår i stokastiska simuleringar . Precis som Monte Carlo-metoder förlitar de sig på upprepade slumpmässiga provtagningar , men dessa prover tas på olika nivåer av noggrannhet. MLMC-metoder kan kraftigt minska beräkningskostnaden för standard Monte Carlo-metoder genom att ta de flesta prover med låg noggrannhet och motsvarande låg kostnad, och endast mycket få prover tas med hög noggrannhet och motsvarande hög kostnad.

Mål

Målet med en Monte Carlo-metod på flera nivåer är att approximera det förväntade värdet $\operatorname {E} [G]$ för den slumpmässiga variabeln $G$ som är resultatet av en stokastisk simulering . Antag att denna slumpvariabel inte kan simuleras exakt, men det finns en sekvens av approximationer $G_{0},G_{1},\ldots ,G_{L}$ med ökande noggrannhet, men också ökande kostnader, som konvergerar till $G$ som $L\rightarrow \infty$ . Grunden för flernivåmetoden är den teleskoperande summaidentiteten ,

{\displaystyle \operatörsnamn {E} [G_{L}]=\operatörsnamn {E

som är trivialt tillfredsställt på grund av linjäriteten hos förväntningsoperatorn. Var och en av förväntningarna $\operatorname {E} [G_{\ell }-G_{\ell -1}]$ approximeras sedan med en Monte Carlo-metod, vilket resulterar i Monte Carlo-metoden på flera nivåer. Observera att att ta ett urval av skillnaden $G_{\ell }-G_{\ell -1}$ på nivå $\ell$ kräver en simulering av både ${\ displaystyle G_{\ell }}$ och $G_{\ell -1}$ .

MLMC-metoden fungerar om varianserna $\operatorname {V} [G_{\ell }-G_{\ell -1}]\högerpil 0$ som $\ell \rightarrow \infty$ , vilket blir fallet om både $G_{\ell }$ och $G_{\ell -1}$ approximerar samma slumpmässiga variabel $G$ . Med Central Limit Theorem innebär detta att man behöver färre och färre sampel för att exakt approximera förväntan på skillnaden $G_{\ell }-G_{\ell -1}$ som $\ell \rightarrow \infty$ . Därför kommer de flesta prover att tas på nivå ${\displaystyle 0} ,$ där prover är billiga, och endast mycket få prover kommer att krävas på den finaste nivån $L$ . I denna mening kan MLMC betraktas som en rekursiv kontrollvariatstrategi .

Ansökningar

Approximation av en provväg för en SDE på olika nivåer.

Den första tillämpningen av MLMC tillskrivs Mike Giles, i samband med stokastiska differentialekvationer (SDE) för optionsprissättning, men tidigare spår finns i Heinrichs arbete i samband med parametrisk integration. Här är den slumpmässiga variabeln $G=f(X(T))$ känd som payoff-funktionen, och sekvensen av approximationer $G_{\ell }$ , $\ell =0,\ldots ,L$ använd en approximation till provvägen $X(t)$ med tidssteg $h_{\ell }=2^{-\ell }T$ .

Tillämpningen av MLMC på problem inom osäkerhetskvantifiering (UQ) är ett aktivt forskningsområde. Ett viktigt prototypiskt exempel på dessa problem är partiella differentialekvationer (PDE) med slumpmässiga koefficienter . I detta sammanhang är den slumpmässiga variabeln $G$ känd som kvantiteten av intresse, och sekvensen av approximationer motsvarar en diskretisering av PDE med olika maskstorlekar.

En algoritm för MLMC-simulering

En enkel nivåadaptiv algoritm för MLMC-simulering ges nedan i pseudokod.


      
    
        
    
 $L\gets 0$  repeat  $\ell =0,\ldots ,L$  uppvärmningsprover på nivå  $L$  Beräkna provvariansen på alla nivåer  Definiera det optimala antalet prover  $N_{\ell }$  på alla nivåer  $\ell =0,\ldots ,L$  Ta ytterligare prover på varje nivå  $\ ell$  enligt  $N_{\ell }$  om  $L\geq 2$  sedan  Testa för  konvergensslut  om  inte konvergerat  då  $L\får L+1$  sluta  tills  den konvergerar

Förlängningar av MLMC

Nya utökningar av Monte Carlo-metoden med flera nivåer inkluderar Monte Carlo med flera index, där mer än en förfiningsriktning beaktas, och kombinationen av MLMC med Quasi- Monte Carlo-metoden .

Se även