Mathematics of Computation

Author(s): Rong-Xian Yue; Fred J. Hickernell.
Journal: Math. Comp. 74 (2005), 1871-1893.
MSC (2000): Primary 65C05, 65D30
Posted: March 3, 2005
Retrieve article in: PDF DVI PostScript

Abstract: We study the randomized worst-case error and the randomized error of scrambled quasi-Monte Carlo (QMC) quadrature as proposed by Owen. The function spaces considered in this article are the weighted Hilbert spaces generated by Haar-like wavelets and the weighted Sobolev-Hilbert spaces. Conditions are found under which multivariate integration is strongly tractable in the randomized worst-case setting and the randomized setting, respectively. The $\varepsilon$ -exponents of strong tractability are found for the scrambled Niederreiter nets and sequences. The sufficient conditions for strong tractability for Sobolev spaces are more lenient for scrambled QMC quadratures than those for deterministic QMC net quadratures.

1.: Heinrich, S., Hickernell, F. J. and Yue R.-X. (2004). Optimal quadrature for Haar wavelet spaces, Math. Comp. 73, 259-277. MR 2034121 (2004k:65037)
2.: Hickernell, F. J. (1996). The mean square discrepancy of randomized nets, ACM Trans. Model. Comput. Simul. 6, 274-296.
3.: Hickernell, F. J. and Hong, H. S. (1999). The asymptotic efficiency of randomized nets for quadrature, Math. Comp., 68, 767-791. MR 1609662 (99i:65021)
4.: Hickernell, F. J. and Wang, X. (2002). The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Math. Comp., 71, 1641-1661.MR 1933048 (2003i:65009)
5.: Hickernell, F. J. and Wozniakowski, H. (2000). Integration and approximation in arbitrary dimensions, Adv. Comput. Math. 12, 25-58.MR 1758946 (2001d:65017)
6.: Hickernell, F. J. and Wozniakowski, H. (2001a). The price of pessimism for multidimensional quadrature, J. Complexity, 17, 625-659.MR 1881662 (2002m:60013)
7.: Hickernell, F. J. and Wozniakowski, H. (2001b). Tractability of multivariate integration for periodic functions, J. Complexity, 17, 660-682.MR 1881663 (2003g:65028)
8.: Hickernell, F. J. and Yue, R.-X. (2000). The mean square discrepancy of scrambled -sequences, SIAM J. Numer. Anal. 38, 1089-1112. MR 1786132 (2002c:65009)
9.: Kuo, F. Y. and Sloan, I. H. (2004). Quasi-Monte Carlo methods can be efficient for integration over products of spheres, J. Complexity to appear.
10.: Niederreiter, H. (1988). Low-discrepancy and low-dispersion sequences, J. Number Theory 30, 51-70. MR 0960233 (89k:11064)
11.: Niederreiter, H. (1992). Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia. MR 1172997 (93h:65008)
12.: Niederreiter, H. and Pirsic, G. (2001). The microstructure of -nets, J. Complexity 17, 683-696. MR 1881664 (2002m:11073)
13.: Owen, A. B. (1995). Randomly permuted -nets and -sequences, in Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P. J. S. Shiue, eds.), Lecture Notes in Statistics, Vol. 106, Springer-Verlag, 299-317. MR 1445791 (97k:65013)
14.: Owen, A. B. (1997a). Monte Carlo variance of scrambled equidistribution quadrature, SIAM J. Num. Anal. 34, 1884-1910. MR 1472202 (98h:65006)
15.: Owen, A. B. (1997b). Scrambled net variance for integrals of smooth functions, Ann. Statist. 25, 1541-1562. MR 1463564 (98j:65004)
16.: Owen, A. B. (1998). Scrambled Sobol and Niederreiter-Xing points, J. Complexity 14, 466-489. MR 1659008 (2000c:65005)
17.: Sloan, I. H. and Wozniakowski, H. (1998). When are quasi-Monte Carlo algorithms efficient for high dimensional integrals, J. Complexity 14, 1-33.MR 1617765 (99d:65384)
18.: Sloan, I. H. and Wozniakowski, H. (2001). Tractability of multivariate integration for weighted Korobov classes, J. Complexity 17, 697-721.MR 1881665 (2003g:65030)
19.: Sloan, I. H. and Wozniakowski, H. (2004). When does Monte Carlo depend polynomially on the number of variables? in Monte Carlo and Quasi-Monte Carlo Methods 2002 (H. Niederreiter, editor), Springer-Verlag, 407-437.MR 2076949
20.: Sobol', I. M. (1967). The distribution of points in a cube and the accurate evaluation of integrals (in Russian), Zh. Vychisl. Mat. i Mat. Phys. 7, 784-802. MR 0219238 (36:2321)
21.: Wahba, G. (1990). Spline Models for Observational Data, SIAM, Philadelphia.MR 1045442 (91g:62028)
22.: Wang, X. (2002). A constructive approach to strong tractability using quasi-Monte Carlo algorithms, J. Complexity 18, 683-701. MR 1928803 (2003m:65008)
23.: Wang, X. (2003). Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Math. Comp. 72, 823-838. MR 1954970 (2003m:65009)
24.: Wozniakowski, H. (2000). Efficiency of quasi-Monte Carlo algorithms for high dimensional integrals, In Monte Carlo and Quasi-Monte Carlo Methods 1998 (H. Niederreiter and J. Spanier, eds.), Springer-Verlag, Berlin, pp. 114-136.MR 1849846 (2002e:65015)
25.: Yue, R.-X. and Hickernell, F. J. (2001). Integration and approximation based on scrambled sampling in arbitrary dimensions, J. Complexity 17, 897.MR 1881675 (2002m:65005)
26.: Yue, R.-X. (1999). Variance of quadrature over scrambled unions of nets, Statistica Sinica 9, 451-473. MR 1707849 (2000h:65022)
27.: Yue, R.-X. and Mao, S.-S. (1999). On the variance of quadrature over scrambled nets and sequences, Stat. and Prob. Letters 44, 267-280. MR 1711617 (2000i:65008)

Rong-Xian Yue
Affiliation: Division of Scientific Computation, E-Institute of Shanghai Universities, 100 Guilin Road, Shanghai 200234, People's Republic of China
Email: yue2@shnu.edu.cn

Fred J. Hickernell
Affiliation: Department of Applied Mathematics, Shanghai Normal University, Shanghai, People's Republic of China
Address at time of publication: Department of Applied Mathematics, Illinois Institute of Technology, 10 West 32nd Street, E1 Building, Room 208, Chicago, Illinois 60616-3793
Email: fred@hkbu.edu.hk, hickernell@iit.edu

DOI: 10.1090/S0025-5718-05-01755-2
PII: S 0025-5718(05)01755-2
Keywords: Multivariate integration, quasi--Monte Carlo methods, nets and sequences, scrambling
Received by editor(s): November 24, 2003
Received by editor(s) in revised form: July 6, 2004
Posted: March 3, 2005
Additional Notes: This work was partially supported by Hong Kong Research Grants Council grant HKBU/2020/02P, National Science Foundation of China grant 10271078, E-Institute of Shanghai Municipal Education Commission (E03004), and the Special Funds for Major Specialties of the Shanghai Education Committee
Copyright of article: Copyright 2005, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS