Bounds on Walsh coefficients by dyadic difference and a new Koksma-Hlawka type inequality for Quasi-Monte Carlo integration

Abstract

In this paper we give a new Koksma-Hlawka type inequality for Quasi-Monte Carlo (QMC) integration. QMC integration of a function $f:[0,1{)}^s\to \mathbb{R}$ by a finite point set $\mathcal{P}\subset [0,1{)}^s$ is the approximation of the integral $I(f):={\int }_{[0,1{)}^s}f(\mathbf{x})d\mathbf{x}$ by the average $I_{\mathcal{P}}(f):=\frac{1}{|\mathcal{P}|}{\sum }_{\mathbf{x}\in \mathcal{P}}f(\mathbf{x})$. We treat a certain class of point sets $\mathcal{P}$ called digital nets. A Koksma-Hlawka type inequality is an inequality bounding the integration error $\text{Err}(f;\mathcal{P}):=I(f)-I_{\mathcal{P}}(f)$ by a bound of the form $|\text{Err}(f;\mathcal{P})|\le C\cdot \Vert f\Vert \cdot D(\mathcal{P})$. We can obtain a Koksma-Hlawka type inequality by estimating bounds on $|\hat{f}(\mathbf{k})|$, where $\hat{f}(\mathbf{k})$ is a generalized Fourier coefficient with respect to the Walsh system. In this paper we prove bounds on Walsh coefficients $\hat{f}(\mathbf{k})$ by introducing an operator called `dyadic difference' ${\partial }_{i,n}$. By converting dyadic differences ${\partial }_{i,n}$ to derivatives $\frac{\partial }{\partial x_i}$, we get a new bound on $|\hat{f}(\mathbf{k})|$ for a function $f$ whose mixed partial derivatives up to order $\alpha$ in each variable are continuous. This new bound is smaller than the known bound on $|\hat{f}(\mathbf{k})|$ under some condition. The new Koksma-Hlawka inequality is derived using this new bound on the Walsh coefficients.

21 pages

Cited by in corpus (4)

• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients
• The Mean Square Quasi-Monte Carlo Error for Digitally Shifted Digital Nets
• Quasi-Monte Carlo integration for twice differentiable functions over a triangle
• Walsh Figure of Merit for Digital Nets: An Easy Measure for Higher Order Convergent QMC