### Walsh functions, scrambled (0,m,s)-nets, and negative covariance: applying symbolic computation to quasi-Monte Carlo integration

Project maintained by wongey Hosted on GitHub Pages — Theme by mattgraham

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.

### CASC 2020

• Elaine gave a talk at CASC 2020 discussing the symbolic computation aspects of this paper:

• Christoph Koutschan and Elaine wrote a sequel to this paper for the post proceedings of CASC, highlighting some of the technical details that were not mentioned in the original and showing different ways to speed up computations. This sequel has been submitted for publication (preprint at arXiv:2010.08889). The code is provided here:

1. J. Dick and F. Pillichshammer. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo integration. UK: Cambridge University Press, 2010.

2. DLMF. NIST Digital Library of Mathematical Functions, 2019. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller and B. V. Saunders, eds.

3. M. Kauers, Guessing Handbook. Technical Report 09-07, RISC Report Series, Johannes Kepler University, Linz, Austria, 2009.

4. C. Koutschan, Advanced Applications of the Holonomic Systems Approach. Ph.D. Thesis, Linz, Austria, 2009.

5. C. Koutschan, HolonomicFunctions User’s Guide. Technical Report 10-01, RISC Report Series, Johannes Kepler University, Linz, Austria, 2010.

6. C. Lemieux, Negative Dependence, Scrambled Nets, and Variance Bounds. Mathematics of Operations Research 43 (2017), 228–251.

7. H. Niederreiter, Low-Discrepancy Point Sets Obtained by Digital Constructions over Finite Fields. Czechoslovak Math. J 42 (1992), 143–166.

8. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods. Vol. 63, SIAM CBMS-NSF Regional Conference Series in Applied Mathematics, 1992.

9. A. B. Owen, Scrambled Net Variance for Integrals of Smooth Functions. The Annals of Statistics 25 (1997), No. 4, 1541–1562.

10. A. B. Owen, Randomly Permuted $$(t, m, s)$$-nets and $$(t, s)$$-sequences. Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, 1995, pp. 299–317.

11. A. B. Owen, Variance and Discrepancy with Alternative Scramblings. ACM Transactions on Modeling and Computer Simulation 13 (2003), 363–378.

12. C. Schneider, Symbolic Summation Assists Combinatorics. Séminaire Lotharingien de Combinatoire 56 (2007), 1–36. Article B56b.

13. J. L. Walsh, A Closed Set of Normal Orthogonal Functions. Amer. J. Math. 45 (192211).

14. J. Wiart, C. Lemieux, and G. Dong, On the Dependence Structure of Scrambled $$(t, m, s)$$-nets. arXiv e-prints (2019), submitted for publication (arXiv:1903.09877).

15. D. Zeilberger, A Holonomic Systems Approach to Special Functions Identities. Journal of Computational and Applied Mathematics 32 (1990), 321–368.

16. D. Zeilberger, The Method of Creative Telescoping. Journal of Symbolic Computation 11 (1991), 195-204.