On the discrepancy of jittered sampling

DOI10.1016/J.JCO.2015.11.003MaRDI QIDQ5963459zbMATH OpenOpenAlexFDO

Authors Florian Pausinger, Stefan Steinerberger

Publication date 19 February 2016

Published in Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

\(L^2\)-discrepancyinverse of the star discrepancyjittered samplingstar discrepancy

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Partitions of sets (05A18) Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D99)

Abstract: We study the discrepancy of jittered sampling sets: such a set $mathcalPsubset[0,1{]}^d$ is generated for fixed $minmathbbN$ by partitioning $[0,1{]}^d$ into $m^d$ axis aligned cubes of equal measure and placing a random point inside each of the $N=m^d$ cubes. We prove that, for $N$ sufficiently large, ${\displaystyle }$ frac{1}{10}frac{d}{N^{frac{1}{2} + frac{1}{2d}}} leq mathbb{E} D_N^*(mathcal{P}) leq frac{sqrt{d} (log{N})^{frac{1}{2}}}{N^{frac{1}{2} + frac{1}{2d}}},${\displaystyle }$ where the upper bound with an unspecified constant $C_d$ was proven earlier by Beck. Our proof makes crucial use of the sharp Dvoretzky-Kiefer-Wolfowitz inequality and a suitably taylored Bernstein inequality; we have reasons to believe that the upper bound has the sharp scaling in $N$. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime $Ngtrsim{d}^d$. We also prove a partition principle showing that every partition of $[0,1{]}^d$ combined with a jittered sampling construction gives rise to a set whose expected squared $L^2-$discrepancy is smaller than that of purely random points.

Recommendations

• A sharp discrepancy bound for jittered sampling
• Optimal jittered sampling for two points in the unit square
• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• A lower bound for the discrepancy of a random point set
• Discrepancy of stratified samples from partitions of the unit cube

Cites work

• A lower bound for the discrepancy of a random point set
• An approximation of partial sums of independent RV'-s, and the sample DF. I
• An approximation of partial sums of independent RV's, and the sample DF. II
• Area Estimation by Point-Counting Techniques
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Calculation of discrepancy measures and applications
• Covering numbers, dyadic chaining and discrepancy
• Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
• Deterministic and probabilistic discrepancies
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 4000052 (Why is no real title available?)
• scientific article; zbMATH DE number 2233281 (Why is no real title available?)
• Irregularities of distribution. I
• Point sets and sequences with small discrepancy
• Sur la distribution limite du terme maximum d'une série aléatoire
• The asymptotic behavior of the average L^p-discrepancies and a randomized discrepancy
• The inverse of the star-discrepancy depends linearly on the dimension
• The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators

Cited in

(17)

• Optimal jittered sampling for two points in the unit square
• Bounds for the traveling salesman paths of two-dimensional modular lattices
• Discrepancy of stratified samples from partitions of the unit cube
• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• scientific article; zbMATH DE number 3170753 (Why is no real title available?)
• Asymptotic Analysis of Multidimensional Jittered Sampling
• Analysis of Signal Reconstruction With Jittered Sampling
• A sharp discrepancy bound for jittered sampling
• One-bit sensing, discrepancy and Stolarsky's principle
• On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling
• Expected integration approximation under general equal measure partition
• Partitions for stratified sampling
• Upper bound estimation of star discrepancy based on Hilbert space filling curve stratified sampling and its applications
• Regularizing random points by deleting a few
• Discrepancy and approximation of absolutely continuous measures with atomic measures
• Probabilistic weighted star discrepancy bound based on the general equal measure partition
• Separation properties of scrambled digital nets and related random point sets

This page was built for publication: On the discrepancy of jittered sampling

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