On the discrepancy of jittered sampling

F. Pausinger, S. Steinerberger, Journal of Complexity 33 (2016) 199–216.


Journal Article | Published | English
Author
;
Department
Abstract
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.
Publishing Year
Date Published
2016-04-01
Journal Title
Journal of Complexity
Acknowledgement
We are grateful to the referee whose suggestions greatly improved the quality and clarity of the exposition.
Volume
33
Page
199 - 216
IST-REx-ID

Cite this

Pausinger F, Steinerberger S. On the discrepancy of jittered sampling. Journal of Complexity. 2016;33:199-216. doi:10.1016/j.jco.2015.11.003
Pausinger, F., & Steinerberger, S. (2016). On the discrepancy of jittered sampling. Journal of Complexity, 33, 199–216. https://doi.org/10.1016/j.jco.2015.11.003
Pausinger, Florian, and Stefan Steinerberger. “On the Discrepancy of Jittered Sampling.” Journal of Complexity 33 (2016): 199–216. https://doi.org/10.1016/j.jco.2015.11.003.
F. Pausinger and S. Steinerberger, “On the discrepancy of jittered sampling,” Journal of Complexity, vol. 33, pp. 199–216, 2016.
Pausinger F, Steinerberger S. 2016. On the discrepancy of jittered sampling. Journal of Complexity. 33, 199–216.
Pausinger, Florian, and Stefan Steinerberger. “On the Discrepancy of Jittered Sampling.” Journal of Complexity, vol. 33, Academic Press, 2016, pp. 199–216, doi:10.1016/j.jco.2015.11.003.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar