Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\) (Q983180)

Monte Carlo algorithms are successful tool for a numerical approximation of integrals of functions from different functional classes. In the present paper randomized algorithms for numerical integration with respect to a product probability measure on the sequence space \({\mathbb R}^{\mathbb N}\) are studied. Integrands from reproducing kernel Hilbert spaces, whose kernels are superposition of weighted tensor product, are considered. In the introduction the classes of integrands are briefly discussed. The basic idea to consider the infinite-dimensional integration as a limiting case of high-dimensional integration is developed. The use of sequences of coordinate weights , which give the dependence of the functions from their arguments, is applied and connected with the idea of the tractability of the numerical integration. The reproducing kernels of the infinite-dimensional spaces are studied as the limiting case of high-dimensional reproducing kernels. In Section 2 the basic assumptions on the probability measure, the kernels, the weights and the corresponding reproducing kernel Hilbert spaces are given. The ideas for the functions of infinitely many variables and the integration with respect to the product measure are developed. Two examples, where the measure \(\rho\) being the uniform distribution on \([0,1],\) are provided. The first example is the functional space \(W_{2}^{1}([0,1])\) of absolutely continuous functions with square-integrable derivatives, and for the second example the form of the reproducing kernel, which generate the functional space is given. Many lemmas are proved. In Section 3 a cost model for the analysis of infinite-dimensional quadrature problems is presented. Two particular models- for fixed subset sampling and for variable subspace sampling are developed. The randomized algorithms are used for approximation of integrals of integrands of infinitely many arguments. The notions of the worst-case cost of the algorithms for fixed and variable subspace models are defined. In Section 4 lower and upper bounds of the worst-case cost of algorithms for fixed subspace sampling are obtained. In Theorem 1, under the given assumptions, estimations for the worst-case error and the worst-case cost of the randomized algorithms \(Q_{n_{N}, S_{n},a}\) are presented. In Theorem 2 a lower bound of the minimal errors for the integration on the unit ball \(B(K)\) using a fixed subspace is obtained. Results of Theorems 1 and 2 are applied in the case, when the measure \(\rho\) is the uniform distribution on \([0,1],\) and to both cases of reproducing kernel Hilbert spaces. The obtained estimations for the worst-case error and the worst-case cost are presented in Corollaries 1, 2 and 3. In section 5 upper bound for multi-level algorithms for variable subspace sampling are presented. An analysis of variable subspace sampling and a motivation by the multi-level approach to infinite-dimensional integration are developed. In Theorem 4 upper bounds of the variation and the expectation of the worst-case cost of randomized algorithms are obtained. In Theorem 5, under given assumptions, upper bounds of the worst-case error and the worst-case cost for the multi-level algorithm \(Q_{N}\) are obtained. Again, the main results of this section are applied, concrete in the case when the measure \(\rho\) is the uniform distribution on \([0,1],\) to both kinds of functional spaces. The paper finishes with an appendix, where auxiliary results are presented.