Multilevel Monte Carlo Method [Draft]

Part of a series: Monte Carlo Method.

Follow reading here

The multilevel Monte Carlo (MLMC) method is a variance reduction technique used for the efficient estimation of the quantity of interest (QoIs) namely, mean, variance, and quantiles of the output distribution in the field of uncertainty quantification (UQ). The basic idea behind MLMC is to use a hierarchy of approximation to the true QoIs, with increasing cost and accuracy. The lower levels or approximations are the cheaper to compute and are less accurate. Whereas, the accuracy and computational cost increases with the higher levels/approximation, see, for example, the figure below.

The MLMC algorithm begins with a small number of simulations at the lowest levels of approximation, i.e., with low accuraccy. These simulations are then used as to obtain initial estimate for the QoIs. The algorithm then refines this estimate by performing simuations at higher levels, i.e., with high accuracy. The variance reduction comes from the fact that the variance reduces at each level with increasing levels of accuracy. Let’s define \(E[u]\) as the true mean and the estimated mean with high accuracy as \(E[u_L]\) then

\[ E[u] \approx E[u_L] = E[u_0] + \sum_{l=1}^{L} E [u_l - u_{l-1}] \approx E_{N_0}[u_0] + \sum_{l=1}^{L} E_{N_l} \left ( u_l - u_{l-1}\right), \]

where \(l \in 0,1,\cdots,L\) and \(u_l\) are the corresponding approximations at each level.

The MLMC method wins over the traditional Monte Carlo method in terms of computational cost by providing accurate estimates of the QoIs at a lower cost as it uses fewer expensive simulations. This is advantageous in the problems where the cost of each sample is high, such as in complex physical or biological simulations.

However, it can challenging to implement, as it requires careful design of the hierarchy of approximations and the statistical extrapolation methods used to combine them. Nevertheless, MLMC has been successfully used in the field of finance, physics, and other areas of science and engineering. For further reading please see [Cliffe et al., 2011] and [Giles, 2008].

References

CGST11

K Andrew Cliffe, Mike B Giles, Robert Scheichl, and Aretha L Teckentrup. Multilevel monte carlo methods and applications to elliptic pdes with random coefficients. Computing and Visualization in Science, 14:3–15, 2011.

Gil08

Michael B Giles. Multilevel monte carlo path simulation. Operations research, 56(3):607–617, 2008.

Authors

• Maqsood Mubarak Rajput