Multilevel Monte Carlo methods

My main research on Monte Carlo methods concerns the development of multilevel methods.

Inspired by multigrid ideas for the iterative solution of discretised PDEs, this can be viewed as a recursive control variate approach which combines stochastic simulations with differing levels of resolution. This results in a significant reduction in the order of complexity, the computational cost required to obtain a user-specified accuracy.

Publications

1. M.B. Giles. 'Multi-level Monte Carlo path simulation'. Operations Research, 56(3):607-617, 2008. (PDF)

This is my original multilevel paper. It presents numerical results for SDEs using an Euler discretisation, but also analyses the computational complexity for a general class of methods and applications, assuming that the discretisation satisfies certain conditions.

The MATLAB code used to produce the figures for the paper is available here.

2. M.B. Giles. `Improved multilevel Monte Carlo convergence using the Milstein scheme'. 343-358, in Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer, 2008. (PDF)

This paper presents significantly improved numerical results using the Milstein discretisation. The Milstein method's improved strong convergence leads to most of the computational effort being confined to the coarsest levels.

The MATLAB code used to produce the figures for the paper is available here.

3. M.B. Giles, D.J. Higham and X. Mao. 'Analysing multilevel Monte Carlo for options with non-globally Lipschitz payoff'. Finance and Stochastics, 13(3):403-413, 2009. (PDF)

This was a collaboration with Des Higham and Xuerong Mao from the University of Strathclyde, in which we performed a numerical analysis of the multilevel Euler-Maruyama method in the first paper.

4. M.B. Giles and B.J. Waterhouse. 'Multilevel quasi-Monte Carlo path simulation'. pp.165-181 in Advanced Financial Modelling, in Radon Series on Computational and Applied Mathematics, de Gruyter, 2009. (PDF)

This was a collaboration with Ben Waterhouse of the University of New South Wales. It uses randomised quasi-Monte Carlo techniques based on a rank-1 lattice rule to further improve the computational efficiency.

5. M.B. Giles. `Multilevel Monte Carlo for Basket Options'. Winter Simulation Conference '09. (PDF)

This is a numerical verification that the Multilevel Milstein treatment also works well for basket options.

6. K.A. Cliffe, M.B. Giles, R. Scheichl, A.L. Teckentrup, 'Multilevel Monte Carlo Methods and Applications to Elliptic PDEs with Random Coefficients', Computing and Visualization in Science, 14(1):3-15, 2011. (PDF)

This is a collaboration with Rob Scheichl and Aretha Teckentrup at the University of Bath, and Andrew Cliffe at the University of Nottingham. This applies the multilevel approach to elliptic SPDEs which arise in the modelling of nuclear waste repositories, with the permeability of the rock being modelled as a log-Normal stochastic field.

7. Y. Xia, M.B. Giles. `Multilevel path simulation for jump-diffusion SDEs', pp.695-708 in Monte Carlo and Quasi-Monte Carlo Methods 2010, Springer, 2012. (PDF)

This paper with my student Yuan Xia tackles Merton-style jump-diffusion models. The key feature of this paper is the use of a change of measure to cope with cases in which the jump rate is path-dependent which would otherwise lead to jumps at different times on coarse and fine paths.

8. S. Burgos, M.B. Giles. `Computing Greeks using multilevel path simulation', pp.281-296 in Monte Carlo and Quasi-Monte Carlo Methods 2010, Springer, 2012. (PDF)

This paper with my student Sylvestre Burgos deals with the calculation of sensitivities. This involves differentiating the payoff, and the loss of smoothness causes difficulties for the multilevel method.

9. M.B. Giles, C. Reisinger. 'Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance', SIAM Journal of Financial Mathematics, 3(1):572-592, 2012. (PDF)

This is a collaboration with my colleague Christoph Reisinger. It is another SPDE application, but in this case it is an unusual parabolic SPDE which arises in a financial credit modelling application. One key aspect of this paper is the proof of mean square stability.

10. A.L. Teckentrup, R. Scheichl, M.B. Giles, E. Ullmann. Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients', Numerische Mathematik, 125(3):569-600, 2013. (PDF)

This paper continues the collaboration with Rob Scheichl and Aretha Teckentrup at the University of Bath.

11. M.B. Giles, L. Szpruch. 'Multilevel Monte Carlo methods for applications in finance', in Recent Developments in Computational Finance, World Scientific, 2013. (PDF)

This is a survey article looking at the application of multilevel methods in computational finance.

12. M.B. Giles, L. Szpruch. 'Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation', Annals of Applied Probability, 24(4):1585-1620, 2014. (PDF)

This paper addresses the use of the Milstein approximation in multiple dimensions. This usually requires the simulation of Lévy areas, but we have developed an antithetic technique which gives a high rate of multilevel convergence without simulating Lévy areas, and this paper includes a lengthy numerical analysis of this.

13. M.B. Giles. 'Multilevel Monte Carlo methods', pp.79-98 in Monte Carlo and Quasi-Monte Carlo Methods 2012, Springer, 2014. (PDF)

This is a survey article for the proceedings of MCQMC12 based on my plenary lecture.

14. M.B. Giles, L. Szpruch. 'Antithetic multilevel Monte Carlo estimation for multidimensional SDEs', pp.297-312 in Monte Carlo and Quasi-Monte Carlo Methods 2012, Springer, 2014. (PDF)

This paper is an extension to paper #13, including an approximation to Lévy areas to efficiently compute digital and barrier options.

15. C. Lester, C. Yates, M.B. Giles, R.E. Baker. 'An adaptive multi-level simulation algorithm for stochastic biological systems'. Journal of Chemical Physics, 142(2):2015. (PDF)
16. M.B. Giles, T. Nagapetyan, K. Ritter. 'Multilevel Monte Carlo approximation of distribution functions and densities'. SIAM/ASA Journal on Uncertainty Quantification, 3:267-295, 2015. (PDF).

This paper extends MLMC analysis to the estimation of cumulative distribution functions and probability densities.

17. M.B. Giles. 'Multilevel Monte Carlo methods'. Acta Numerica, 24:259-328, 2015. (PDF)

This is a 70-page review article -- MATLAB code for all of the test cases presented is available here.

18. F. Vidal-Codina, N.C. Nguyen, M.B. Giles, J. Peraire. 'A model and variance reduction method for computing statistical outputs of stochastic elliptic partial differential equations'. Journal of Computational Physics, 297:700-720, 2015. (PDF)

This paper is slightly unusual in using MLMC in an application where there is not a natural geometric sequence of levels. Instead, it determines empirically the best sequence of levels to use.

19. M.B. Giles, C. Lester, J. Whittle. 'Non-nested adaptive timesteps in multilevel Monte Carlo computations'. Monte Carlo and Quasi-Monte Carlo Methods 2014, Springer, 2015. (PDF)

This short paper explains that it is easy to use adaptive timestepping within multilevel Monte Carlo, for both SDEs and continuous-time Markov processes.

20. F. Vidal-Codina, N.C. Nguyen, M.B. Giles, J. Peraire. 'An empirical interpolation and model-variance reduction method for computing statistical outputs of parametrized stochastic partial differential equations'. SIAM/ASA Journal on Uncertainty Quantification, 4(1):244-265, 2016. link

This paper is a continuation of the previous collaboration.

21. C. Lester, R.E. Baker, M.B. Giles, C.A. Yates. 'Extending the multi-level method for the simulation of stochastic biological systems'. Bulletin of Mathematical Biology, 78(8):1640-1677, 2016. link

22. W. Fang, M.B. Giles. 'Adaptive Euler-Maruyama method for SDEs with non-globally Lipschitz drift: Part I, finite time interval'. arXiv pre-print, 2016. link
W. Fang, M.B. Giles. 'Adaptive Euler-Maruyama method for SDEs with non-globally Lipschitz drift: Part II, infinite time interval'. arXiv pre-print, 2017. link

These two papers analyse adaptive time-stepping for SDEs with a drift which is not globally Lipschitz. This follows on from the earlier paper with Lester and Whittle.

23. M.B. Giles, T. Nagapetyan, K. Ritter. 'Adaptive multilevel Monte Carlo approximation of distribution functions'. arXiv pre-print, 2017. link

This paper extends our previous paper on this topic by developing a fully-automated adaptive procedure to select the key parameters in the MLMC algorithm.

24. M.B. Giles, Y. Xia. 'Multilevel Monte Carlo for exponential Lévy models'. Finance and Stochastics, 21(4):995-1026, 2017. link

This paper analyses the MLMC variance for financial options based on exponential Lévy models.

25. G. Katsiolides, E.H. Muller, R. Scheichl, T. Shardlow, M.B. Giles, D.J. Thomson. 'Multilevel Monte Carlo and improved timestepping methods in atmospheric dispersion modelling'. Journal of Computational Physics, 354:320-343, 2018. link

This paper looks at MLMC for particle dispersion modelling. In particular it develops a more efficient MLMC treatment of particle reflections at a boundary.

26. M.B. Giles. 'MLMC for Nested Expectations'. Festschrift for 80th Birthday of Ian Sloan, Springer, 2018. link

This paper discusses the application and analysis of MLMC methods for different kinds of nested expectations.

27. M.B. Giles, F.Y. Kuo, I.H. Sloan. 'Combining sparse grids, multilevel MC and QMC for elliptic PDEs with random coefficients'. Monte Carlo and Quasi-Monte Carlo Methods 2016, Springer, 2018. link

This paper has a number of meta-theorems (similar to the original MLMC theorem) which look at the complexity of various MLMC/MLQMC generalisations. It also contains a number of ideas of variants of the Multi-Index Monte Carlo (MIMC) method.

28. W. Fang, M.B. Giles. 'Adaptive Euler-Maruyama method for SDEs with non-globally Lipschitz drift'. Monte Carlo and Quasi-Monte Carlo Methods 2016, Springer, 2018. link

This paper summarises the theoretical results in our earlier papers.

29. M.B. Giles, F. Bernal. 'Multilevel estimation of expected exit times and other functionals of stopped diffusions'. SIAM/ASA Journal on Uncertainty Quantification, 6(4):1454-1474, 2018. link

This paper considers SDEs in a bounded space-time domain, and associated path functionals with expected values which are equivalent to parabolic PDE solutions through the Feynman-Kac theory.

30. M. Croci, M.B. Giles, M.E. Rognes, P.E. Farrell. 'Efficient white noise sampling and coupling for multilevel Monte Carlo with non-nested meshes'. SIAM/ASA Journal on Uncertainty Quantification, 6(4):1630-1655, 2018. link

This paper develops and analyses a technique for the efficient sampling of white noise realizations in order to generate Gaussian fields with a Matern covariance structure. This includes coupled constructions for coarse and fine grids for use within a multilevel Monte Carlo simulation.

31. M.B. Giles. 'MLMC for nested expectations'. pp.425-442 in Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan, Springer, 2018. link

This paper discusses progress and future research possibilities in applying MLMC ideas to nested expectations.

32. M.B. Giles, M. Hefter, L. Mayer, K. Ritter. 'Random bit quadrature and approximation of distributions on Hilbert spaces'. Foundations of Computational Mathematics, 19(1):205-238, 2019. link

This is a theoretical paper which uses a computational cost model proportional to the number of random bits which are used.

33. M.B. Giles, T. Goda. 'Decision-making under uncertainty: using MLMC for efficient estimation of EVPPI'. Statistics and Computing, 29(4):739-751, 2019. link

This paper develops and analyses an MLMC approach to the estimation of Expected Value of Partial Perfect Information, which is relevant to applications such as the evaluating the cost-effectiveness of medical research.

34. M.B. Giles, K. Debrabant, A. Roessler. 'Numerical analysis of multilevel Monte Carlo path simulation using the Milstein discretisation'. Discrete and Continuous Dynamical Systems - series B, 24(8):3881-3903, 2019. link
35. This paper performs a numerical analysis of the multilevel Milstein method presented in paper #2, and also presents basket option results similar to those in paper #5.

36. W. Fang, M.B. Giles. 'Multilevel Monte Carlo method for ergodic SDEs without contractivity'. Journal of Mathematical Analysis and Applications, 476(1):149-176, 2019. link

This paper couples coarse and fine paths using a "spring" to improve the MLMC variance in cases in which the two paths would otherwise diverge exponentially.

37. M.B. Giles, M. Hefter, L. Mayer, K. Ritter. 'Random bit multilevel algorithms for stochastic differential equations'. Journal of Complexity, 54:101395, 2019. link

This is a second theoretical paper which uses a computational cost model proportional to the number of random bits which are used.

38. M.B. Giles, A.L. Haji-Ali. 'Multilevel nested simulation for efficient risk estimation'. SIAM/ASA Journal on Uncertainty Quantification, 7(2):497-525, 2019. link.

This paper develops and analyses an adaptive multilevel Monte Carlo algorithm for nested simulation problems arising the calculation of VaR (Value-at-Risk) and CVaR (Conditional Value-at-Risk, also known as Expected Shortfall).

39. M.B. Giles, M. Hefter, L. Mayer, K. Ritter. 'An Adaptive Random Bit Multilevel Algorithm for SDEs'. To appear in Multivariate Algorithms and Information-Based Complexity, De Gruyter, 2019. link

This is the third paper using a computational cost model proportional to the number of random bits which are used. In this case, the numerical algorithm uses a Brownian Bridge construction with more precision for the terms with the greatest span. The numerical results indicate a near-optimal order of complexity.

40. W. Fang, M.B. Giles. 'Adaptive Euler-Maruyama method for SDEs with non-globally Lipschitz drift'. Annals of Applied Probability, to appear 2019. link

This is the published version of papers 22a/b, proving that the use of adaptive timesteps cures the instability of the standard uniform timestep Euler-Maruyama method when applied to SDEs with a drift which is not globally Lipschitz.

41. M.B. Giles, M.B. Majka, L. Szpruch, S.J. Vollmer, K.C. Zygalakis. 'Multi-level Monte Carlo methods for the approximation of invariant measures of stochastic differential equations'. Statistics and Computing, online Sept 2019. link.

This paper also looks at the problem of approximating invariant measures of SDEs.

Current MLMC research, involving several collaborations, is addressing the following applications:

• stochastic PDEs
• use of approximate probability distributions

Acknowledgements

This research has been supported over the years by the following EPSRC research grants:
• EP/E031455/1: Development of Multilevel Monte Carlo Algorithms for Mathematical Finance
• EP/H05183X/1: Multilevel Monte Carlo Methods for Elliptic Problems with Applications to Radioactive Waste Disposal
• MA/3630057: Inference, COmputation and Numerics for Insights into Cities (ICONIC)