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

Jaspar Wiart; Elaine Wong

doi:10.1016/j.matcom.2020.10.026

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

Jaspar Wiart
, Elaine Wong

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	277-295
Number of pages	19
Journal	Mathematics and Computers in Simulation
Volume	182
DOIs	https://doi.org/10.1016/j.matcom.2020.10.026
State	Published - Apr 2021
Externally published	Yes

Funding

We are particularly grateful to Josef Dick, Christoph Koutschan, Peter Kritzer and Christiane Lemieux for taking time out of their busy schedules to guide us in the right direction at the beginning, and their subsequent encouragement towards the completion of this work. Both authors want to especially acknowledge Christoph for his valuable comments that improved this manuscript greatly. E. Wong would also like to thank Manuel Kauers and Veronika Pillwein for the opportunity to give a talk about this work at OPSFA and to Lin Jiu, Mehdi Makhul, Isabel Pirsic and Ali Uncu for some helpful commentary. E. Wong is supported by the Austrian Science Fund (FWF) : F5011-N15 . J. Wiart is supported by the Austrian Science Fund (FWF) , Projects F5506-N26 and F5509-N26 , which are parts of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.

Keywords

Creative telescoping
Quasi-Monte Carlo integration
Scrambled digital nets
Symbolic computation
Symbolic summation
Walsh functions

Access to Document

10.1016/j.matcom.2020.10.026

Cite this

@article{61cef920275c4e38a990a17cefd49818,

title = "Walsh functions, scrambled (0,m,s)-nets, and negative covariance: Applying symbolic computation to quasi-Monte Carlo integration",

abstract = "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.",

keywords = "Creative telescoping, Quasi-Monte Carlo integration, Scrambled digital nets, Symbolic computation, Symbolic summation, Walsh functions",

author = "Jaspar Wiart and Elaine Wong",

note = "Publisher Copyright: {\textcopyright} 2020 International Association for Mathematics and Computers in Simulation (IMACS)",

year = "2021",

month = apr,

doi = "10.1016/j.matcom.2020.10.026",

language = "English",

volume = "182",

pages = "277--295",

journal = "Mathematics and Computers in Simulation",

issn = "0378-4754",

publisher = "Elsevier",

}

TY - JOUR

T1 - Walsh functions, scrambled (0,m,s)-nets, and negative covariance

T2 - Applying symbolic computation to quasi-Monte Carlo integration

AU - Wiart, Jaspar

AU - Wong, Elaine

PY - 2021/4

Y1 - 2021/4

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

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

KW - Creative telescoping

KW - Quasi-Monte Carlo integration

KW - Scrambled digital nets

KW - Symbolic computation

KW - Symbolic summation

KW - Walsh functions

UR - https://www.scopus.com/pages/publications/85096699093

U2 - 10.1016/j.matcom.2020.10.026

DO - 10.1016/j.matcom.2020.10.026

M3 - Article

AN - SCOPUS:85096699093

SN - 0378-4754

VL - 182

SP - 277

EP - 295

JO - Mathematics and Computers in Simulation

JF - Mathematics and Computers in Simulation

ER -

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

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this