Víceúrovňová metoda Monte Carlo - Multilevel Monte Carlo method

Víceúrovňové metody Monte Carlo (MLMC) v numerická analýza jsou algoritmy pro výpočet očekávání které vznikají v stochastické simulace. Stejně jako Metody Monte Carlo, spoléhají se na opakování náhodný výběr, ale tyto vzorky jsou odebírány na různých úrovních přesnosti. Metody MLMC mohou výrazně snížit výpočetní náklady standardních metod Monte Carlo tím, že odeberou většinu vzorků s nízkou přesností a odpovídajícími nízkými náklady a pouze velmi málo vzorků se odebírá s vysokou přesností a odpovídajícími vysokými náklady.

Fotbalová branka

Cílem víceúrovňové metody Monte Carlo je přiblížit očekávaná hodnota ${ displaystyle operatorname {E} [G]}$ z náhodná proměnná ${ displaystyle G}$ to je výstup a stochastická simulace. Předpokládejme, že tuto náhodnou proměnnou nelze simulovat přesně, ale existuje posloupnost aproximací ${ displaystyle G_ {0}, G_ {1}, ldots, G_ {L}}$ se zvyšující se přesností, ale také zvyšujícími se náklady, které konvergují ${ displaystyle G}$ tak jako ${ displaystyle L rightarrow infty}$. Základem víceúrovňové metody je teleskopická částka identita,^[1]

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

to je triviálně uspokojeno kvůli linearitě operátoru očekávání. Každé z očekávání ${ displaystyle operatorname {E} [G _ { ell} -G _ { ell -1}]}$ se pak aproximuje metodou Monte Carlo, což vede k víceúrovňové metodě Monte Carlo. Všimněte si, že odebrání vzorku rozdílu ${ displaystyle G _ { ell} -G _ { ell -1}}$ na úroveň ${ displaystyle ell}$ vyžaduje simulaci obou ${ displaystyle G _ { ell}}$ a ${ displaystyle G _ { ell -1}}$.

Metoda MLMC funguje, pokud odchylky ${ displaystyle operatorname {V} [G _ { ell} -G _ { ell -1}] rightarrow 0}$ tak jako ${ displaystyle ell rightarrow infty}$, což bude případ obou ${ displaystyle G _ { ell}}$ a ${ displaystyle G _ { ell -1}}$ přibližně stejnou náhodnou proměnnou ${ displaystyle G}$. Podle Teorém centrálního limitu, to znamená, že k přesné aproximaci očekávání rozdílu je potřeba stále méně vzorků ${ displaystyle G _ { ell} -G _ { ell -1}}$ tak jako ${ displaystyle ell rightarrow infty}$. Proto bude většina vzorků odebrána na úrovni ${ displaystyle 0}$, kde jsou vzorky levné a na nejlepší úrovni bude vyžadováno jen velmi málo vzorků ${ displaystyle L}$. V tomto smyslu lze MLMC považovat za rekurzivní ovládání se mění strategie.

Aplikace

Aproximace cesty vzorku SDE na různých úrovních.

První aplikace MLMC je přičítána Gilesovi,^[2] v kontextu stochastické diferenciální rovnice (SDE) pro ceny opcí dřívější stopy se však v práci Heinricha nacházejí v kontextu parametrické integrace.^[3] Zde náhodná proměnná ${ displaystyle G = f (X (T))}$ je známá jako funkce výplaty a posloupnost aproximací ${ displaystyle G _ { ell}}$, ${ displaystyle ell = 0, ldots, L}$ použijte aproximaci k cestě vzorku ${ displaystyle X (t)}$ s časovým krokem ${ displaystyle h _ { ell} = 2 ^ {- ell} T}$.

Aplikace MLMC na problémy v roce 2006 kvantifikace nejistoty (UQ) je aktivní oblastí výzkumu.^[4][5] Důležitým prototypovým příkladem těchto problémů jsou parciální diferenciální rovnice (PDE) s náhodné koeficienty. V této souvislosti náhodná proměnná ${ displaystyle G}$ je známá jako kvantita zájmu a posloupnost aproximací odpovídá a diskretizace PDE s různými velikostmi ok.

Algoritmus pro simulaci MLMC

Níže je v pseudokódu uveden jednoduchý algoritmus adaptivní na úroveň pro simulaci MLMC.

${ displaystyle L  dostane 0}$opakovat    Odeberte zahřívací vzorky na úrovni ${ displaystyle L}$    Vypočítejte rozptyl vzorku na všech úrovních ${ displaystyle  ell = 0,  ldots, L}$    Definujte optimální počet vzorků ${ displaystyle N _ { ell}}$ na všech úrovních ${ displaystyle  ell = 0,  ldots, L}$    Odeberte další vzorky na každé úrovni ${ displaystyle  ell}$ podle ${ displaystyle N _ { ell}}$    -li ${ displaystyle L  geq 2}$ pak        Test konvergence konec    -li nekonvergované pak        ${ displaystyle L  dostane L + 1}$    konecdokud konvergované

Rozšíření MLMC

Nedávná rozšíření víceúrovňové metody Monte Carlo zahrnují více indexové Monte Carlo,^[6] kde je zvažován více než jeden směr zdokonalení a kombinace MLMC s Metoda kvazi-Monte Carla.^[7][8]

Viz také

• Metoda Monte Carlo
• Metody Monte Carlo ve financích
• Kvazi-Monte Carlo metody ve financích
• Kvantifikace nejistoty
• Parciální diferenciální rovnice s náhodnými koeficienty

Reference