Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension


Authors: Fred J. Hickernell and Xiaoqun Wang
Journal: Math. Comp. 71 (2002), 1641-1661
MSC (2000): Primary 65C05, 65D30
Published electronically: August 2, 2001
MathSciNet review: 1933048
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation.

Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor $\varepsilon$ is bounded by $C \varepsilon ^{-p}$ for some exponent $p$ and some positive constant $C$. The $\varepsilon$-exponent of tractability is defined as the smallest power of $\varepsilon^{-1}$ in these bounds. It is shown by using Monte Carlo quadrature that the $\varepsilon$-exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the $\varepsilon$-exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65C05, 65D30

Retrieve articles in all journals with MSC (2000): 65C05, 65D30


Additional Information

Fred J. Hickernell
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong SAR, China
Email: fred@hkbu.edu.hk

Xiaoqun Wang
Affiliation: Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China
Email: xwang@math.tsinghua.edu.cn

DOI: http://dx.doi.org/10.1090/S0025-5718-01-01377-1
PII: S 0025-5718(01)01377-1
Keywords: Quasi-Monte Carlo methods, Monte Carlo methods, tractability, infinite dimensional integration
Received by editor(s): May 24, 2000
Received by editor(s) in revised form: October 18, 2000
Published electronically: August 2, 2001
Additional Notes: This work was supported by a Hong Kong Research Grants Council grant RGC/97-98/47 and by the NSF of China Grants 79970120 and 10001021.
Article copyright: © Copyright 2001 American Mathematical Society