A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy

DOI10.1090/MCOM/3666MaRDI QIDQ4956929zbMATH OpenOpenAlexFDO

Authors Michael Gnewuch, Hendrik Pasing, Christian Weiß

Publication date 2 September 2021

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.11479

zbMATH Keywords

negative correlationcovering numbertractabilitysums of powersbracketing numberFaulhaber's formulastar-discrepancyweighted star-discrepancyMonte Carlo point setspre-asymptotic bound

Mathematics Subject Classification ID

Estimates on exponential sums (11L07) Inequalities for sums, series and integrals (26D15) Pseudo-random numbers; Monte Carlo methods (11K45) Probabilistic theory: distribution modulo (1); metric theory of algorithms (11K99)

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.

Recommendations

• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Covering numbers, dyadic chaining and discrepancy
• The inverse of the star-discrepancy depends linearly on the dimension
• scientific article; zbMATH DE number 3946256
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy

Cites work

• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1999206 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 822320 (Why is no real title available?)
• A lower bound for the discrepancy of a random point set
• A note on the existence of sequences with small star discrepancy
• A two-sided Faulhaber-like formula involving Bernoulli polynomials
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• An algorithm to compute bounds for the star discrepancy
• An aspect of optimal regression design for LSMC
• An upper bound of the minimal dispersion via delta covers
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Calculation of discrepancy measures and applications
• Component-by-component construction of low-discrepancy point sets of small size
• Construction of minimal bracketing covers for rectangles
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Covering numbers, dyadic chaining and discrepancy
• Entropy, Randomization, Derandomization, and Discrepancy
• Expected dispersion of uniformly distributed points
• Implementation of a component-by-component algorithm to generate small low-discrepancy samples
• Improving a constant in high-dimensional discrepancy estimates
• Irregularities of distribution, VII
• Johann Faulhaber and Sums of Powers
• Metrical star discrepancy bounds for lacunary subsequences of digital Kronecker-sequences and polynomial tractability
• Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Multilevel quasi-Monte Carlo path simulation
• Negative dependence, scrambled nets, and variance bounds
• Note on pairwise negative dependence of randomly shifted and jittered rank-1 lattices
• On negatively dependent sampling schemes, variance reduction, and probabilistic upper discrepancy bounds
• On the inverse of the discrepancy for infinite dimensional infinite sequences
• On the small ball inequality in all dimensions
• On the small ball inequality in three dimensions
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Probabilistic discrepancy bound for Monte Carlo point sets
• Probabilistic lower bounds for the discrepancy of Latin hypercube samples
• Probabilistic star discrepancy bounds for double infinite random matrices
• Randomization of Number Theoretic Methods for Multiple Integration
• Randomized quasi-Monte Carlo: an introduction for practitioners
• Secure pseudorandom bit generators and point sets with low star-discrepancy
• The inverse of the star-discrepancy depends linearly on the dimension
• Tractability properties of the weighted star discrepancy
• Tractability results for the weighted star-discrepancy
• Weak convergence and empirical processes. With applications to statistics
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cited in

(6)

• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• An elementary proof of a lower bound for the inverse of the star discrepancy
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\)
• Construction of minimal bracketing covers for rectangles
• Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy

This page was built for publication: A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956929)