Bounds and constructions for the star-discrepancy via -covers
The (\(L^{\infty}\)-) star-discrepancy is a well known measure for the irregularity of distribution of \(n\) points in the \(d\)-dimensional unit cube. In addition, for certain classes of functions, point sets with small star discrepancy yield cubature formulas with low error of multivariate integration. Many of the known bounds on the star discrepancy of well-chosen point sets of size \(n\) are of the form \(C_d (\log n)^{d-1} n^{-1}\), which is not very helpful for large \(d\) since the number of points \(n\) needs to be extremely high if one wants to obtain small star discrepancy. For this reason, it is of great interest to find bounds on the discrepancy which depend only polynomially on \(d\). By the use of so-called \(\delta\)-covers, which are certain finite sets of points in the unit cube \([0,1]^d\), and a probabilistic argument, the authors show the existence of point sets of size \(n\) in \([0,1]^d\) such that their discrepancy is bounded by \(Cd^{1/2}n^{-1/2}(\log n)^{1/2}\), where \(C\) is a constant (independent of \(d\) and \(n\)). One of the main tools in the proof of this result is Hoeffding's inequality. Furthermore, the paper contains an algorithm for the construction of such point sets by a derandomization of the probabilistic argument.
- Entropy, Randomization, Derandomization, and Discrepancy
- The inverse of the star-discrepancy depends linearly on the dimension
- Computing bounds for the star discrepancy
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
- Probabilistic discrepancy bound for Monte Carlo point sets
- Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
- Convergence of stochastic processes
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
- Geometric discrepancy. An illustrated guide
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 53679 (Why is no real title available?)
- scientific article; zbMATH DE number 1857654 (Why is no real title available?)
- scientific article; zbMATH DE number 852056 (Why is no real title available?)
- Improved algorithms via approximations of probability distributions
- On the tractability of multivariate integration and approximation by neural networks
- On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Sequences, discrepancies and applications
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Some open problems concerning the star-discrepancy
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- The inverse of the star-discrepancy depends linearly on the dimension
- Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
- An algorithm to compute bounds for the star discrepancy
- Computing bounds for the star discrepancy
- Tractability properties of the weighted star discrepancy of the Halton sequence
- Secure pseudorandom bit generators and point sets with low star-discrepancy
- Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
- On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
- A nonlocal functional promoting low-discrepancy point sets
- Theory of generalized discrepancies on a ball of arbitrary finite dimensions and algorithms for finding low-discrepancy point sets
- Minimizing the \(L_{2}\) and \(L_{\infty}\) star discrepancies of a single point in the unit hypercube
- A note on the existence of sequences with small star discrepancy
- Tractability properties of the weighted star discrepancy
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
- A new randomized algorithm to approximate the star discrepancy based on threshold accepting
- The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
- Discrepancy estimates for acceptance-rejection samplers using stratified inputs
- A best possible upper bound on the star discrepancy of (t, m, 2)-nets
- The weighted star discrepancy of Korobov’s p-sets
- Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding
- Component-by-component construction of low-discrepancy point sets of small size
- The inverse of the star-discrepancy depends linearly on the dimension
- Irregularities of distributions and extremal sets in combinatorial complexity theory
- A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
- A sharp discrepancy bound for jittered sampling
- Metrical star discrepancy bounds for lacunary subsequences of digital Kronecker-sequences and polynomial tractability
- Discrepancy theory and quasi-Monte Carlo integration
- Calculation of discrepancy measures and applications
- Entropy, Randomization, Derandomization, and Discrepancy
- Probabilistic discrepancy bound for Monte Carlo point sets
- Low-discrepancy point sets for non-uniform measures
- Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- A Metropolis random walk algorithm to estimate a lower bound of the star discrepancy
- Covering numbers, dyadic chaining and discrepancy
- Upper bound estimation of star discrepancy based on Hilbert space filling curve stratified sampling and its applications
- Hammersley point sets and inverse of star-discrepancy
- Constructing optimal star discrepancy sets
- Probabilistic weighted star discrepancy bound based on the general equal measure partition
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- The star discrepancy of a union of randomly shifted Korobov lattice point sets depends polynomially on the dimension
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
This page was built for publication: Bounds and constructions for the star-discrepancy via \(\delta\)-covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2576276)
