On the effective dimension and multilevel Monte Carlo

Abstract

I consider the problem of integrating a function $f$ over the $d$-dimensional unit cube. I describe a multilevel Monte Carlo method that estimates the integral with variance at most ${\epsilon }^2$ in $O(d+\ln (d)d_t{\epsilon }^{-2})$ time, for $\epsilon >0$, where $d_t$ is the truncation dimension of $f$. In contrast, the standard Monte Carlo method typically achieves such variance in $O(d{\epsilon }^{-2})$ time. A lower bound of order $d+d_t{\epsilon }^{-2}$ is described for a class of multilevel Monte Carlo methods.

References in corpus (4)

• Multilevel Monte Carlo estimation of expected information gains
• General multilevel Monte Carlo methods for pricing discretely monitored Asian options
• Randomized Dimension Reduction for Monte Carlo Simulations
• Efficient Steady-state Simulation of High-dimensional Stochastic Networks

Cited by in corpus (1)

• Unbiased time-average estimators for Markov chains