Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T12:48:29.209Z Has data issue: false hasContentIssue false
  • English
  • Français

Multilevel Monte Carlo methods

Published online by Cambridge University Press:  27 April 2015

Michael B. Giles
Michael B. Giles*
Affiliation:
Mathematical Institute, University of Oxford, Woodstock Road, Oxford OX2 6GG, UK E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Monte Carlo methods are a very general and useful approach for the estimation of expectations arising from stochastic simulation. However, they can be computationally expensive, particularly when the cost of generating individual stochastic samples is very high, as in the case of stochastic PDEs. Multilevel Monte Carlo is a recently developed approach which greatly reduces the computational cost by performing most simulations with low accuracy at a correspondingly low cost, with relatively few simulations being performed at high accuracy and a high cost.

In this article, we review the ideas behind the multilevel Monte Carlo method, and various recent generalizations and extensions, and discuss a number of applications which illustrate the flexibility and generality of the approach and the challenges in developing more efficient implementations with a faster rate of convergence of the multilevel correction variance.

Type
Research Article
Information
Acta Numerica , Volume 24 , 01 May 2015 , pp. 259 - 328
Copyright
© Cambridge University Press, 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES 3

Andersen, L. and Broadie, M. (2004), ‘A primal–dual simulation algorithm for pricing multi-dimensional American options’, Management Sci. 50, 1222–1234.CrossRefGoogle Scholar
Anderson, D. and Higham, D. (2012), ‘Multi-level Monte Carlo for continuous time Markov chains with applications in biochemical kinetics’, SIAM Multiscale Model. Simul. 10, 146–179.CrossRefGoogle Scholar
Anderson, D., Higham, D. and Sun, Y. (2014), ‘Complexity of multilevel Monte Carlo tau-leaping’, SIAM J. Numer. Anal. 52, 3106–3127.CrossRefGoogle Scholar
Asmussen, A. and Glynn, P. (2007), Stochastic Simulation, Springer.Google Scholar
Avikainen, R. (2009), ‘On irregular functionals of SDEs and the Euler scheme’, Finance Stoch. 13, 381–401.CrossRefGoogle Scholar
Babuška, I., Nobile, F. and Tempone, R. (2010), ‘A stochastic collocation method for elliptic partial differential equations with random input data’, SIAM Rev. 52, 317–355.Google Scholar
Babuška, I., Tempone, R. and Zouraris, G. (2004), ‘Galerkin finite element approximations of stochastic elliptic partial differential equations’, SIAM J. Numer. Anal. 42, 800–825.CrossRefGoogle Scholar
Baldeaux, J. and Gnewuch, M. (2014), ‘Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition’, SIAM J. Numer. Anal. 52, 1128–1155.Google Scholar
Barth, A., Lang, A. and Schwab, C. (2013), ‘Multilevel Monte Carlo method for parabolic stochastic partial differential equations’, BIT Numer. Math. 53, 3–27.Google Scholar
Barth, A., Schwab, C. and Zollinger, N. (2011), ‘Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients’, Numer. Math. 119, 123–161.CrossRefGoogle Scholar
Belomestny, D., Schoenmakers, J. and Dickmann, F. (2013), ‘Multilevel dual approach for pricing American style derivatives’, Finance Stoch. 17, 717–742.CrossRefGoogle Scholar
Brandt, A. and Ilyin, V. (2003), ‘Multilevel Monte Carlo methods for studying large scale phenomena in fluids’, J. Molecular Liquids 105, 245–248.CrossRefGoogle Scholar
Brandt, A., Galun, M. and Ron, D. (1994), ‘Optimal multigrid algorithms for calculating thermodynamic limits’, J. Statist. Phys. 74, 313–348.CrossRefGoogle Scholar
Broadie, M. and Glasserman, P. (1996), ‘Estimating security price derivatives using simulation’, Management Sci. 42, 269–285.Google Scholar
Brugger, C., de Schryver, C., Wehn, N., Omland, S., Hefter, M., Ritter, K., Kostiuk, A. and Korn, R. (2014), Mixed precision multilevel Monte Carlo on hybrid computing systems. In Proc. Conference on Computational Intelligence for Financial Engineering and Economics, IEEE.Google Scholar
Bujok, K. and Reisinger, C. (2012), ‘Numerical valuation of basket credit derivatives in structural jump-diffusion models’, J. Comput. Finance 15, 115–158.Google Scholar
Bujok, K., Hambly, B. and Reisinger, C. (2013), ‘Multilevel simulation of functionals of Bernoulli random variables with application to basket credit derivatives’, Methodol. Comput. Appl. Probab. doi:10.1007/s11009-013-9380-5 Google Scholar
Bungartz, H.-J. and Griebel, M. (2004), Sparse grids. In Acta Numerica, Vol. 13, Cambridge University Press, pp. 147–269.Google Scholar
Burgos, S. (2014), The computation of Greeks with multilevel Monte Carlo. DPhil thesis, University of Oxford.Google Scholar
Burgos, S. and Giles, M. (2012), Computing Greeks using multilevel path simulation. In Monte Carlo and Quasi-Monte Carlo Methods 2010 (Plaskota, L. and Woźniakowski, H., eds), Springer, pp. 281–296.CrossRefGoogle Scholar
Charrier, J., Scheichl, R. and Teckentrup, A. (2013), ‘Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods’, SIAM J. Numer. Anal. 51, 322–352.Google Scholar
Chen, N. and Liu, Y. (2012), Estimating expectations of functionals of conditional expected via multilevel nested simulation. Presentation at conference on Monte Carlo and Quasi-Monte Carlo Methods, Sydney.Google Scholar
Clark, J. and Cameron, R. (1980), The maximum rate of convergence of discrete approximations for stochastic differential equations. In Stochastic Differential Systems Filtering and Control (Grigelionis, B., ed.), Vol. 25 of Lecture Notes in Control and Information Sciences , Springer, pp. 162–171.CrossRefGoogle Scholar
Cliffe, K., Giles, M., Scheichl, R. and Teckentrup, A. (2011), ‘Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients’, Comput. Visualization Sci. 14, 3–15.Google Scholar
Collier, N., Haji-Ali, A.-L., Nobile, F., von Schwerin, E. and Tempone, R. (2014), ‘A continuation multilevel Monte Carlo algorithm’, BIT Numer. Math. doi:10.1007/s10543-014-0511-3 Google Scholar
Creutzig, J., Dereich, S., Müller-Gronbach, T. and Ritter, K. (2009), ‘Infinite-dimensional quadrature and approximation of distributions’, Found. Comput. Math. 9, 391–429.CrossRefGoogle Scholar
Daun, T. and Heinrich, S. (2013), Complexity of Banach space valued and parametric integration. In Monte Carlo and Quasi-Monte Carlo Methods 2012 (Dick, J., Kuo, F., Peters, G. and Sloan, I., eds), Springer, pp. 297–316.CrossRefGoogle Scholar
Daun, T. and Heinrich, S. (2014a), ‘Complexity of parametric initial value problems in Banach spaces’, J. Complexity 30, 392–429.Google Scholar
Daun, T. and Heinrich, S. (2014b), ‘Complexity of parametric integration in various smoothness classes’, J. Complexity 30, 750–766.Google Scholar
Dereich, S. (2011), ‘Multilevel Monte Carlo algorithms for Lévy-driven SDEs with Gaussian correction’, Ann. Appl. Probab. 21, 283–311.CrossRefGoogle Scholar
Dereich, S. and Heidenreich, F. (2011), ‘A multilevel Monte Carlo algorithm for Lévy-driven stochastic differential equations’, Stochastic Process. Appl. 121, 1565–1587.CrossRefGoogle Scholar
Dereich, S., Neuenkirch, A. and Szpruch, L. (2012), ‘An Euler-type method for the strong approximation of the Cox–Ingersoll–Ross process’, Proc. Royal Soc. A 468(2140), 1105–1115.CrossRefGoogle Scholar
Dick, J. and Gnewuch, M. (2014a), ‘Infinite-dimensional integration in weighted Hilbert spaces: Anchored decompositions, optimal deterministic algorithms, and higher-order convergence’, Found. Comput. Math. 14, 1027–1077.Google Scholar
Dick, J. and Gnewuch, M. (2014b), ‘Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition’, J. Approx. Theory 184, 111–145.Google Scholar
Dick, J., Kuo, F. and Sloan, I. (2013), High-dimensional integration: The quasi-Monte Carlo way. In Acta Numerica, Vol. 22, Cambridge University Press, pp. 133–288.Google Scholar
Dick, J., Pillichshammer, F. and Waterhouse, B. (2007), ‘The construction of good extensible rank-1 lattices’, Math. Comp. 77, 2345–2373.CrossRefGoogle Scholar
Dietrich, C. and Newsam, G. (1997), ‘Fast and exact simulation of stationary Gaussian processes through circulant embedding of the covariance matrix’, SIAM J. Sci. Comput. 18, 1088–1107.CrossRefGoogle Scholar
Efendiev, Y., Iliev, O. and Kronsbein, C. (2013), ‘Multilevel Monte Carlo methods using ensemble level mixed MsFEM for two-phase flow and transport simulations’, Comput. Geosci. 17, 833–850.CrossRefGoogle Scholar
Ferreiro-Castilla, A., Kyprianou, A., Scheichl, R. and Suryanarayana, G. (2014), ‘Multi-level Monte-Carlo simulation for Lévy processes based on the Wiener–Hopf factorisation’, Stochastic Process. Appl. 124, 985–1010.Google Scholar
Giles, M. (2008a), Improved multilevel Monte Carlo convergence using the Milstein scheme. In Monte Carlo and Quasi-Monte Carlo Methods 2006 (Keller, A., Heinrich, S. and Niederreiter, H., eds), Springer, pp. 343–358.Google Scholar
Giles, M. (2008b), ‘Multilevel Monte Carlo path simulation’, Operations Research 56, 607–617.Google Scholar
Giles, M. (2009), Multilevel Monte Carlo for basket options. In Proc. 2009 Winter Simulation Conference (Rossetti, M., Hill, R., Johansson, B., Dunkin, A. and Ingalls, R., eds), IEEE, pp. 1283–1290.Google Scholar
Giles, M. (2013), Multilevel Monte Carlo methods. In Monte Carlo and Quasi-Monte Carlo Methods 2012 (Dick, J., Kuo, F., Peters, G. and Sloan, I., eds), Springer, pp. 79–98.Google Scholar
Giles, M. (2014), MATLAB code for multilevel Monte Carlo computations. http://people.maths.ox.ac.uk/gilesm/acta/ Google Scholar
Giles, M. and Reisinger, C. (2012), ‘Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance’, SIAM J. Financial Math. 3, 572–592.Google Scholar
Giles, M. and Szpruch, L. (2013), Antithetic multilevel Monte Carlo estimation for multidimensional SDEs. In Monte Carlo and Quasi-Monte Carlo Methods 2012 (Dick, J., Kuo, F., Peters, G. and Sloan, I., eds), Springer, pp. 367–384.Google Scholar
Giles, M. and Szpruch, L. (2014), ‘Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation’, Ann. Appl. Probab. 24, 1585–1620.Google Scholar
Giles, M. and Waterhouse, B. (2009), Multilevel quasi-Monte Carlo path simulation. In Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics, De Gruyter, pp. 165–181.CrossRefGoogle Scholar
Giles, M., Debrabant, K. and Rößler, A. (2013), Numerical analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. arXiv:1302.4676 Google Scholar
Giles, M., Higham, D. and Mao, X. (2009), ‘Analysing multilevel Monte Carlo for options with non-globally Lipschitz payoff’, Finance Stoch. 13, 403–413.Google Scholar
Giles, M., Lester, C. and Whittle, J. (2015a), Simple adaptive timestepping for multilevel Monte Carlo. In Monte Carlo and Quasi-Monte Carlo Methods 2014, Springer, to appear.Google Scholar
Giles, M., Nagapetyan, T. and Ritter, K. (2015b), ‘Multilevel Monte Carlo approximation of distribution functions and densities’, SIAM/ASA J. Uncertainty Quantification, to appear.Google Scholar
Gillespie, D. (1976), ‘A general method for numerically simulating the stochastic time evolution of coupled chemical reactions’, J. Comput. Phys. 22, 403–434.Google Scholar
Glasserman, P. (2004), Monte Carlo Methods in Financial Engineering, Springer.Google Scholar
Glasserman, P. and Merener, N. (2004), ‘Convergence of a discretization scheme for jump-diffusion processes with state-dependent intensities’, Proc. Royal Soc. London A 460, 111–127.CrossRefGoogle Scholar
Glynn, P. and Rhee, C.-H. (2014), ‘Exact estimation for Markov chain equilibrium expectations’, J. Appl. Probab. 51A, 377–389.Google Scholar
Gobet, E. and Menozzi, S. (2010), ‘Stopped diffusion processes: overshoots and boundary correction’, Stochastic Process. Appl. 120, 130–162.Google Scholar
Graubner, S. (2008), Multi-level Monte Carlo Methoden für stochastische partielle Differentialgleichungen. Diplomarbeit, TU Darmstadt.Google Scholar
Gunzburger, M., Webster, C. and Zhang, G. (2014), Stochastic finite element methods for partial differential equations with random input data. In Acta Numerica, Vol. 23, Cambridge University Press, pp. 521–650.Google Scholar
Haji-Ali, A.-L. (2012), Pedestrian flow in the mean-field limit. MSc thesis, KAUST.Google Scholar
Haji-Ali, A.-L., Nobile, F. and Tempone, R. (2014a), Multi Index Monte Carlo: When sparsity meets sampling. arXiv:1405.3757 Google Scholar
Haji-Ali, A.-L., Nobile, F., von Schwerin, E. and Tempone, R. (2014b), Optimization of mesh hierarchies in multilevel Monte Carlo samplers. arXiv:1403.2480 CrossRefGoogle Scholar
Heinrich, S. (1998), ‘Monte Carlo complexity of global solution of integral equations’, J. Complexity 14, 151–175.CrossRefGoogle Scholar
Heinrich, S. (2000), The multilevel method of dependent tests. In Advances in Stochastic Simulation Methods (Balakrishnan, N., Melas, V. and Ermakov, S., eds), Springer, pp. 47–61.CrossRefGoogle Scholar
Heinrich, S. (2001), Multilevel Monte Carlo methods. In Multigrid Methods, Vol. 2179 of Lecture Notes in Computer Science , Springer, pp. 58–67.Google Scholar
Heinrich, S. (2006), ‘Monte Carlo approximation of weakly singular integral operators’, J. Complexity 22, 192–219.Google Scholar
Heinrich, S. and Sindambiwe, E. (1999), ‘Monte Carlo complexity of parametric integration’, J. Complexity 15, 317–341.Google Scholar
Higham, D., Mao, X. and Stuart, A. (2002), ‘Strong convergence of Euler-type methods for nonlinear stochastic differential equations’, SIAM J. Numer. Anal. 40, 1041–1063.CrossRefGoogle Scholar
Higham, D., Mao, X., Roj, M., Song, Q. and Yin, G. (2013), ‘Mean exit times and the multi-level Monte Carlo method’, SIAM J. Uncertainty Quantification 1, 2–18.Google Scholar
Hoel, H., von Schwerin, E., Szepessy, A. and Tempone, R. (2012), Adaptive multilevel Monte Carlo simulation. In Numerical Analysis of Multiscale Computations, (Engquist, B., Runborg, O. and Tsai, Y.-H., eds), Vol. 82 of Lecture Notes in Computational Science and Engineering , Springer, pp. 217–234.Google Scholar
Hoel, H., von Schwerin, E., Szepessy, A. and Tempone, R. (2014), ‘Implementation and analysis of an adaptive multilevel Monte Carlo algorithm’, Monte Carlo Methods Appl. 20, 1–41.Google Scholar
Hutzenthaler, M., Jentzen, A. and Kloeden, P. (2013), ‘Divergence of the multilevel Monte Carlo method’, Ann. Appl. Probab. 23, 1913–1966.Google Scholar
Iliev, O., Nagapetyan, T. and Ritter, K. (2013), Monte Carlo simulation of asymmetric flow field flow fractionation. In Monte Carlo Methods and Applications: Proc. 8th IMACS Seminar on Monte Carlo Methods, de Gruyter, pp. 115–123.Google Scholar
Joe, S. and Kuo, F. (2008), ‘Constructing Sobol sequences with better two-dimensional projections’, SIAM J. Sci. Comput. 30, 2635–2654.Google Scholar
Kebaier, A. (2005), ‘Statistical Romberg extrapolation: A new variance reduction method and applications to options pricing’, Ann. Appl. Probab. 14, 2681–2705.Google Scholar
Kebaier, A. and Kohatsu-Higa, A. (2008), ‘An optimal control variance reduction method for density estimation’, Stochastic Process. Appl. 118, 2143–2180.Google Scholar
Kloeden, P. and Platen, E. (1992), Numerical Solution of Stochastic Differential Equations, Springer.Google Scholar
Kuo, F., Schwab, C. and Sloan, I. (2015), ‘Multi-level quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients’. Found. Comput. Math. 15, 411–449.Google Scholar
Kurtz, T. (1982), Representation and approximation of counting processes. In Advances in Filtering and Optimal Stochastic Control, Vol. 42, Springer, pp. 177–191.Google Scholar
L’Ecuyer, P. (1990), ‘A unified view of the IPA SF and LR gradient estimation techniques’, Management Sci. 36, 1364–1383.Google Scholar
Ledoux, M. and Talagrand, M. (1991), Probability in Banach Spaces: Isoperimetry and Processes, Springer.Google Scholar
Lemaire, V. and Pagès, G. (2013), Multilevel Richardson–Romberg extrapolation. arXiv:1401.1177 Google Scholar
Lester, C., Yates, C., Giles, M. and Baker, R. (2015), ‘An adapted multi-level simulation algorithm for stochastic biological systems’, J. Chem. Phys., to appear.Google Scholar
Li, Q. (2007), Numerical approximation for SDE. PhD thesis, University of Edinburgh.Google Scholar
Marxen, H. (2010), ‘The multilevel Monte Carlo method used on a Lévy driven SDE’, Monte Carlo Methods Appl. 16, 167–190.Google Scholar
Merton, R. (1976), ‘Option pricing when underlying stock returns are discontinuous’, J. Finance 3, 125–144.Google Scholar
Mikulevicius, R. and Platen, E. (1988), ‘Time discrete Taylor approximations for Itô processes with jump component’, Mathematische Nachrichten 138, 93–104.Google Scholar
Mishra, S., Schwab, C. and Sukys, J. (2012), ‘Multi-level Monte Carlo finite volume methods for nonlinear systems of conservation laws in multi-dimensions’, J. Comput. Phys. 231, 3365–3388.Google Scholar
Moraes, A., Tempone, R. and Vilanova, P. (2014), A multilevel adaptive reaction-splitting simulation method for stochastic reaction networks. arXiv:1406.1989 Google Scholar
Moraes, A., Tempone, R. and Vilanova, P. (2015), ‘Multilevel hybrid Chernoff tau-leap’, BIT Numer. Math., to appear.Google Scholar
Müller, F., Jenny, P. and Meyer, D. (2013), ‘Multilevel Monte Carlo for two phase flow and Buckley–Leverett transport in random heterogeneous porous media’, J. Comput. Phys. 250, 685–702.CrossRefGoogle Scholar
Niu, B., Hickernell, F., Müller-Gronbach, T. and Ritter, K. (2010), ‘Deterministic multi-level algorithms for infinite-dimensional integration on $\mathbb{R}^{N}$ ’, J. Complexity 27, 331–351.Google Scholar
Platen, E. and Bruti-Liberati, N. (2010), Numerical Solution of Stochastic Differential Equations With Jumps in Finance, Springer.CrossRefGoogle Scholar
Primozic, T. (2011), Estimating expected first passage times using multilevel Monte Carlo algorithm. MSc thesis, University of Oxford.Google Scholar
Putko, M., Taylor, A., Newman, P. and Green, L. (2002), ‘Approach for input uncertainty propagation and robust design in CFD using sensitivity derivatives’, J. Fluids Engng 124, 60–69.Google Scholar
Rhee, C.-H. and Glynn, P. (2012), A new approach to unbiased estimation for SDEs. In Proc. 2012 Winter Simulation Conference, IEEE.Google Scholar
Rhee, C.-H. and Glynn, P. (2015), ‘Unbiased estimation with square root convergence for SDE models’, Operations Research, to appear.Google Scholar
Rosin, M., Ricketson, L., Dimits, A., Caflisch, R. and Cohen, B. (2014), ‘Multilevel Monte Carlo simulation of Coulomb collisions’, J. Comput. Phys. 247, 140–157.CrossRefGoogle Scholar
Schoutens, W. (2003), Lévy Processes in Finance: Pricing Financial Derivatives, Wiley.Google Scholar
Silverman, B. (1986), Density Estimation for Statistics and Data Analysis, Chapman & Hall.Google Scholar
Speight, A. (2009), ‘A multilevel approach to control variates’, J. Comput. Finance 12, 1–25.Google Scholar
Teckentrup, A. (2013), Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath.Google Scholar
Teckentrup, A., Scheichl, R., Giles, M. and Ullmann, E. (2013), ‘Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients’, Numer. Math. 125, 569–600.Google Scholar
Vidal-Codina, F., Nguyen, N., Giles, M. and Peraire, J. (2014), A model and variance reduction method for computing statistical outputs of stochastic elliptic partial differential equations. arXiv:1409.1526 Google Scholar
Xia, Y. (2014), Multilevel Monte Carlo for jump processes. DPhil thesis, University of Oxford.Google Scholar
Xia, Y. and Giles, M. (2012), Multilevel path simulation for jump-diffusion SDEs. In Monte Carlo and Quasi-Monte Carlo Methods 2010 (Plaskota, L. and Woźniakowski, H., eds), Springer, pp. 695–708.Google Scholar
Xia, Y. and Giles, M. (2014), Multilevel Monte Carlo for exponential Lévy models. arXiv:1403.5309 Google Scholar
Xiu, D. and Karniadakis, G. (2002), ‘The Wiener–Askey polynomial chaos for stochastic differential equations’, SIAM J. Sci. Comput. 24, 619–644.Google Scholar