The asymptotic efficiency

of randomized nets for quadrature

Authors:
Fred J. Hickernell and Hee Sun Hong

Journal:
Math. Comp. **68** (1999), 767-791

MSC (1991):
Primary 65D30, 65D32

DOI:
https://doi.org/10.1090/S0025-5718-99-01019-4

MathSciNet review:
1609662

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An -type discrepancy arises in the average- and worst-case error analyses for multidimensional quadrature rules. This discrepancy is uniquely defined by , which serves as the covariance kernel for the space of random functions in the average-case analysis and a reproducing kernel for the space of functions in the worst-case analysis. This article investigates the asymptotic order of the root mean square discrepancy for randomized -nets in base . For moderately smooth the discrepancy is , and for with greater smoothness the discrepancy is , where is the number of points in the net. Numerical experiments indicate that the -nets of Faure, Niederreiter and Sobol' do not necessarily attain the higher order of decay for sufficiently smooth kernels. However, Niederreiter nets may attain the higher order for kernels corresponding to spaces of periodic functions.

**[AS64]**M. Abramowitz and I. A. Stegun (eds.),*Handbook of mathematical functions with formulas, graphs and mathematical tables*, U. S. Government Printing Office, Washington, DC, 1964. MR**29:4914****[BF88]**P. Bratley and B. L. Fox,*Algorithm 659: Implementing Sobol's quasirandom sequence generator*, ACM Trans. Math. Softw.**14**(1988), 88-100.**[BFN92]**P. Bratley, B. L. Fox, and H. Niederreiter,*Implementation and tests of low-discrepancy sequences*, ACM Trans. Model. Comput. Simul.**2**(1992), 195-213.**[Ent96]**K. Entacher,*Generalized Haar function systems in the theory of uniform distribution modulo one*, Ph.D. thesis, University of Salzburg, 1996.**[Fau82]**H. Faure,*Discrépance de suites associées à un système de numération (en dimension s)*, Acta Arith.**41**(1982), 337-351. MR**84m:10050****[Gen92]**A. Genz,*Numerical computation of multivariate normal probabilities*, J. Comput. Graph. Statist.**1**(1992), 141-150.**[Hic95]**F. J. Hickernell,*A comparison of random and quasirandom points for multidimensional quadrature*, 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, New York, 1995, pp. 213-227. MR**97j:65002****[Hic96a]**F. J. Hickernell,*The mean square discrepancy of randomized nets*, ACM Trans. Model. Comput. Simul.**6**(1996), 274-296.**[Hic96b]**F. J. Hickernell,*Quadrature error bounds with applications to lattice rules*, SIAM J. Numer. Anal.**33**(1996), 1995-2016. MR**97m:65050****[Hic98]**F. J. Hickernell,*A generalized discrepancy and quadrature error bound*, Math. Comp.**67**(1998), 299-322. MR**98c:65032****[HW81]**L. K. Hua and Y. Wang,*Applications of number theory to numerical analysis*, Springer-Verlag, Berlin, and Science Press, Beijing, 1981. MR**83g:10034****[LSW94]**G. Larcher, W. Ch. Schmid, and R. Wolf,*Representation of functions as Walsh series to different bases and an application to the numerical integration of high-dimensional Walsh series.*, Math. Comp.**63**(1994), 701-716. MR**95a:65045****[LT94]**G. Larcher and C. Traunfellner,*On the numerical integration of Walsh series by number-theoretic methods*, Math. Comp.**63**(1994), 277-291. MR**94j:65030****[MC94]**W. J. Morokoff and R. E. Caflisch,*Quasi-random sequences and their discrepancies*, SIAM J. Sci. Comput.**15**(1994), 1251-1279. MR**95e:65009****[Nie92]**H. Niederreiter,*Random number generation and quasi-Monte Carlo methods*, SIAM, Philadelphia, 1992. MR**93h:65008****[Owe95]**A. B. Owen,*Randomly permuted -nets and -sequences*, 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, New York, 1995, pp. 299-317. MR**97k:65013****[Owe97a]**A. B. Owen,*Monte Carlo variance of scrambled equidistribution quadrature*, SIAM J. Numer. Anal.**34**(1997), 1884-1910. CMP**98:01****[Owe97b]**A. B. Owen,*Scrambled net variance for integrals of smooth functions*, Ann. Stat.**25**(1997), 1541-1562. CMP**97:16****[Rit95]**K. Ritter,*Average case analysis of numerical problems*, Ph.D. thesis, Universität Erlangen-Nürnberg, Erlangen, Germany, 1995.**[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****[Ton90]**Y. L. Tong,*The multivariate normal distribution*, Springer-Verlag, New York, 1990. MR**91g:60021****[Wah90]**G. Wahba,*Spline models for observational data*, SIAM, Philadelphia, 1990. MR**91g:62028****[Was93]**G. W. Wasilkowski,*Integration and approximation of multivariate functions: Average case complexity with isotropic Wiener measure*, Bull. Amer. Math. Soc.**28**(1993), 308-314. MR**93i:65136****[Wo\'{z}91]**H. Wo\'{z}niakowski,*Average case complexity of multivariate integration*, Bull. Amer. Math. Soc.**24**(1991), 185-194. MR**91i:65224****[Zar68]**S. K. Zaremba,*Some applications of multidimensional integration by parts*, Ann. Polon. Math.**21**(1968), 85-96. MR**38:4034**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
65D30,
65D32

Retrieve articles in all journals with MSC (1991): 65D30, 65D32

Additional Information

**Fred J. Hickernell**

Affiliation:
Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong

Email:
fred@hkbu.edu.hk, http://www.math.hkbu.edu.hk/~fred

**Hee Sun Hong**

Affiliation:
Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong

DOI:
https://doi.org/10.1090/S0025-5718-99-01019-4

Keywords:
$\mathcal{L}_{2}$-discrepancy,
multidimensional integration,
$(t,
m,
s)$-nets,
number-theoretic nets and sequences

Received by editor(s):
March 6, 1997

Received by editor(s) in revised form:
September 11, 1997

Additional Notes:
This research was supported by a HKBU FRG grant 95-96/II-01.

Article copyright:
© Copyright 1999
American Mathematical Society