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, 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.

  27. 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.

  28. 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.

  29. 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.

  30. 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.

  31. 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.

  32. 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.

  33. 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
  34. 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.

  35. 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.

  36. 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.

  37. 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).

  38. M.B. Giles, A.L. Haji-Ali. 'Sub-sampling and other considerations for efficient risk estimation in large portfolios'. arXiv pre-print, 2019, link.

    This paper follows on from the previous paper by tackling the computational cost of very large portfolios by sub-sampling within them. It also looks at the use of various control variates which reduce the MLMC variance.

  39. 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, 30(3):507-524, 2020. link.

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

  40. M.B. Giles, M. Hefter, L. Mayer, K. Ritter. 'An Adaptive Random Bit Multilevel Algorithm for SDEs', in Multivariate Algorithms and Information-Based Complexity, De Gruyter, 2020. 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.

  41. W. Fang, M.B. Giles. 'Adaptive Euler-Maruyama method for SDEs with non-globally Lipschitz drift'. Annals of Applied Probability, 30(2):526-560, 2020. 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.

  42. T. Hironaka, M.B. Giles, T. Goda, H. Thom. 'Multilevel Monte Carlo estimation of the expected value of sample information'. SIAM/ASA Journal on Uncertainty Quantification, 8(3):1236-1259, 2020. link,

    This paper extends the previous work on the estimation of Expected Value of Partial Perfect Information, relevant to applications such as the evaluating the cost-effectiveness of medical research.

  43. W. Fang, Z. Wang, M.B. Giles, C.H. Jackson, N.J. Welton, C. Andrieu, H. Thom. 'Multilevel and quasi Monte Carlo methods for the calculation of the expected value of partial perfect information'. Medical Decision Making, July 2021. link.

    This paper continues the research on the estimation of EVPPI, looking at the use of Quasi-Monte Carlo methods as well as MLMC.

  44. M. Croci, M.B. Giles, P.E. Farrell. 'Multilevel quasi Monte Carlo methods for elliptic PDEs with random field coefficients via fast white noise sampling'. SIAM Journal on Scientific Computing, 43(4), A2840-A2868, 2021. link.

    This paper develops a wavelet representation of white noise to provide a consistent Multilevel Monte Carlo coupling for improved variance reduction.

  45. W. Fang, M.B. Giles. 'Importance Sampling for Pathwise Sensitivity of Stochastic Chaotic Systems'. SIAM/ASA Journal on Uncertainty Quantification, 9(3):1217-1241, 2021. link.

    Chaotic SDEs pose a challenge to sensitivity analysis because sensitivities grow exponentially. In this paper we avoid this problem by building on prior research in which we introduced a novel coupling between coarse and fine paths in a multilevel Monte Carlo formulation.

  46. M.B. Giles, O. Sheridan-Methven. 'Analysis of nested multilevel Monte Carlo using approximate Normal random variables'. SIAM/ASA Journal on Uncertainty Quantification, 10(1):200-226, 2022. link.

    In this paper we combine a standard MLMC treatment of SDEs with the use of approximate Normal random variables which can be generated extremely cheaply. The paper includes an analysis of the mixed 4-way difference with different timesteps and true or approximate Normal random variables. Even bigger computational savings may be achieved in other settings where it is extremely costly to invert a CDF to generate random variables from uniform random variables.

  47. A.L. Haji-Ali, M.B. Giles. 'Sub-sampling and other considerations for efficient risk estimation in large portfolios'. Journal of Computational Finance, 26(1), June 2022. link.

    This paper extends our previous work on financial risk estimation by developing a MLMC method with a cost which is insensitive to the number of products in a financial portfolio.

  48. M.B. Giles, O. Sheridan-Methven. 'Approximating inverse cumulative distribution functions to produce approximate random variables'. ACM Transactions on Mathematical Software, 49(3):1-29, 2023. link.

    This paper is a follow-on to #45 with a concentration on different approaches to approximating the inverse cumulative Normal distribution, and their suitability and implementation on different hardware. It also has numerical experiments using an approximation to the inverse of the non-central chi-squared distribution for simulating the CIR SDE.

  49. M.B. Giles, A.-L. Haji-Ali. 'Multilevel path branching for digital options'. arXiv pre-print, 2022. link.

    This article develops a new approach for improving the multilevel variance for discontinuous functionals of the terminal state of an SDE solution. Inspired by talks on branching diffusions, a deterministic repeated branching is used to greatly reduce the variance at the expense of a very modest increase in sample cost.

  50. M.B. Giles, A.-L. Haji-Ali, J. Spence. 'Efficient risk estimation for the Credit Valuation Adjustment'. arXiv pre-print, 2023. link.

    This article, in which I was a very minor contributor, expands on #36 and #37 by considering triply-nested expectations!

  51. M.B. Giles. 'MLMC techniques for discontinuous functions'. Monte Carlo and Quasi-Monte Carlo Methods 2022, Springer, to appear, 2024. link.

    This review article, following a plenary presentation at MCQMC2020, discusses the many methods in the literature to improve the MLMC variance convergence which is usually poor when the output functional has a discontinuity.



  52. Acknowledgements

    This research has been supported over the years by the following EPSRC research grants: