### 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.

• Update (May 4, 2021): This sequel has been accepted to the CASC 2020 Special Issue of Springer Mathematics in Computer Science and is online with DOI:10.1007/s11786-021-00514-3. The preprint is available here arXiv:2010.08889. The Mathematica code can be downloaded from here: CASC2020Files.zip (3MB).

• Errata (July 2021): Section 3.8 - there is a missing negative sign in front of the given rational function. This is just a typo and the written conclusion holds with the typo fixed.
1. G. Andrews, P. Paule, and C. Schneider. Plane partitions VI: Stem-bridge’s TSPP theorem. Advances in Applied Mathematics 34 (2005).

2. A. Bostan, P. Lairez, and B. Salvy Multiple binomial sums. Journal of Symbolic Computation 80, 351–386 (2017).

3. F. Chyzak, Groebner bases, symbolic summation and symbolic integration. Groebner Bases and Applications UK: Cambridge University Press, pp. 32–60 (1997).

4. F. Chyzak, A. Mahboubi, T. Sibut-Pinote, and E. Tassi. A computer-algebra-based formal proof of the irrationality of ζ(3). In: G. Klein, and R. Gamboa (eds.) Springer. ITP 2014: Interactive Theorem Proving 8558, 160–176 (2014).

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

6. 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.

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

8. M. Kauers, M. Jaroschek, and F. Johansson. Ore Polynomials in Sage. Lecture Notes in Computer Science 8942, 105–125 (2015).

9. C. Koutschan, Advanced Applications of the Holonomic Systems Approach. Ph.D. Thesis, Johannes Kepler University, Linz, Austria (2009).

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

11. R. Lyons, P. Paule, and A. Riese. A computer proof of a series evaluation in termsof harmonic numbers. Applicable Algebra in Engineering, Communication and Computing 13, 327–333 (2002)

12. H. Prodinger. Descendants in heap ordered trees or a triumph of computer algebra. The Electronic Journal of Combinatorics 3, R29 (1996).

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

14. H. Niederreiter, Low-Discrepancy Point Sets Obtained by Digital Constructions over Finite Fields. Czechoslovakia Mathematics Journal 42, 143–166 (1992).

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

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

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

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

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

20. J. L. Walsh, A Closed Set of Normal Orthogonal Functions. American Journal of Mathematics 45(1), 5-24 (1923).

21. K. Wegschaider. Computer generated proofs of binomial multi-sum identities. Ph.D. Thesis, Johannes Kepler University, Linz, Austria (1997).

22. J. Wiart, C. Lemieux, and G. Dong, On the Dependence Structure of Scrambled $$(t, m, s)$$-nets. Monte Carlo Methods and Applications 27(1), 1-26 (2021).

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

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