A sharp discrepancy bound for jittered sampling

Source abstract

For m , d ∈ N m, d \in {\mathbb N} , a jittered (or stratified) sampling point set P P having N = m d N = m^d points in [ 0 , 1 ) d [0,1)^d is constructed by partitioning the unit cube [ 0 , 1 ) d [0,1)^d into m d 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 c > 0 c > 0 and C C such that for all d d and all m ≥ d m \ge d the expected non-normalized star discrepancy of a jittered sampling point set satisfies $$c d m d − 1 2 1 + log ⁡ ( m d ) ≤ E D ∗ ( P ) ≤ C d m d − 1 2 1 + log ⁡ ( m d ) . c \,dm^{\frac {d-1}{2}} \sqrt {1 + \log (\tfrac md)} \le {\mathbb E} D^*(P) \le C\, dm^{\frac {d-1}{2}} \sqrt {1 + \log (\tfrac md)}.$$ This discrepancy is thus smaller by a factor of Θ ( ( 1 + log ⁡ ( m / d ) m / d ) 1 / 2 ) \Theta \big (\big (\frac {1+\log (m/d)}{m/d}\big )^{1/2}\big ) than the one of a uniformly distributed random point set (Monte Carlo point set) of cardinality m d 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 m is sufficiently large compared to d d .