Implementation and analysis of an adaptive multilevel Monte Carlo algorithm

Hoel Håkon (), Erik von Schwerin (), Szepessy Anders () and Tempone Raúl ()
Additional contact information
Hoel Håkon: Applied Mathematics and Computational Sciences, KAUST, Thuwal, Saudi Arabia
Erik von Schwerin: CSQI-MATHICSE, École Polytechnique Fédérale de Lausanne, Switzerland
Szepessy Anders: Department of Mathematics, Royal Institute of Technology (KTH), Stockholm, Sweden
Tempone Raúl: Applied Mathematics and Computational Sciences, KAUST, Thuwal, Saudi Arabia

Monte Carlo Methods and Applications, 2014, vol. 20, issue 1, 1-41

Abstract: We present an adaptive multilevel Monte Carlo (MLMC) method for weak approximations of solutions to Itô stochastic differential equations (SDE). The work [Oper. Res. 56 (2008), 607–617] proposed and analyzed an MLMC method based on a hierarchy of uniform time discretizations and control variates to reduce the computational effort required by a single level Euler–Maruyama Monte Carlo method from 𝒪( TOL -3)${{{\mathcal {O}}({\mathrm {TOL}}^{-3})}}$ to 𝒪( TOL -2log( TOL -1)2)${{{\mathcal {O}}({\mathrm {TOL}}^{-2}\log ({\mathrm {TOL}}^{-1})^{2})}}$ for a mean square error of 𝒪( TOL 2)${{{\mathcal {O}}({\mathrm {TOL}}^2)}}$. Later, the work [Lect. Notes Comput. Sci. Eng. 82, Springer-Verlag, Berlin (2012), 217–234] presented an MLMC method using a hierarchy of adaptively refined, non-uniform time discretizations, and, as such, it may be considered a generalization of the uniform time discretization MLMC method. This work improves the adaptive MLMC algorithms presented in [Lect. Notes Comput. Sci. Eng. 82, Springer-Verlag, Berlin (2012), 217–234] and it also provides mathematical analysis of the improved algorithms. In particular, we show that under some assumptions our adaptive MLMC algorithms are asymptotically accurate and essentially have the correct complexity but with improved control of the complexity constant factor in the asymptotic analysis. Numerical tests include one case with singular drift and one with stopped diffusion, where the complexity of a uniform single level method is 𝒪( TOL -4)${{{\mathcal {O}}({\mathrm {TOL}}^{-4})}}$. For both these cases the results confirm the theory, exhibiting savings in the computational cost for achieving the accuracy 𝒪( TOL )${{{\mathcal {O}}({\mathrm {TOL}})}}$ from 𝒪( TOL -3)${{{\mathcal {O}}({\mathrm {TOL}}^{-3})}}$ for the adaptive single level algorithm to essentially 𝒪( TOL -2log( TOL -1)2)${{{\mathcal {O}}({\mathrm {TOL}}^{-2}\log ({\mathrm {TOL}}^{-1})^2)}}$ for the adaptive MLMC algorithm.

Keywords: Computational finance; Monte Carlo; multilevel; adaptivity; weak approximation; error control; Euler–Maruyama method; a posteriori error estimates; backward dual functions; adjoints (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma-2013-0014 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:20:y:2014:i:1:p:1-41:n:1

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/mcma-2013-0014

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().