## The asymptotic efficiency of randomized nets for quadrature

HTML articles powered by AMS MathViewer

- by Fred J. Hickernell and Hee Sun Hong PDF
- Math. Comp.
**68**(1999), 767-791 Request permission

## Abstract:

An $\mathcal {L}_{2}$-type discrepancy arises in the average- and worst-case error analyses for multidimensional quadrature rules. This discrepancy is uniquely defined by $K(x,y)$, 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 $(0,m,s)$-nets in base $b$. For moderately smooth $K(x,y)$ the discrepancy is $\operatorname {O}(N^{-1}[\log (N)]^{(s-1)/2})$, and for $K(x,y)$ with greater smoothness the discrepancy is $\operatorname {O}(N^{-3/2}[\operatorname {log}(N)]^{(s-1)/2})$, where $N=b^{m}$ is the number of points in the net. Numerical experiments indicate that the $(t,m,s)$-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.## References

- Milton Abramowitz and Irene A. Stegun,
*Handbook of mathematical functions with formulas, graphs, and mathematical tables*, National Bureau of Standards Applied Mathematics Series, No. 55, U. S. Government Printing Office, Washington, D.C., 1964. For sale by the Superintendent of Documents. MR**0167642** - P. Bratley and B. L. Fox,
*Algorithm 659: Implementing Sobol’s quasirandom sequence generator*, ACM Trans. Math. Softw.**14**(1988), 88–100. - P. Bratley, B. L. Fox, and H. Niederreiter,
*Implementation and tests of low-discrepancy sequences*, ACM Trans. Model. Comput. Simul.**2**(1992), 195–213. - K. Entacher,
*Generalized Haar function systems in the theory of uniform distribution modulo one*, Ph.D. thesis, University of Salzburg, 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 - A. Genz,
*Numerical computation of multivariate normal probabilities*, J. Comput. Graph. Statist.**1**(1992), 141–150. - Harald Niederreiter and Peter Jau-Shyong Shiue (eds.),
*Monte Carlo and quasi-Monte Carlo methods in scientific computing*, Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995. MR**1445777**, DOI 10.1007/978-1-4612-2552-2 - F. J. Hickernell,
*The mean square discrepancy of randomized nets*, ACM Trans. Model. Comput. Simul.**6**(1996), 274–296. - Fred J. Hickernell,
*Quadrature error bounds with applications to lattice rules*, SIAM J. Numer. Anal.**33**(1996), no. 5, 1995–2016. MR**1411860**, DOI 10.1137/S0036142994261439 - 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 - Loo Keng Hua and Yuan Wang,
*Applications of number theory to numerical analysis*, Springer-Verlag, Berlin-New York; Kexue Chubanshe (Science Press), Beijing, 1981. Translated from the Chinese. MR**617192** - Gerhard Larcher, Wolfgang Ch. Schmid, and Reinhard 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), no. 208, 701–716. MR**1254146**, DOI 10.1090/S0025-5718-1994-1254146-4 - Gerhard Larcher and Claudia Traunfellner,
*On the numerical integration of Walsh series by number-theoretic methods*, Math. Comp.**63**(1994), no. 207, 277–291. MR**1234426**, DOI 10.1090/S0025-5718-1994-1234426-9 - 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 - Art B. Owen,
*Randomly permuted $(t,m,s)$-nets and $(t,s)$-sequences*, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 299–317. MR**1445791**, DOI 10.1007/978-1-4612-2552-2_{1}9 - A. B. Owen,
*Monte Carlo variance of scrambled equidistribution quadrature*, SIAM J. Numer. Anal.**34**(1997), 1884–1910. - A. B. Owen,
*Scrambled net variance for integrals of smooth functions*, Ann. Stat.**25**(1997), 1541–1562. - K. Ritter,
*Average case analysis of numerical problems*, Ph.D. thesis, Universität Erlangen-Nürnberg, Erlangen, Germany, 1995. - 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** - Y. L. Tong,
*The multivariate normal distribution*, Springer Series in Statistics, Springer-Verlag, New York, 1990. MR**1029032**, DOI 10.1007/978-1-4613-9655-0 - 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 - G. W. Wasilkowski,
*Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure*, Bull. Amer. Math. Soc. (N.S.)**28**(1993), no. 2, 308–314. MR**1184000**, DOI 10.1090/S0273-0979-1993-00379-3 - 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 - S. C. Zaremba,
*Some applications of multidimensional integration by parts*, Ann. Polon. Math.**21**(1968), 85–96. MR**235731**, DOI 10.4064/ap-21-1-85-96

## Additional Information

**Fred J. Hickernell**- Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong
- ORCID: 0000-0001-6677-1324
- Email: fred@hkbu.edu.hk
**Hee Sun Hong**- Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong
- 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.
- © Copyright 1999 American Mathematical Society
- 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