Optimal error bound of restricted Monte Carlo integration on anisotropic Sobolev classes

DOI10.1080/10020070612330039MaRDI QIDQ2455840zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 26 October 2007

Published in Progress in Natural Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10020070612330039

zbMATH Keywords

anisotropic Sobolev classesdiscretization techniquehigh-dimensional integralsrandom bitsrandomized \((n,m)\)-th minimal errorrestricted Monte Carlo integrationrestricted randomized algorithms

Mathematics Subject Classification ID

Well-distributed sequences and other variations (11K36) Pseudo-random numbers; Monte Carlo methods (11K45) Monte Carlo methods (65C05) Stochastic particle methods (65C35)

Review text

The calculation of high-dimensional integrals is applied in different fields of science. Recently, \textit{N. S. Bakhvalov} [On the rate of convergence of indeterministic integration processes within the functional classes \(W^\ell_p\). Theory Probab. Appl. 7, 227 (1962)], \textit{S. Heinrich, E. Novak}, and \textit{H. Pfeiffer} [Monte Carlo and quasi-Monte Carlo methods 2002. 27--49 (2004; Zbl 1041.65005)] have proved that using \({\mathcal O}(\log_2n)\) random bits one can achieve the same error bound of the integration problem for classical isotropic Sobolev class \(W_pr([0,1]^d)\) \((1\leq p\leq\infty)\). In the paper some notions as a solution operator mapping \(S\) on a functional space \(F\), generalized Monte Carlo method, a randomized \(n\)-th minimal error are considered. The class of restricted randomized algorithms with \(n\) function evaluations and \(m\) random bits is considered and the randomized \((n,m)\)-th minimal error on \(F\) \(e_{n,m}^{\text{coin}}(S,F)\) is reminded. The definition of the so-called anisotropic Sobolev class \(W_p^r(D)\) is given. Theorem 2 gives the exact order \(n^{-g(r)- {1 \over 2} + \max \{ {1 \over p}- {1 \over 2}, 0 \}}\) of the randomized \((n, \lfloor(2 + {1 \over g(r)})\log_{2}n\rfloor)\)-th minimal error of the integration on the anisotropic class \(W_p^r(D)\). The study is essentially based on the discretization technique developed for the study of classical Sobolev classes.

Recommendations

• Complexity of deterministic and randomized methods for multivariate integration problems for the class HpΛ(Id)
• Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms
• scientific article; zbMATH DE number 2051207
• Complexity of Sobolev imbeddings and integration in the deterministic and randomized settings
• Randomized approximation of Sobolev embeddings
• Computational complexity of the integration problem for anisotropic classes
• Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension
• Coin Tossing Algorithms for Integral Equations and Tractability
• Optimal confidence for Monte Carlo integration of smooth functions
• scientific article; zbMATH DE number 2186130

Cited in

(9)

• Random bit quadrature and approximation of distributions on Hilbert spaces
• Random bit multilevel algorithms for stochastic differential equations
• Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms
• scientific article; zbMATH DE number 2051207 (Why is no real title available?)
• On the Power of Restricted Monte Carlo Algorithms
• Randomized complexity of parametric integration and the role of adaption. II: Sobolev spaces
• Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms
• Integration error for multivariate functions from anisotropic classes
• Optimal restricted Monte Carlo integration on generalized Hölder classes

This page was built for publication: Optimal error bound of restricted Monte Carlo integration on anisotropic Sobolev classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2455840)