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

DOI10.1090/MCOM/3666zbMATH Open1485.11118arXiv2010.11479OpenAlexW3159303325MaRDI QIDQ4956929FDOQ4956929

Authors: Michael Gnewuch, Hendrik Pasing, Christian Weiß 

Publication date: 2 September 2021

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

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.

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

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

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)

Cites Work

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

Cited In (6)

• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• An elementary proof of a lower bound for the inverse of the star discrepancy
• Construction of minimal bracketing covers for rectangles
• The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\)
• 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)