Jittered sampling and probability measures

Abstract

This paper investigates the discrepancy of a family of random sampling methods obtained by perturbing the grid $\frac{1}{M}{\mathbb{Z}}^d\cap {\left[-1/2,1/2\right)}^d$, where $M$ is a large positive integer. Parameterized by an arbitrary probability measure $\hat{I}¼$, this family encompasses several classical methods for evaluating the quality of an $N$-point set in ${\mathbb{T}}^d$, where $N=M^d$. We show that all probability measures, except for Dirac measures, behave like the Lebesgue measure in the Monte Carlo discrepancy. This represents a limiting case where the measure $\hat{I}¼$ depends on $M$. In this latter context, we prove that, up to a constant, the lowest possible discrepancy is achieved when the support of $\hat{I}¼$ has diameter $\le c/M$, and that this upper bound is sharp.