On polynomial-time property for a class of randomized quadratures (Q1888372)

A class of randomized methods for the evaluation of multivariate integrals over the unit cube \([0,1]^s\) is considered. In distinction to the classical Monte Carlo method, the proposed methods use a special importance sampling, which allows to achieve remarkably smaller errors. Besides, for periodic functions these methods require less restrictive assumptions to enjoy polynomial-time and/or strong polynomial-time properties. The polynomial-time property means, roughly, that the errors are bounded from above by a polynomial in \(s\) and in \(1/n\), whereas for the strong polynomial-time property this bound is polynomial in \(1/n\) and independent of \(s\). Integrals of the form \[ I_s(f) = \int\limits_{[0,1]^s} f({\mathbf x}) d {\mathbf x} \] are considered, where \(f\) is a function of \(s\) variables, which belongs to reproducing kernel Hilbert space. Two types of kernels of a multiplicative form \({\mathcal K}_s({\mathbf x},{\mathbf y}) = \prod_{k=1}^s K_{{\gamma}_k,s}(x_k,y_k)\) are considered with \(K_{\gamma}(x,y)=1+ \gamma \, \min (x,y)\) and \(K_{\gamma}(x,y)=1+ \gamma \, ( \min (x,y) -xy)\). In the classical Monte Carlo method, the integral is approximated by a sum \(\frac{1}{n} \sum_{i=1}^n f \left( {\mathbf x}^i \right)\) with the sampling points \({\mathbf x}^i\) independently and randomly generated according to the uniform distribution on \([0,1]^s\). The actually proposed methods use the weighted sum \( \frac{1}{n} \sum_{i=1}^n f \left( {\mathbf x}^i \right) / \rho_s^{[\alpha]} \left( {\mathbf x}^i \right) \) instead with the sampling points \({\mathbf x}^i\) distributed independently, each with the probability corresponding to the probability distribution function \( \rho_s^{[\alpha]}({\mathbf x}) = { ({\mathcal K}_s({\mathbf x},{\mathbf y})) ^{\alpha}} / { \int_{[0,1]^s} ({\mathcal K}_s({\mathbf t},{\mathbf t}))^{\alpha} d {\mathbf t} } \;. \) The main result of the paper is the proof of certain error bounds for this approximation with the two kernels considered.