Elsevier

Journal of Complexity

Volume 15, Issue 3, September 1999, Pages 317-341
Journal of Complexity

Regular Article
Monte Carlo Complexity of Parametric Integration

https://doi.org/10.1006/jcom.1999.0508Get rights and content
Under an Elsevier user license
open archive

Abstract

The Monte Carlo complexity of computing integrals depending on a parameter is analyzed for smooth integrands. An optimal algorithm is developed on the basis of a multigrid variance reduction technique. The complexity analysis implies that our algorithm attains a higher convergence rate than any deterministic algorithm. Moreover, because of savings due to computation on multiple grids, this rate is also higher than that of previously developed Monte Carlo algorithms for parametric integration.

Cited by (0)