The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
HTML articles powered by AMS MathViewer
- by Fred J. Hickernell and Xiaoqun Wang PDF
- Math. Comp. 71 (2002), 1641-1661 Request permission
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
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- 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), 27–46.
- 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
- D. Duffie, Dynamic asset pricing theory, Princeton University Press, Princeton, New Jersey, 1996.
- Henri Faure, Discrépance de suites associées à un système de numération (en dimension $s$), Acta Arith. 41 (1982), no. 4, 337–351 (French). MR 677547, DOI 10.4064/aa-41-4-337-351
- K.-T. Fang and Y. Wang, Number-theoretic methods in statistics, Monographs on Statistics and Applied Probability, vol. 51, Chapman & Hall, London, 1994. MR 1284470, DOI 10.1007/978-1-4899-3095-8
- J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math. 2 (1960), 84–90. MR 121961, DOI 10.1007/BF01386213
- Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
- 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, DOI 10.1023/A:1018948631251
- William J. Morokoff and Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251–1279. MR 1298614, DOI 10.1137/0915077
- Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
- E. Novak and H. Woźniakowski, 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.
- 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, DOI 10.1017/CBO9780511525988.022
- 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
- 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
- I. M. Tsobol′, Mnogomernye kvadraturnye formuly i funktsii Khaara, Izdat. “Nauka”, Moscow, 1969 (Russian). MR 0422968
- I. M. Sobol, On quasi-Monte Carlo integrations, Math. Comput. Simulation 47 (1998), no. 2-5, 103–112. IMACS Seminar on Monte Carlo Methods (Brussels, 1997). MR 1641362, DOI 10.1016/S0378-4754(98)00096-2
- Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
- J. F. Traub and A. G. Werschulz, Complexity and information, Lezioni Lincee. [Lincei Lectures], Cambridge University Press, Cambridge, 1998. MR 1692462, DOI 10.1080/16073606.1997.9631861
- Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128
- H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015, DOI 10.1090/S0273-0979-1991-15985-9
- Grzegorz W. Wasilkowski and Henryk Woźniakowski, On tractability of path integration, J. Math. Phys. 37 (1996), no. 4, 2071–2086. MR 1380891, DOI 10.1063/1.531493
Additional Information
- Fred J. Hickernell
- Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong SAR, China
- ORCID: 0000-0001-6677-1324
- Email: fred@hkbu.edu.hk
- Xiaoqun Wang
- Affiliation: Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China
- Email: xwang@math.tsinghua.edu.cn
- 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.
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 1641-1661
- MSC (2000): Primary 65C05, 65D30
- DOI: https://doi.org/10.1090/S0025-5718-01-01377-1
- MathSciNet review: 1933048