Computable error bounds for quasi-Monte Carlo using points with non-negative local discrepancy

Let f:[0,1]ᵈ→R be a completely monotone integrand as defined by Aistleitner and Dick (2015, Acta Arithmetica, 167, 143–171) and let points x₀, ,xₙ₋₁∈ [0,1]ᵈ have a non-negative local discrepancy (NNLD) everywhere in [0,1]ᵈ. We show how to use these properties to get a non-asymptotic and computable upper bound for the integral of f over [0,1]ᵈ. An analogous non-positive local discrepancy property provides a computable lower bound. It has been known since Gabai (1967, Illinois J. Math., 11, 1–12) that the two-dimensional Hammersley points in any base b 2 have NNLD. Using the probabilistic notion of associated random variables, we generalize Gabai’s finding to digital nets in any base b 2 and any dimension d 1 when the generator matrices are permutation matrices. We show that permutation matrices cannot attain the best values of the digital net quality parameter when d 3. As a consequence the computable absolutely sure bounds we provide come with less accurate estimates than the usual digital net estimates do in high dimensions. We are also able to construct high-dimensional rank one lattice rules that are NNLD. We show that those lattices do not have good discrepancy properties: any lattice rule with the NNLD property in dimension d 2 either fails to be projection regular or has all its points on the main diagonal. Complete monotonicity is a very strict requirement that for some integrands can be mitigated via a control variate.