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, K. Debrabant, A. Roessler. 'Numerical analysis of multilevel Monte Carlo path simulation using the Milstein discretisation', ArXiv preprint, 2013. (PDF)

    This paper performs a numerical analysis of the multilevel Milstein method presented in paper #2.

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

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

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

  16. C. Lester, C. Yates, M.B. Giles, R.E. Baker. 'An adaptive multi-level simulation algorithm for stochastic biological systems'. Journal of Chemical Physics, 2015. (PDF)
  17. 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.

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

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

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

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

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

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

  24. M.B. Giles, Y. Xia. 'Multilevel Monte Carlo for exponential Lévy models'. Finance and Stochastics, 21: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, to appear, 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. 'Multilevel estimation of expected exit times and other functionals of stopped diffusions'. arXiv pre-print, 2017. (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.

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

  28. M.B. Giles, F.Y. Kuo, I.H. Sloan. 'Combining sparse grids, multilevel MC and QMC for elliptic PDEs with random coefficients'. To appear in 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.


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


Acknowledgements

This research has been supported by