Implementation and Analysis of an Adaptive Multilevel Monte Carlo Algorithm
2012 (English)Report (Other academic)
This work generalizes a multilevel Monte Carlo (MLMC) method in-troduced in  for the approximation of expected values of functions depending on the solution to an Ito stochastic differential equation. The work  proposed and analyzed a forward Euler MLMC method based on a hierarchy of uniform time discretizations and control variates to reduce the computational effort required by a standard, single level, forward Euler Monte Carlo method from O( TOL^(−3) ) to O( TOL^(−2) log( TOL^(−1))^2 ) for a meansquare error of size 2 . This work uses instead a hierarchy of adaptivelyrefined, non uniform, time discretizations, generated by an adaptive algo-rithm introduced in [20, 19, 5]. Given a prescribed accuracy TOL in theweak error, this adaptive algorithm generates time discretizations basedon a posteriori expansions of the weak error first developed in . Atheoretical analysis gives results on the stopping, the accuracy, and thecomplexity of the resulting adaptive MLMC algorithm. In particular, it isshown that: the adaptive refinements stop after a finite number of steps;the probability of the error being smaller than TOL is under certain as-sumptions controlled by a given confidence parameter, asymptotically asTOL → 0; the complexity is essentially the expected for MLMC methods,but with better control of the constant factors. We also show that themultilevel estimator is asymptotically normal using the Lindeberg-FellerCentral Limit Theorem. These theoretical results are based on previouslydeveloped single level estimates, and results on Monte Carlo stoppingfrom . Our numerical tests include cases, one with singular drift andone with stopped diffusion, where the complexity of uniform single levelmethod is O TOL−4 . In both these cases the results confirm the theoryby exhibiting savings in the computational cost to achieve an accuracy of O(TOL), from O( TOL^(−3) )for the adaptive single level algorithm toessentially O( TOL^(−2) log(TOL−1)^2 ) for the adaptive MLMC.
Place, publisher, year, edition, pages
2012. , 57 p.
Trita-NA, ISSN 0348-2952 ; 2012:6
computational finance; Monte Carlo; multi-level; adaptivity; weak approximation
Probability Theory and Statistics Computer Engineering
IdentifiersURN: urn:nbn:se:kth:diva-94108OAI: oai:DiVA.org:kth-94108DiVA: diva2:525328
QC 201205082012-05-082012-05-072012-05-08Bibliographically approved