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

preprint2015arXivOpen access

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→Rf\colon[0,1)^s\rightarrow \mathbb{R} by a finite point set P⊂[0,1)s\mathcal{P}\subset [0,1)^s is the approximation of the integral I(f):=∫[0,1)sf(x) dxI(f):=\int_{[0,1)^s}f(\mathbf{x})\,d\mathbf{x} by the average IP(f):=1∣P∣∑x∈Pf(x)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 P\mathcal{P} called digital nets. A Koksma-Hlawka type inequality is an inequality bounding the integration error Err(f;P):=I(f)−IP(f)\text{Err}(f;\mathcal{P}):=I(f)-I_{\mathcal{P}}(f) by a bound of the form ∣Err(f;P)∣≤C⋅∥f∥⋅D(P)|\text{Err}(f;\mathcal{P})|\le C\cdot \|f\|\cdot D(\mathcal{P}). We can obtain a Koksma-Hlawka type inequality by estimating bounds on ∣f^(k)∣|\hat{f}(\mathbf{k})|, where f^(k)\hat{f}(\mathbf{k}) is a generalized Fourier coefficient with respect to the Walsh system. In this paper we prove bounds on Walsh coefficients f^(k)\hat{f}(\mathbf{k}) by introducing an operator called `dyadic difference' ∂i,n\partial_{i,n}. By converting dyadic differences ∂i,n\partial_{i,n} to derivatives ∂∂xi\frac{\partial }{\partial x_i}, we get a new bound on ∣f^(k)∣|\hat{f}(\mathbf{k})| for a function ff whose mixed partial derivatives up to order αα in each variable are continuous. This new bound is smaller than the known bound on ∣f^(k)∣|\hat{f}(\mathbf{k})| under some condition. The new Koksma-Hlawka inequality is derived using this new bound on the Walsh coefficients.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.