A sharp discrepancy bound for jittered sampling

DOI10.1090/MCOM/3727MaRDI QIDQ5082039zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr

Publication date 15 June 2022

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

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

zbMATH Keywords

star discrepancystratified sampling

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Monte Carlo methods (65C05)

Abstract: For $m,dinmathbbN$, a jittered sampling point set $P$ having $N=m^d$ points in $[0,1{)}^d$ is constructed by partitioning the unit cube $[0,1{)}^d$ into $m^d$ axis-aligned cubes of equal size and then placing one point independently and uniformly at random in each cube. We show that there are constants $cge0$ and $C$ such that for all $d$ and all $mged$ the expected non-normalized star discrepancy of a jittered sampling point set satisfies [c ,dm^{frac{d-1}{2}} sqrt{1 + log( frac md)} le {mathbb E} D^*(P) le C, dm^{frac{d-1}{2}} sqrt{1 + log( frac md)}.] This discrepancy is thus smaller by a factor of $$ than the one of a uniformly distributed random point set of $m^d$ points. This result improves both the upper and the lower bound for the discrepancy of jittered sampling given by Pausinger and Steinerberger (Journal of Complexity (2016)). It also removes the asymptotic requirement that $m$ is sufficiently large compared to $d$.

Recommendations

• On the discrepancy of jittered sampling
• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• Discrepancy of stratified samples from partitions of the unit cube
• Discrepancy, integration and tractability
• Optimal jittered sampling for two points in the unit square

Cites work

• A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code
• A lower bound for the discrepancy of a random point set
• A quasi-Monte Carlo Metropolis algorithm
• A Remark on Stirling's Formula
• Area Estimation by Point-Counting Techniques
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Covering numbers, dyadic chaining and discrepancy
• Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
• Entropy, Randomization, Derandomization, and Discrepancy
• Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
• Geometric discrepancy. An illustrated guide
• 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 735224 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3042316 (Why is no real title available?)
• Irregularities of distribution. I
• On negatively dependent sampling schemes, variance reduction, and probabilistic upper discrepancy bounds
• On the discrepancy of jittered sampling
• Probabilistic discrepancy bound for Monte Carlo point sets
• Probabilistic lower bounds for the discrepancy of Latin hypercube samples
• Quasi-Monte Carlo feature maps for shift-invariant kernels
• Sequences, discrepancies and applications
• The inverse of the star-discrepancy depends linearly on the dimension
• The supremum norm of the discrepancy function: recent results and connections

Cited in

(12)

• Optimal jittered sampling for two points in the unit square
• 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
• Asymptotic Analysis of Multidimensional Jittered Sampling
• On the discrepancy of jittered sampling
• The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\)
• On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling
• Partitions for stratified sampling
• Upper bound estimation of star discrepancy based on Hilbert space filling curve stratified sampling and its applications
• Discrepancy and approximation of absolutely continuous measures with atomic measures
• Probabilistic weighted star discrepancy bound based on the general equal measure partition
• The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension

This page was built for publication: A sharp discrepancy bound for jittered sampling

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