Multilevel Monte Carlo method

Multilevel Monte Carlo (MLMC) methods in numerical analysis are algorithms for computing expectations that arise in stochastic simulations. Just as Monte Carlo methods, they rely on repeated random sampling, but these samples are taken on different levels of accuracy. MLMC methods can greatly reduce the computational cost of standard Monte Carlo methods by taking most samples with a low accuracy and corresponding low cost, and only very few samples are taken at high accuracy and corresponding high cost.

Goal

The goal of a multilevel Monte Carlo method is to approximate the expected value ${\displaystyle \operatorname {E} [G]}$ of the random variable ${\displaystyle G}$ that is the output of a stochastic simulation. Suppose this random variable cannot be simulated exactly, but there is a sequence of approximations ${\displaystyle G_{0},G_{1},\ldots ,G_{L}}$ with increasing accuracy, but also increasing cost, that converges to ${\displaystyle G}$ as ${\displaystyle L\rightarrow \infty }$. The basis of the multilevel method is the telescoping sum identity, ^[1]

${\displaystyle \operatorname {E} [G_{L}]=\operatorname {E} [G_{0}]+\sum _{\ell =1}^{L}\operatorname {E} [G_{\ell }-G_{\ell -1}],}$

that is trivially satisfied because of the linearity of the expectation operator. Each of the expectations ${\displaystyle \operatorname {E} [G_{\ell }-G_{\ell -1}]}$ is then approximated by a Monte Carlo method, resulting in the multilevel Monte Carlo method. Note that taking a sample of the difference ${\displaystyle G_{\ell }-G_{\ell -1}}$ at level${\displaystyle \ell }$ requires a simulation of both ${\displaystyle G_{\ell }}$ and ${\displaystyle G_{\ell -1}}$.

The MLMC method works if the variances ${\displaystyle \operatorname {V} [G_{\ell }-G_{\ell -1}]\rightarrow 0}$ as ${\displaystyle \ell \rightarrow \infty }$, which will be the case if both ${\displaystyle G_{\ell }}$ and ${\displaystyle G_{\ell -1}}$ approximate the same random variable ${\displaystyle G}$. By the Central Limit Theorem, this implies that one needs fewer and fewer samples to accurately approximate the expectation of the difference ${\displaystyle G_{\ell }-G_{\ell -1}}$ as ${\displaystyle \ell \rightarrow \infty }$. Hence, most samples will be taken on level ${\displaystyle 0}$, where samples are cheap, and only very few samples will be required at the finest level ${\displaystyle L}$. In this sense, MLMC can be considered as a recursive control variate strategy.

Applications

Approximation of a sample path of an SDE on different levels.

The first application of MLMC is attributed to Mike Giles, ^[2] in the context of stochastic differential equations (SDEs) for option pricing, however, earlier traces are found in the work of Heinrich in the context of parametric integration. ^[3] Here, the random variable ${\displaystyle G=f(X(T))}$ is known as the payoff function, and the sequence of approximations ${\displaystyle G_{\ell }}$, ${\displaystyle \ell =0,\ldots ,L}$ use an approximation to the sample path ${\displaystyle X(t)}$ with time step ${\displaystyle h_{\ell }=2^{-\ell }T}$.

The application of MLMC to problems in uncertainty quantification (UQ) is an active area of research. ^{[4] [5]} An important prototypical example of these problems are partial differential equations (PDEs) with random coefficients. In this context, the random variable ${\displaystyle G}$ is known as the quantity of interest, and the sequence of approximations corresponds to a discretization of the PDE with different mesh sizes.

An algorithm for MLMC simulation

A simple level-adaptive algorithm for MLMC simulation is given below in pseudo-code.

${\displaystyle L\gets 0}$repeat     Take warm-up samples at level ${\displaystyle L}$     Compute the sample variance on all levels ${\displaystyle \ell =0,\ldots ,L}$     Define the optimal number of samples ${\displaystyle N_{\ell }}$ on all levels ${\displaystyle \ell =0,\ldots ,L}$     Take additional samples on each level ${\displaystyle \ell }$ according to ${\displaystyle N_{\ell }}$if${\displaystyle L\geq 2}$then         Test for convergence     endif not converged then${\displaystyle L\gets L+1}$enduntil converged

Extensions of MLMC

Recent extensions of the multilevel Monte Carlo method include multi-index Monte Carlo, ^[6] where more than one direction of refinement is considered, and the combination of MLMC with the Quasi-Monte Carlo method. ^{[7] [8]}

See also

• Monte Carlo method
• Monte Carlo methods in finance
• Quasi-Monte Carlo methods in finance
• Uncertainty quantification
• Partial differential equations with random coefficients

References

1. Giles, M. B. (2015). "Multilevel Monte Carlo Methods". Acta Numerica. 24: 259–328. arXiv: 1304.5472 . doi:10.1017/s096249291500001x.
2. Giles, M. B. (2008). "Multilevel Monte Carlo Path Simulation". Operations Research. 56 (3): 607–617. CiteSeerX   10.1.1.121.713 . doi:10.1287/opre.1070.0496.
3. Heinrich, S. (2001). "Multilevel Monte Carlo Methods". Lecture Notes in Computer Science (Multigrid Methods). Lecture Notes in Computer Science. Springer. 2179: 58–67. doi:10.1007/3-540-45346-6_5. ISBN   978-3-540-43043-8.
4. Cliffe, A.; Giles, M. B.; Scheichl, R.; Teckentrup, A. (2011). "Multilevel Monte Carlo Methods and Applications to Elliptic PDEs with Random Coefficients" (PDF). Computing and Visualization in Science. 14 (1): 3–15. doi:10.1007/s00791-011-0160-x.
5. Pisaroni, M.; Nobile, F. B.; Leyland, P. (2017). "A Continuation Multi Level Monte Carlo Method for Uncertainty Quantification in Compressible Inviscid Aerodynamics" (PDF). Computer Methods in Applied Mechanics and Engineering. 326 (C): 20–50. doi:10.1016/j.cma.2017.07.030. Archived from the original (PDF) on 2018-02-14.
6. Haji-Ali, A. L.; Nobile, F.; Tempone, R. (2016). "Multi-Index Monte Carlo: When Sparsity Meets Sampling". Numerische Mathematik. 132 (4): 767–806. arXiv: 1405.3757 . doi:10.1007/s00211-015-0734-5.
7. Giles, M. B.; Waterhouse, B. (2009). "Multilevel Quasi-Monte Carlo Path Simulation" (PDF). Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics. De Gruyter: 165–181.
8. Robbe, P.; Nuyens, D.; Vandewalle, S. (2017). "A Multi-Index Quasi-Monte Carlo Algorithm for Lognormal Diffusion Problems". SIAM Journal on Scientific Computing. 39 (5): A1811–C392. arXiv: 1608.03157 . doi:10.1137/16M1082561.