## Abstract

We study a class of randomized methods that use a special importance sampling for approximating multivariate integrals over the unit cube [0,1]^{s}. These methods have errors in the randomized setting significantly smaller that the errors of the classical Monte Carlo method for the spaces of functions considered in this paper. In particular, for periodic functions, to enjoy the polynomial-time and/or strongly polynomial-time properties, these methods require less restrictive assumptions on the spaces than the assumptions required by the classical Monte Carlo methods. Recall that polynomial-time property means, roughly, that the errors are bounded from above by a polynomial in s and in 1/n. Here n is the number of function values used. The strong polynomial-time property means that the error is bounded by a polynomial in 1/n independently of s.

Original language | English |
---|---|

Pages (from-to) | 624-637 |

Number of pages | 14 |

Journal | Journal of Complexity |

Volume | 20 |

Issue number | 5 |

DOIs | |

State | Published - Oct 2004 |

### Bibliographical note

Funding Information:$The author was partially supported by the National Science Foundation under Grant CCR-0095709. E-mail address: greg@cs.uky.edu.

## Keywords

- Importance sampling
- Monte Carlo methods
- Multivariate integration
- Randomized methods
- Tractability

## ASJC Scopus subject areas

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- Mathematics (all)
- Control and Optimization
- Applied Mathematics