When Does Monte Carlo Depend Polynomially on the Number of Variables?

Ian H. Sloan () and Henryk Woźniakowski ()
Additional contact information
Ian H. Sloan: University of New South Wales, School of Mathematics
Henryk Woźniakowski: Columbia University, Department of Computer Science

A chapter in Monte Carlo and Quasi-Monte Carlo Methods 2002, 2004, pp 407-437 from Springer

Abstract: Summary We study the classical Monte Carlo algorithm for weighted multivariate integration. It is well known that if Monte Carlo uses n randomized sample points for a function of d variables then it has error (vard(f)/n)1/2, where vard(f) is the variance of f. Hence, the speed of convergence n-1-2 is independent of d. However, the error may depend on d through the variance and may even be exponentially large in d. We compare the Monte Carlo error with the initial error that can be achieved without sampling the function. The initial error is the norm of the integration functional I d. We say that Monte Carlo is strongly polynomial or polynomial if the ratio vard(f)/I d 2 is uniformly bounded in d or depends polynomially on d for all functions from the unit ball of a given space. We restrict our analysis to reproducing kernel Hilbert spaces, and check for which spaces Monte Carlo is strongly polynomial or polynomial. We illustrate our results for a number of weighted tensor product Sobolev spaces over bounded and unbounded regions and for both non-periodic and periodic cases. We obtain necessary and sufficient conditions for Monte Carlo being polynomial in terms of the weights of the spaces. The conditions for Monte Carlo to be (strongly) polynomial are more lenient for periodic Sobolev spaces than for non-periodic Sobolev spaces; in either case, these conditions are more lenient than those for deterministic algorithms. For general reproducing kernel Hilbert spaces, the opposite may also happen: there are spaces for which Monte Carlo is strongly polynomial in the non-periodic case, and not polynomial in the periodic case. It may also happen that for some spaces Monte Carlo is not polynomial but multivariate integration is trivial for deterministic algorithms, i.e., multivariate integration can be computed exactly using only one function value.

Keywords: Tensor Product; Sobolev Space; Large Eigenvalue; Initial Error; Reproduce Kernel Hilbert Space (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-18743-8_26

Ordering information: This item can be ordered from
http://www.springer.com/9783642187438

DOI: 10.1007/978-3-642-18743-8_26

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().