×

Walsh functions, scrambled \((0, m, s)\)-nets, and negative covariance: applying symbolic computation to quasi-Monte Carlo integration. (English) Zbl 1524.65020

Summary: We investigate base \(b\) Walsh functions for which the variance of the integral estimator based on a scrambled \((0, m, s)\)-net in base \(b\) is less than or equal to that of the Monte-Carlo estimator based on the same number of points. First we compute the Walsh decomposition for the joint probability density function of two distinct points randomly chosen from a scrambled \((t, m, s)\)-net in base \(b\) in terms of certain counting numbers and simplify it in the special case \(t\) is zero. Using this, we obtain an expression for the covariance of the integral estimator in terms of the Walsh coefficients of the function. Finally, we prove that the covariance of the integral estimator is negative when the Walsh coefficients of the function satisfy a certain decay condition. To do this, we use creative telescoping and recurrence solving algorithms from symbolic computation to find a sign equivalent closed form expression for the covariance term.

MSC:

65C05 Monte Carlo methods
11K45 Pseudo-random numbers; Monte Carlo methods
65D30 Numerical integration
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Dick, J.; Pillichshammer, F., Digital nets and sequences: discrepancy theory and quasi-Monte Carlo integration (2010), Cambridge University Press, UK · Zbl 1282.65012
[2] . DLMF, in: F.W.J. Olvera, A.B. Olde Daalhuis, B.I.S. D. W. Lozier, R.F. Boisvert, C.W. Clark, B.R. Miller, B.V. Saunders, H.S. Cohl, M.A. McClain (Eds.), NIST Digital Library of Mathematical Functions, Release 1.0.028 of 2020-09-15, http://dlmf.nist.gov/. · Zbl 1019.65001
[3] Kauers, M., Guessing handbookTechnical Report 09-07 (2009), RISC Report Series, Johannes Kepler University: RISC Report Series, Johannes Kepler University Linz, Austria, http://www.risc.jku.at/research/combinat/software/Guess/
[4] Koutschan, C., Advanced applications of the holonomic systems approach (2009), Johannes Kepler University: Johannes Kepler University Linz, Austria, (Ph.D. thesis) · Zbl 1344.68301
[5] Koutschan, C., HolonomicFunctions user’s guideTechnical Report 10 - 01 (2010), RISC Report Series, Johannes Kepler University: RISC Report Series, Johannes Kepler University Linz, Austria, http://www.risc.jku.at/publications/download/risc_3934/hf.pdf
[6] Koutschan, C.; Wong, E., Creative telescoping on multiple sums, Math. Comput. Sci. (2020), under review, arXiv:2010.08889
[7] Lemieux, C., Negative dependence, scrambled nets, and variance bounds, Math. Oper. Res., 43, 228-251 (2017) · Zbl 1445.62126
[8] Niederreiter, H., Random number generation and quasi-Monte Carlo methods, Vol. 63 (1992), SIAM CBMS-NSF Regional Conference Series in Applied Mathematics · Zbl 0761.65002
[9] Niederreiter, H., Low-discrepancy point sets obtained by digital constructions over finite fields, Czechoslovak Math. J., 42, 143-166 (1992) · Zbl 0757.11024
[10] Owen, A. B., Randomly permuted \(( t , m , s )\)-nets and \(( t , s )\)-sequences, (Niederreiter, H.; Shiue, P. J., Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Vol. 106 (1995), Springer: Springer New York, NY), 299-317 · Zbl 0831.65024
[11] Owen, A. B., Scrambled net variance for integrals of smooth functions, Ann. Statist., 25, 4, 1541-1562 (1997) · Zbl 0886.65018
[12] Owen, A. B., Variance and discrepancy with alternative scramblings, ACM Trans. Model. Comput. Simul., 13, 363-378 (2003) · Zbl 1390.65037
[13] Schneider, C., Symbolic summation assists combinatorics, Sém. Lothar. Combin., 56, 1-36 (2007), Article B56b, http://www.risc.jku.at/research/combinat/software/Sigma/ · Zbl 1188.05001
[14] Walsh, J. L., A closed set of normal orthogonal functions, Amer. J. Math., 45 (1922) · JFM 48.0492.10
[15] Wiart, J.; Lemieux, C.; Dong, G., On the dependence structure of scrambled \(( t , m , s )\)-nets (2019), arXiv:1903.09877
[16] Wong, E., Website for the paper with Mathematica computations (2020), https://wongey.github.io/digital-nets-walsh/
[17] Zeilberger, D., A holonomic systems approach to special functions identities, J. Comput. Appl. Math., 32, 321-368 (1990) · Zbl 0738.33001
[18] Zeilberger, D., The method of creative telescoping, J. Symbolic Comput., 11, 3, 195-204 (1991) · Zbl 0738.33002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.