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

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.