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

N1 - Publisher Copyright:
© 2020 International Association for Mathematics and Computers in Simulation (IMACS)

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 - http://www.scopus.com/inward/record.url?scp=85096699093&partnerID=8YFLogxK

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 -