On the discrepancy of jittered sampling

Florian Pausinger, Stefan Steinerberger*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


We study the discrepancy of jittered sampling sets: such a set P⊂ [0,1]d is generated for fixed m∈ℕ by partitioning [0,1]d into md axis aligned cubes of equal measure and placing a random point inside each of the N=md cubes. We prove that, for N sufficiently large, 1/10 d/N1/2+1/2d ≤EDN∗(P)≤ √d(log N) 1/2/N1/2+1/2d, where the upper bound with an unspecified constant Cd 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 N≳dd. 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 L2-discrepancy is smaller than that of purely random points.

Original languageEnglish
Pages (from-to)199-216
Number of pages18
JournalJournal of Complexity
Early online date17 Nov 2015
Publication statusPublished - Apr 2016


  • Inverse of the star discrepancy
  • Jittered sampling
  • L-discrepancy
  • Star discrepancy

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'On the discrepancy of jittered sampling'. Together they form a unique fingerprint.

Cite this