Skip to main content
Top
Published in: BIT Numerical Mathematics 2/2015

01-06-2015

A continuation multilevel Monte Carlo algorithm

Authors: Nathan Collier, Abdul-Lateef Haji-Ali, Fabio Nobile, Erik von Schwerin, Raúl Tempone

Published in: BIT Numerical Mathematics | Issue 2/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We propose a novel Continuation Multi Level Monte Carlo (CMLMC) algorithm for weak approximation of stochastic models. The CMLMC algorithm solves the given approximation problem for a sequence of decreasing tolerances, ending when the required error tolerance is satisfied. CMLMC assumes discretization hierarchies that are defined a priori for each level and are geometrically refined across levels. The actual choice of computational work across levels is based on parametric models for the average cost per sample and the corresponding variance and weak error. These parameters are calibrated using Bayesian estimation, taking particular notice of the deepest levels of the discretization hierarchy, where only few realizations are available to produce the estimates. The resulting CMLMC estimator exhibits a non-trivial splitting between bias and statistical contributions. We also show the asymptotic normality of the statistical error in the MLMC estimator and justify in this way our error estimate that allows prescribing both required accuracy and confidence in the final result. Numerical results substantiate the above results and illustrate the corresponding computational savings in examples that are described in terms of differential equations either driven by random measures or with random coefficients.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
For the variance estimator, one can also use the unbiased estimator; by dividing by \(\overline{M}_\ell -1\) instead of \({\overline{M}}_\ell \). All discussions in this work still apply.
 
Literature
1.
go back to reference Amestoy, P.R., Duff, I.S., L’Excellent, J.Y., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23, 15–41 (2001)CrossRefMATHMathSciNet Amestoy, P.R., Duff, I.S., L’Excellent, J.Y., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23, 15–41 (2001)CrossRefMATHMathSciNet
2.
go back to reference Amestoy, P.R., Guermouche, A., L’Excellent, J.Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136–156 (2006)CrossRefMathSciNet Amestoy, P.R., Guermouche, A., L’Excellent, J.Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136–156 (2006)CrossRefMathSciNet
3.
go back to reference Babuška, I., Nobile, F., Tempone, R.: A stochastic collocation method for elliptic partial differential equations with random input data. SIAM Rev. 52(2), 317–355 (2010)CrossRefMATHMathSciNet Babuška, I., Nobile, F., Tempone, R.: A stochastic collocation method for elliptic partial differential equations with random input data. SIAM Rev. 52(2), 317–355 (2010)CrossRefMATHMathSciNet
5.
go back to reference Barth, A., Schwab, C., Zollinger, N.: Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients. Numer. Math. 119(1), 123–161 (2011)CrossRefMATHMathSciNet Barth, A., Schwab, C., Zollinger, N.: Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients. Numer. Math. 119(1), 123–161 (2011)CrossRefMATHMathSciNet
6.
go back to reference Charrier, J., Scheichl, R., Teckentrup, A.: Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods. SIAM J. Numer. Anal. 51(1), 322–352 (2013)CrossRefMATHMathSciNet Charrier, J., Scheichl, R., Teckentrup, A.: Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods. SIAM J. Numer. Anal. 51(1), 322–352 (2013)CrossRefMATHMathSciNet
7.
go back to reference Cliffe, K., Giles, M., Scheichl, R., Teckentrup, A.: Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Comput. Vis. Sci. 14(1), 3–15 (2011)CrossRefMATHMathSciNet Cliffe, K., Giles, M., Scheichl, R., Teckentrup, A.: Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Comput. Vis. Sci. 14(1), 3–15 (2011)CrossRefMATHMathSciNet
10.
go back to reference Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxbury Press, Belmont (1996) Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxbury Press, Belmont (1996)
11.
go back to reference Giles, M.: Improved multilevel Monte Carlo convergence using the Milstein scheme. In: Monte Carlo and quasi-Monte Carlo methods 2006, pp. 343–358. Springer, Berlin (2008) Giles, M.: Improved multilevel Monte Carlo convergence using the Milstein scheme. In: Monte Carlo and quasi-Monte Carlo methods 2006, pp. 343–358. Springer, Berlin (2008)
13.
go back to reference Giles, M., Reisinger, C.: Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance. SIAM J. Financ. Math. 3(1), 572–592 (2012)CrossRefMATHMathSciNet Giles, M., Reisinger, C.: Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance. SIAM J. Financ. Math. 3(1), 572–592 (2012)CrossRefMATHMathSciNet
14.
go back to reference Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multidimensional SDEs. In: Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer, Berlin (2013) Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multidimensional SDEs. In: Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer, Berlin (2013)
15.
go back to reference Giles, M., Szpruch, L.: Multilevel Monte Carlo methods for applications in finance, pp. 3–48. World Scientific, Singapore (2013) Giles, M., Szpruch, L.: Multilevel Monte Carlo methods for applications in finance, pp. 3–48. World Scientific, Singapore (2013)
16.
go back to reference Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation. Ann. Appl. Probab. (2014) Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation. Ann. Appl. Probab. (2014)
17.
go back to reference Glasserman, P.: Monte Carlo methods in financial engineering. Applications of Mathematics (New York), vol. 53. Stochastic Modelling and Applied Probability. Springer, New York (2004) Glasserman, P.: Monte Carlo methods in financial engineering. Applications of Mathematics (New York), vol. 53. Stochastic Modelling and Applied Probability. Springer, New York (2004)
20.
go back to reference Hoel, H., Schwerin, E.v., Szepessy, A., Tempone, R.: Adaptive multilevel Monte Carlo simulation. In: Engquist, B., Runborg, O., Tsai, Y.H. (eds.) Numerical Analysis of Multiscale Computations, no. 82 in Lecture Notes in Computational Science and Engineering, pp. 217–234. Springer, New York (2012) Hoel, H., Schwerin, E.v., Szepessy, A., Tempone, R.: Adaptive multilevel Monte Carlo simulation. In: Engquist, B., Runborg, O., Tsai, Y.H. (eds.) Numerical Analysis of Multiscale Computations, no. 82 in Lecture Notes in Computational Science and Engineering, pp. 217–234. Springer, New York (2012)
21.
go back to reference Hunter, J.D.: Matplotlib: a 2D graphics environment. Comput. Sci. Eng. 9(3), 90–95 (2007)CrossRef Hunter, J.D.: Matplotlib: a 2D graphics environment. Comput. Sci. Eng. 9(3), 90–95 (2007)CrossRef
22.
go back to reference Jouini, E., Cvitanić, J., Musiela, M. (eds.): Handbooks in Mathematical Finance. Option Pricing, Interest Rates and Risk Management. Cambridge University Press, Cambridge (2001) Jouini, E., Cvitanić, J., Musiela, M. (eds.): Handbooks in Mathematical Finance. Option Pricing, Interest Rates and Risk Management. Cambridge University Press, Cambridge (2001)
23.
go back to reference Karatzas, I., Shreve, S.E.: Brownian Motion and Stochastic Calculus, Graduate Texts in Mathematics, 2nd edn, vol. 113. Springer, New York (1991) Karatzas, I., Shreve, S.E.: Brownian Motion and Stochastic Calculus, Graduate Texts in Mathematics, 2nd edn, vol. 113. Springer, New York (1991)
24.
go back to reference Kebaier, A.: Statistical Romberg extrapolation: a new variance reduction method and applications to options pricing. Ann. Appl. Probab. 14(4), 2681–2705 (2005)CrossRefMathSciNet Kebaier, A.: Statistical Romberg extrapolation: a new variance reduction method and applications to options pricing. Ann. Appl. Probab. 14(4), 2681–2705 (2005)CrossRefMathSciNet
25.
go back to reference Mordecki, E., Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of diffusions with jumps. SIAM J. Numer. Anal. 46(4), 1732–1768 (2008)CrossRefMATHMathSciNet Mordecki, E., Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of diffusions with jumps. SIAM J. Numer. Anal. 46(4), 1732–1768 (2008)CrossRefMATHMathSciNet
26.
go back to reference Øksendal, B.: Stochastic differential equations. Universitext, 5th edn. Springer, Berlin (1998) Øksendal, B.: Stochastic differential equations. Universitext, 5th edn. Springer, Berlin (1998)
27.
go back to reference Sivia, D.S., Skilling, J.: Data Analysis.: A Bayesian Tutorial, 2nd edn. Oxford University Press, Oxford (2006) Sivia, D.S., Skilling, J.: Data Analysis.: A Bayesian Tutorial, 2nd edn. Oxford University Press, Oxford (2006)
28.
go back to reference Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of stochastic differential equations. Commun. Pure Appl. Math. 54(10), 1169–1214 (2001)CrossRefMATHMathSciNet Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of stochastic differential equations. Commun. Pure Appl. Math. 54(10), 1169–1214 (2001)CrossRefMATHMathSciNet
29.
go back to reference Teckentrup, A.: Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath (2013) Teckentrup, A.: Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath (2013)
30.
go back to reference Teckentrup, A., Scheichl, R., Giles, M., Ullmann, E.: Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients. Numer. Math. 125(3), 569–600 (2013)CrossRefMATHMathSciNet Teckentrup, A., Scheichl, R., Giles, M., Ullmann, E.: Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients. Numer. Math. 125(3), 569–600 (2013)CrossRefMATHMathSciNet
31.
go back to reference Xia, Y., Giles, M.: Multilevel path simulation for jump-diffusion SDEs. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 695–708. Springer, Berlin (2012) Xia, Y., Giles, M.: Multilevel path simulation for jump-diffusion SDEs. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 695–708. Springer, Berlin (2012)
Metadata
Title
A continuation multilevel Monte Carlo algorithm
Authors
Nathan Collier
Abdul-Lateef Haji-Ali
Fabio Nobile
Erik von Schwerin
Raúl Tempone
Publication date
01-06-2015
Publisher
Springer Netherlands
Published in
BIT Numerical Mathematics / Issue 2/2015
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI
https://doi.org/10.1007/s10543-014-0511-3

Other articles of this Issue 2/2015

BIT Numerical Mathematics 2/2015 Go to the issue

Premium Partner