The error bounds and tractability of quasiMonte Carlo algorithms in infinite dimension
Authors:
Fred J. Hickernell and Xiaoqun Wang
Journal:
Math. Comp. 71 (2002), 16411661
MSC (2000):
Primary 65C05, 65D30
Published electronically:
August 2, 2001
MathSciNet review:
1933048
Fulltext 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 quasiMonte 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 is bounded by for some exponent and some positive constant . The exponent of tractability is defined as the smallest power of in these bounds. It is shown by using Monte Carlo quadrature that the 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 exponent of tractability is 1, which implies that infinite dimensional integration is no harder than onedimensional integration.
 [Aro50]
N.
Aronszajn, Theory of reproducing
kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 0051437
(14,479c), http://dx.doi.org/10.1090/S00029947195000514377
 [CMO97]
R. E. Caflisch, W. Morokoff, and A. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance 1 (1997), 2746.
 [DR84]
Philip
J. Davis and Philip
Rabinowitz, Methods of numerical integration, 2nd ed.,
Computer Science and Applied Mathematics, Academic Press, Inc., Orlando,
FL, 1984. MR
760629 (86d:65004)
 [Duf96]
D. Duffie, Dynamic asset pricing theory, Princeton University Press, Princeton, New Jersey, 1996.
 [Fau82]
Henri
Faure, Discrépance de suites associées à un
système de numération (en dimension 𝑠), Acta
Arith. 41 (1982), no. 4, 337–351 (French). MR 677547
(84m:10050)
 [FW94]
K.T.
Fang and Y.
Wang, Numbertheoretic methods in statistics, Monographs on
Statistics and Applied Probability, vol. 51, Chapman & Hall,
London, 1994. MR
1284470 (95g:65189)
 [Hal60]
J.
H. Halton, On the efficiency of certain quasirandom sequences of
points in evaluating multidimensional integrals, Numer. Math.
2 (1960), 84–90. MR 0121961
(22 #12688)
 [Hic98]
Fred
J. Hickernell, A generalized discrepancy and
quadrature error bound, Math. Comp.
67 (1998), no. 221, 299–322. MR 1433265
(98c:65032), http://dx.doi.org/10.1090/S0025571898008941
 [HW00]
F.
J. Hickernell and H.
Woźniakowski, Integration and approximation in arbitrary
dimensions, Adv. Comput. Math. 12 (2000), no. 1,
25–58. High dimensional integration. MR 1758946
(2001d:65017), http://dx.doi.org/10.1023/A:1018948631251
 [MC94]
William
J. Morokoff and Russel
E. Caflisch, Quasirandom sequences and their discrepancies,
SIAM J. Sci. Comput. 15 (1994), no. 6,
1251–1279. MR 1298614
(95e:65009), http://dx.doi.org/10.1137/0915077
 [Nie92]
Harald
Niederreiter, Random number generation and quasiMonte Carlo
methods, CBMSNSF Regional Conference Series in Applied Mathematics,
vol. 63, Society for Industrial and Applied Mathematics (SIAM),
Philadelphia, PA, 1992. MR 1172997
(93h:65008)
 [NW00]
E. Novak and H. Wozniakowski, When are integration and discrepancy tractable?, Foundations of Computational Mathematics (R. De Vore, A. Iserles, E. Süli, eds.), Chap. 8, Cambridge University Press, Cambridge, 2001.
 [NX96]
Harald
Niederreiter and Chaoping
Xing, Quasirandom points and global function fields, Finite
fields and applications (Glasgow, 1995) London Math. Soc. Lecture Note
Ser., vol. 233, Cambridge Univ. Press, Cambridge, 1996,
pp. 269–296. MR 1433154
(97j:11037), http://dx.doi.org/10.1017/CBO9780511525988.022
 [Sai88]
Saburou
Saitoh, Theory of reproducing kernels and its applications,
Pitman Research Notes in Mathematics Series, vol. 189, Longman
Scientific & Technical, Harlow; copublished in the United States with
John Wiley & Sons, Inc., New York, 1988. MR 983117
(90f:46045)
 [SJ94]
I.
H. Sloan and S.
Joe, Lattice methods for multiple integration, Oxford Science
Publications, The Clarendon Press, Oxford University Press, New York, 1994.
MR
1442955 (98a:65026)
 [Sob69]
I.
M. \cyr{T}sobol′, Mnogomernye kvadraturnye formuly i funktsii
Khaara, Izdat. “Nauka”, Moscow, 1969 (Russian). MR 0422968
(54 #10952)
 [Sob98]
I.
M. Sobol, On quasiMonte Carlo integrations, Math. Comput.
Simulation 47 (1998), no. 25, 103–112. IMACS
Seminar on Monte Carlo Methods (Brussels, 1997). MR 1641362
(99d:65017), http://dx.doi.org/10.1016/S03784754(98)000962
 [SW98]
Ian
H. Sloan and Henryk
Woźniakowski, When are quasiMonte Carlo algorithms
efficient for highdimensional integrals?, J. Complexity
14 (1998), no. 1, 1–33. MR 1617765
(99d:65384), http://dx.doi.org/10.1006/jcom.1997.0463
 [TW98]
J.
F. Traub and A.
G. Werschulz, Complexity and information, Lezioni Lincee.
[Lincei Lectures], Cambridge University Press, Cambridge, 1998. MR 1692462
(2000m:65170)
 [Wah90]
Grace
Wahba, Spline models for observational data, CBMSNSF Regional
Conference Series in Applied Mathematics, vol. 59, Society for
Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442
(91g:62028)
 [Woz91]
H.
Woźniakowski, Average case complexity of
multivariate integration, Bull. Amer. Math.
Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015
(91i:65224), http://dx.doi.org/10.1090/S027309791991159859
 [WW96]
Grzegorz
W. Wasilkowski and Henryk
Woźniakowski, On tractability of path integration, J.
Math. Phys. 37 (1996), no. 4, 2071–2086. MR 1380891
(97a:65010), http://dx.doi.org/10.1063/1.531493
 [Aro50]
 M. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337404. MR 14:479c
 [CMO97]
 R. E. Caflisch, W. Morokoff, and A. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comput. Finance 1 (1997), 2746.
 [DR84]
 P. J. Davis and P. Rabinowitz, Methods of numerical integration, Academic Press, Orlando, Florida, 1984. MR 86d:65004
 [Duf96]
 D. Duffie, Dynamic asset pricing theory, Princeton University Press, Princeton, New Jersey, 1996.
 [Fau82]
 H. Faure, Discrépance de suites associées à un système de numération (en dimension ), Acta Arith. 41 (1982), 337351. MR 84m:10050
 [FW94]
 K. T. Fang and Y. Wang, Numbertheoretic methods in statistics, Chapman and Hall, New York, 1994. MR 95g:65189
 [Hal60]
 J. H. Halton, On the efficiency of certain quasirandom sequences of points in evaluating multidimensional integrals, Numer. Math. 2 (1960), 8490. MR 22:12688
 [Hic98]
 F. J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), 299322. MR 98c:65032
 [HW00]
 F. J. Hickernell and H. Wozniakowski, Integration and approximation in arbitrary dimensions, Adv. Comput. Math. 12 (2000), 2558. MR 2001d:65017
 [MC94]
 W. J. Morokoff and R. E. Caflisch, Quasirandom sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), 12511279. MR 95e:65009
 [Nie92]
 H. Niederreiter, Random number generation and quasiMonte Carlo methods, CBMSNSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1992. MR 93h:65008
 [NW00]
 E. Novak and H. Wozniakowski, When are integration and discrepancy tractable?, Foundations of Computational Mathematics (R. De Vore, A. Iserles, E. Süli, eds.), Chap. 8, Cambridge University Press, Cambridge, 2001.
 [NX96]
 H. Niederreiter and C. Xing, Quasirandom points and global function fields, Finite Fields and Applications (S. Cohen and H. Niederreiter, eds.), London Math. Society Lecture Note Series, no. 233, Cambridge University Press, 1996, pp. 269296. MR 97j:11037
 [Sai88]
 S. Saitoh, Theory of reproducing kernels and its applications, Longman Scientific & Technical, Essex, England, 1988. MR 90f:46045
 [SJ94]
 I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford University Press, Oxford, 1994. MR 98a:65026
 [Sob69]
 I. M. Sobol', Multidimensional quadrature formulas and Haar functions (in Russian), Izdat. ``Nauka'', Moscow, 1969. MR 54:10952
 [Sob98]
 I. M. Sobol', On quasiMonte Carlo integration, Math. Comput. Simulation 47 (1998), 103112. MR 99d:65017
 [SW98]
 I. H. Sloan and H. Wozniakowski, When are quasiMonte Carlo algorithms efficient for high dimensional integrals, J. Complexity 14 (1998), 133. MR 99d:65384
 [TW98]
 J. F. Traub and A. G. Werschulz, Complexity and information, Cambridge University Press, Cambridge, 1998. MR 2000m:65170
 [Wah90]
 G. Wahba, Spline models for observational data, SIAM, Philadelphia, 1990. MR 91g:62028
 [Woz91]
 H. Wozniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. 24 (1991), 185194. MR 91i:65224
 [WW96]
 G. W. Wasilkowski and H. Wozniakowski, On tractability of path integration, J. Math. Phys. 37 (1996), 20712087. MR 97a:65010
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/S0025571801013771
PII:
S 00255718(01)013771
Keywords:
QuasiMonte 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/9798/47 and by the NSF of China Grants 79970120 and 10001021.
Article copyright:
© Copyright 2001
American Mathematical Society
