Optimal importance sampling for the approximation of integrals (Q964918)

The Monte Carlo method is a very appropriate tool for numerical approximation of multidimensional integrals. In the present paper, \(d\) denotes the dimension and the weight \(\rho\) is a probability density function on the Borel measurable set \(D \subseteq {\mathbb R}^{d}.\) The integration problem \(I(f) = \int_{D}f(x)\rho(x) \,dx,\) where the function \(f:D \to {\mathbb R}\) belongs to some reproducing kernel Hilbert space, is considered. The above problem is rewritten in the terms of another probability density function \(\omega\) on \(D.\) Using \(n\) random sample points \(x_{1}, x_{2}, \ldots , x_{n},\) according to the new probability density function \(\omega,\) the Monte Carlo algorithm \(Q_{n}(f)= {1 \over n}\sum_{i=1}^{n} {f(x_{i}) \rho(x_{i}) \over \omega(x_{i})}\) for numerical approximation of \(I(f)\) is proposed. The notions of an initial error and a worst case error of the randomized algorithm \(Q_{n}(f)\) are defined. In Section 2, the problem for a change of the density function is developed. The Pietsch domination theorem is recalled. In Section 3, the importance sampling from change of the density function is considered. Theorem 3 states the existence of a density function \(\omega > 0\) such that the worst case error of importance sampling with density function \(\omega\) has an order \({\mathcal O}(n^{-{1 \over 2}}).\) Theorem 4 considers the case when the reproducing kernel is nonnegative. This theorem confirms the existence of a density function \(\omega\) such that the worst case error of importance sampling with density function \(\omega\) has an order \({\mathcal O}(n^{-{1 \over 2}}).\) In Section 4, as a consequence of Theorems 3 and 4, the polynomial tractability of the multivariate integration problem is obtained. This is the contents of Theorem 5. In Section 5, two concrete examples of reproducing kernel Hilbert spaces are considered. The details, connected with the form of the reproducing kernels and the errors, are developed. The construction of the corresponding density functions \(\omega\) is presented. The cases of integration of non-periodic and periodic functions are discussed.