Bounds on Walsh coefficients by dyadic difference and a new Koksma-Hlawka type inequality for Quasi-Monte Carlo integration
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→R by a finite point set P⊂[0,1)s is the approximation of the integral I(f):=∫[0,1)sf(x)dx by the average IP(f):=∣P∣1∑x∈Pf(x). We treat a certain class of point sets P called digital nets. A Koksma-Hlawka type inequality is an inequality bounding the integration error Err(f;P):=I(f)−IP(f) by a bound of the form ∣Err(f;P)∣≤C⋅∥f∥⋅D(P). We can obtain a Koksma-Hlawka type inequality by estimating bounds on ∣f^(k)∣, where f^(k) is a generalized Fourier coefficient with respect to the Walsh system. In this paper we prove bounds on Walsh coefficients f^(k) by introducing an operator called `dyadic difference' ∂i,n. By converting dyadic differences ∂i,n to derivatives ∂xi∂, we get a new bound on ∣f^(k)∣ for a function f whose mixed partial derivatives up to order α in each variable are continuous. This new bound is smaller than the known bound on ∣f^(k)∣ under some condition. The new Koksma-Hlawka inequality is derived using this new bound on the Walsh coefficients.