mlmc: Multi-level Monte Carlo estimation

Description Usage Arguments Details Value Author(s) References Examples

Description

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

Usage

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

Arguments

Lmin

the minimum level of refinement. Must be ≥ 2.

Lmax

the maximum level of refinement. Must be 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

Details

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

Consider a sequence P_0, P_1, …, which approximates P_L with increasing accuracy, but also increasing cost, we have the simple identity

E[P_L] = E[P_0] + ∑_{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} ∑_{n=1}^{N_0} P_0^{(0,n)} + ∑_{l=1}^L \{ N_l^{-1} ∑_{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 ∑_{l=0}^L N_l C_l\} and ∑_{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.

Value

A list containing:

P

The MLMC estimate;

Nl

A vector of the number of samples performed on each level.

Author(s)

Louis Aslett <aslett@stats.ox.ac.uk>

Mike Giles <Mike.Giles@maths.ox.ac.uk>

Tigran Nagapetyan <nagapetyan@stats.ox.ac.uk>

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

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

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

mlmc documentation built on May 1, 2019, 9:45 p.m.

Related to mlmc in mlmc...