Scrambled net variance for integrals of smooth functions. (English) Zbl 0886.65018

Owen, Art B.

Ann. Stat. 25, No. 4, 1541-1562 (1997).

Hybrids of quasi-Monte Carlo and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the later. This paper studies the variance of one such hybrid, randomized \((t,m,s)\)-nets, one of the best low-discrepancy sequence, by applying a multidimensional multiresolution (wavelet) analysis to the integrand. For any square integrable integrand over \(s\) dimensions, the integral estimates are unbiased and the variance is \(o(1/n)\). For smooth integrand, the variance is even of order \(n^{-3}n^{-3}(\log n)^{s-1}\), compared to \(n^{-1}\) for classical Monte Carlo method. Thus the integration errors are of order \(n^{-3/2}(\log n)^{(s-1)/2}\) in probability which compares favorably with the rate \(n^{-1}(\log n)^{s-1}\) for the best low-discrepancy sequence. Of course, the rate for randomized \((t,m,s)\)-nets is an average case result for a fixed function, while the rate for the latter describes the worst case over functions, for a fixed set of integration points.

Reviewer: Y.Xiao (Noisy le Grand)

MSC:

65D32	Numerical quadrature and cubature formulas
65C05	Monte Carlo methods

Keywords:

integration; Latin hypercube; error estimation methods; orthogonal array sampling; randomized \((t,m,s)\)-net; multiresolution (wavelet) analysis; quasi-Monte Carlo methods

Software:

TESTPACK

References:

[1]	DAUBECHIES, I. 1992. Ten Lectures on Wavelets. SIAM, Philadelphia. Z. · Zbl 0776.42018
[2]	EFRON, B. and STEIN, C. 1981. The jackknife estimate of variance. Ann. Statist. 9 586 596. Z. · Zbl 0481.62035 · doi:10.1214/aos/1176345462
[3]	GENZ, A. 1994. Testing multidimensional integration routines. In Tools, Methods and Z Languages for Scientific and Engineering Computation B. Ford, J. C. Rault and F.. Thomasset, eds. 81 94. North Holland, Amsterdam. Z.
[4]	HICKERNELL, F. J. 1996a. Quadrature error bounds and figures of merit for quasi-random points. Technical Report 111, Dept. Mathematics, Hong Kong Baptist Univ. Z.
[5]	HICKERNELL, F. J. 1996b. The mean square discrepancy of randomized nets. Technical Report 112, Dept. Mathematics, Hong Kong Baptist Univ. Z. · Zbl 0887.65030
[6]	JAWERTH, B. and SWELDENS, W. 1994. An overview of wavelet based multiresolution analyses. SIAM Review 30 377 412. Z. 2 Z n. JSTOR: · Zbl 0803.42016 · doi:10.1137/1036095
[7]	MADy CH, W. R. 1992. Some elementary properties of multiresolution analyses of L R. In Z. Wavelets: A Tutorial in Theory and Applications C. K. Chui, ed. 259 294. Academic Press, New York. Z. · Zbl 0760.41030
[8]	MOROKOFF, W. J. and CAFLISCH, R. E. 1994. Quasi-random sequences and their discrepancies. SIAM J. Sci. Comput. 15 1251 1279. Z. · Zbl 0815.65002 · doi:10.1137/0915077
[9]	NIEDERREITER, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia. Z. · Zbl 0761.65002
[10]	NIEDERREITER, H. and XING, C. 1995. Low discrepancy sequences obtained from global function fields. In Finite Fields and Applications 241 273. Cambridge Univ. Press. Z. · Zbl 0893.11029 · doi:10.1006/ffta.1996.0016
[11]	OWEN, A. B. 1992. Orthogonal array s for computer experiments, integration and visualization. Statist. Sinica 2 439 452. Z. Z. Z. · Zbl 0822.62064
[12]	OWEN, A. B. 1995. Randomly permuted t, m, s -nets and t, s -sequences. In Monte Carlo and Z Quasi-Monte Carlo Methods in Scientific Computing H. Niederreiter and J.-S. Shiue,. eds. 299 317. Springer, New York. Z. · Zbl 0831.65024
[13]	OWEN, A. B. 1997. Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34. To appear. Z. JSTOR: · Zbl 0890.65023 · doi:10.1137/S0036142994277468
[14]	PASKOV, S. H. 1993. Average case complexity of multivariate integration for smooth functions. J. Complexity 9 291 312. Z. · Zbl 0781.65017 · doi:10.1006/jcom.1993.1019
[15]	RITTER, K. 1995. Average case analysis of numerical problems. Ph.D. dissertation, Univ. Erlangen, Germany. Z.
[16]	RITTER, K., WASILKOWSKI, G. W. and WOZNIAKOWSKI, H. 1993. On multivariate integration for Ź. stochastic processes. In Numerical Integration H. Brass and G. Hammerlin, eds. 112 \" 331 347. Birkhauser, Basel. \" Z. · Zbl 0791.41026
[17]	WAHBA, G. 1990. Spline Models for Observational Data. SIAM, Philadelphia. Z. · Zbl 0813.62001
[18]	WASILKOWSKI, G. W. 1993. Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure. Bull. Amer. Math. Soc. 28 308 314. · Zbl 0770.41020 · doi:10.1090/S0273-0979-1993-00379-3
[19]	WOZNIAKOWSKI, H. 1991. Average case complexity of multivariate integration. Bull. Amer. Ḿath. Soc. 24 185 194. · Zbl 0729.65010 · doi:10.1090/S0273-0979-1991-15985-9
[20]	STANFORD, CALIFORNIA 94305 E-MAIL: owen@play fair.stanford.edu