A SHARP DISCREPANCY BOUND FOR JITTERED SAMPLING

For m, d ∈ N, a jittered (or stratified) sampling point set P having N = m^d points in [0, 1)d is constructed by partitioning the unit cube [0, 1)^d into md 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 c > 0 and C such that for all d and all m ≥ d the expected non-normalized star discrepancy of a jittered sampling point set satisfies (Formula Presented) This discrepancy is thus smaller by a factor of (Formula Presented) than the one of a uniformly distributed random point set (Monte Carlo point set) of cardinality m^d. This result improves both the upper and the lower bound for the discrepancy of jittered sampling given by Pausinger and Steinerberger [J. Complexity 33 (2016), pp. 199–216]. It also removes the asymptotic requirement that m is sufficiently large compared to d.