Multilevel Monte Carlo methods

Acta Numerica - Tập 24 - Trang 259-328 - 2015
Michael B. Giles1
1University of Oxford.

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

10.1287/mnsc.42.2.269

F. Vidal-Codina , N. Nguyen , M. Giles  and J. Peraire (2014), A model and variance reduction method for computing statistical outputs of stochastic elliptic partial differential equations. arXiv:1409.1526

Glasserman, 2004, Monte Carlo Methods in Financial Engineering

Iliev, 2013, Monte Carlo Methods and Applications: Proc. 8th IMACS Seminar on Monte Carlo Methods, 115

A. Teckentrup (2013), Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath.

M. Giles , K. Debrabant  and A. Rößler (2013), Numerical analysis of multilevel Monte Carlo path simulation using the Milstein discretisation. arXiv:1302.4676

10.1016/0021-9991(76)90041-3

10.1007/s00791-011-0160-x

10.1016/j.jco.2014.01.002

10.1137/S0036142901389530

10.1137/110840546

Gunzburger, 2014, Acta Numerica, 23, 521

10.1007/s10208-014-9237-5

10.1016/j.jco.2005.11.002

T. Primozic (2011), Estimating expected first passage times using multilevel Monte Carlo algorithm. MSc thesis, University of Oxford.

10.1007/s00780-013-0208-5

Asmussen, 2007, Stochastic Simulation

10.1287/mnsc.1040.0258

10.1137/120896001

10.1016/j.jcp.2012.01.011

10.1016/j.jco.2010.08.001

Q. Li (2007), Numerical approximation for SDE. PhD thesis, University of Edinburgh.

10.1137/130940761

10.1063/1.4904980

10.1007/s10543-012-0401-5

10.1115/1.1446068

10.1137/S0036142902418680

10.1007/s00211-013-0546-4

10.1016/j.jat.2014.04.014

A. Moraes , R. Tempone  and P. Vilanova (2014), A multilevel adaptive reaction-splitting simulation method for stochastic reaction networks. arXiv:1406.1989

10.1137/100786356

10.1007/978-3-642-27440-4_13

10.1214/105051605000000511

10.1007/978-1-4612-1318-5_4

10.1007/s10208-014-9198-8

Bujok, 2013, Multilevel simulation of functionals of Bernoulli random variables with application to basket credit derivatives, Methodol. Comput. Appl. Probab.

Y. Xia (2014), Multilevel Monte Carlo for jump processes. DPhil thesis, University of Oxford.

10.1016/j.spa.2011.03.015

N. Chen  and Y. Liu (2012), Estimating expectations of functionals of conditional expected via multilevel nested simulation. Presentation at conference on Monte Carlo and Quasi-Monte Carlo Methods, Sydney.

10.1007/s00780-009-0099-7

Giles, 2009, Advanced Financial Modelling, 165, 10.1515/9783110213140.165

10.21314/JCF.2009.201

10.1007/978-3-642-27440-4_41

10.1007/s10596-013-9358-y

10.1016/j.jco.2014.04.002

10.1214/10-AAP695

10.1006/jcom.1999.0508

Giles, 2013, Monte Carlo and Quasi-Monte Carlo Methods 2012, 79

A.-L. Haji-Ali (2012), Pedestrian flow in the mean-field limit. MSc thesis, KAUST.

10.1137/120883803

10.1137/110853054

10.1007/978-3-642-21943-6_10

10.1287/mnsc.36.11.1364

Y. Xia  and M. Giles (2014), Multilevel Monte Carlo for exponential Lévy models. arXiv:1403.5309

Collier, 2014, A continuation multilevel Monte Carlo algorithm, BIT Numer. Math.

10.1287/opre.1070.0496

10.1002/0470870230

M. Giles (2014), MATLAB code for multilevel Monte Carlo computations. http://people.maths.ox.ac.uk/gilesm/acta/

S. Graubner (2008), Multi-level Monte Carlo Methoden für stochastische partielle Differentialgleichungen. Diplomarbeit, TU Darmstadt.

V. Lemaire  and G. Pagès (2013), Multilevel Richardson–Romberg extrapolation. arXiv:1401.1177

10.1287/opre.2015.1404

10.1016/j.spa.2008.01.006

10.1007/s10208-008-9029-x

10.1137/S1064827592240555

10.1016/j.spa.2009.09.014

10.1137/S1064827501387826

Rhee, 2012, Proc. 2012 Winter Simulation Conference

Giles, 2015a, Monte Carlo and Quasi-Monte Carlo Methods 2014

10.1016/j.jcp.2014.05.030

A.-L. Haji-Ali , F. Nobile  and R. Tempone (2014a), Multi Index Monte Carlo: When sparsity meets sampling. arXiv:1405.3757

10.21314/JCF.2012.249

10.1214/12-AAP890

10.1007/978-3-642-41095-6_16

10.1007/978-3-642-20212-4

10.1137/070709359

10.1007/978-3-662-12616-5

10.1007/s00211-011-0377-0

Bungartz, 2004, Acta Numerica, 13, 147

Giles, 2009, Proc. 2009 Winter Simulation Conference, 1283, 10.1109/WSC.2009.5429692

S. Burgos (2014), The computation of Greeks with multilevel Monte Carlo. DPhil thesis, University of Oxford.

10.1098/rspa.2011.0505

10.1090/S0025-5718-08-02009-7

10.1137/110841916

A.-L. Haji-Ali , F. Nobile , E. von Schwerin  and R. Tempone (2014b), Optimization of mesh hierarchies in multilevel Monte Carlo samplers. arXiv:1403.2480

Heinrich, 2001, Multigrid Methods, 58

10.1515/mcma.2010.007

10.1098/rspa.2003.1237

10.1007/978-3-540-74496-2_20

10.1007/978-1-4899-3324-9

10.1016/j.jcp.2013.03.023

10.1016/j.spa.2013.09.015

10.1007/978-3-642-41095-6_12

10.1006/jcom.1998.0471

10.1515/mcma-2013-0014

M. Giles , T. Nagapetyan  and K. Ritter (2015b), ‘Multilevel Monte Carlo approximation of distribution functions and densities’, SIAM/ASA J. Uncertainty Quantification, to appear.

10.1007/BFb0004537

Merton, 1976, Option pricing when underlying stock returns are discontinuous, J. Finance, 3, 125

10.1239/jap/1417528487

Dick, 2013, Acta Numerica, 22, 133

10.1007/BF02186816

Brugger, 2014, Proc. Conference on Computational Intelligence for Financial Engineering and Economics

10.1007/s00780-009-0092-1

10.1016/S0167-7322(03)00061-8

10.1002/mana.19881380107

10.1214/13-AAP957

10.1007/978-3-642-13694-8

A. Moraes , R. Tempone  and P. Vilanova (2015), ‘Multilevel hybrid Chernoff tau-leap’, BIT Numer. Math., to appear.

10.1007/BFb0004007