A Generalized Faulhaber Inequality, Improved Bracketing Covers, and Applications to Discrepancy

Abstract

We prove a generalized Faulhaber inequality to bound the sums of the $j$-th powers of the first $n$ (possibly shifted) natural numbers. With the help of this inequality we are able to improve the known bounds for bracketing numbers of $d$-dimensional axis-parallel boxes anchored in $0$ (or, put differently, of lower left orthants intersected with the $d$-dimensional unit cube $[0,1{]}^d$). We use these improved bracketing numbers to establish new bounds for the star-discrepancy of negatively dependent random point sets and its expectation. We apply our findings also to the weighted star-discrepancy.

arXiv commentAccepted for publication in Mathematics of Computation

References in corpus (9)

• Calculation of Discrepancy Measures and Applications
• A Lower Bound for the Discrepancy of a Random Point Set
• Critical Hyper-Parameters: No Random, No Cry
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• On Negatively Dependent Sampling Schemes, Variance Reduction, and Probabilistic Upper Discrepancy Bounds
• A Sharp Discrepancy Bound for Jittered Sampling
• Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples
• Note on Pairwise Negative Dependence of Randomized Rank-1 Lattices
• A two-sided Faulhaber-like formula involving Bernoulli polynomials

Cited by in corpus (1)

• On a partition with a lower expected ${\mathcal{L}}_2$-discrepancy than classical jittered sampling