mlmc (version 1.0.0)

mlmc: Multi-level Monte Carlo estimation

Description

This function is the Multi-level Monte Carlo driver which will sample from the levels of user specified function.

Usage

mlmc(Lmin, Lmax, N0, eps, mlmc_l, alpha = NA, beta = NA, gamma,
  parallel = NA, ...)

Arguments

Lmin

the minimum level of refinement. Must be $\ge 2$.

Lmax

the maximum level of refinement. Must be $\ge$ Lmin.

N0

initial number of samples which are used for the first 3 levels and for any subsequent levels which are automatically added. Must be $> 0$.

eps

the target accuracy of the estimate. Must be $> 0$.

mlmc_l

a user supplied function which provides the estimate for level l

alpha

the weak error, $O(2^{-alpha*l})$. If NA then alpha will be estimated.

beta

the variance, $O(2^{-beta*l})$. If NA then beta will be estimated.

gamma

the sample cost, $O(2^{gamma*l})$. Must be $> 0$.

parallel

if an integer is supplied, R will fork parallel parallel processes an compute each level estimate in parallel.

...

additional arguments which are passed on when the user supplied mlmc_l function is called

Value

• A list containing: [object Object],[object Object]

Details

Multilevel Monte Carlo Method method originated in works Giles (2008) and Heinrich (1998).

Consider a sequence $P_0, P_1, \ldots,$ which approximates $P_L$ with increasing accuracy, but also increasing cost, we have the simple identity $$E[P_L] = E[P_0] + \sum_{l=1}^L E[P_l-P_{l-1}],$$ and therefore we can use the following unbiased estimator for $E[P_L]$, $$N_0^{-1} \sum_{n=1}^{N_0} P_0^{(0,n)} + \sum_{l=1}^L { N_l^{-1} \sum_{n=1}^{N_l} (P_l^{(l,n)} - P_{l-1}^{(l,n)}) }$$ with the inclusion of the level $l$ in the superscript $(l,n)$ indicating that the samples used at each level of correction are independent.

Set $C_0$, and $V_0$ to be the cost and variance of one sample of $P_0$, and $C_l, V_l$ to be the cost and variance of one sample of $P_l - P_{l-1}$, then the overall cost and variance of the multilevel estimator is $\sum_{l=0}^L N_l C_l}$ and $\sum_{l=0}^L N_l^{-1} V_l$, respectively.

The idea begind the method, is that provided that the product $V_l C_l$ decreases with $l$, i.e. the cost increases with level slower than the variance decreases, then one can achieve significant computational savings, which can be formalised as in Theorem 1 of Giles (2015).

For further information on multilevel Monte Carlo methods, see the webpage http://people.maths.ox.ac.uk/gilesm/mlmc_community.html which lists the research groups working in the area, and their main publications.

This function is based on GPL-2 'Matlab' code by Mike Giles.

References

M.B. Giles. Multilevel Monte Carlo path simulation. Operations Research, 56(3):607-617, 2008.

M.B. Giles. Multilevel Monte Carlo methods. Acta Numerica, 24:259-328, 2015.

S. Heinrich. Monte Carlo complexity of global solution of integral equations. Journal of Complexity, 14(2):151-175, 1998.

Examples

mlmc(2, 6, 1000, 0.01, opre_l, gamma=1, option=1)

mlmc(2, 10, 1000, 0.01, mcqmc06_l, gamma=1, option=1)