On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling (Q6169854)

The paper studies the \(L_2\) discrepancy of point sets obtained from jittered sampling. Jittered sampling is a simple yet effective idea to obtain \(N=m^d\) points, where \(m\) and \(d\) are positive integers, in the unit cube \([0,1]^d\) with reasonably uniform distribution. In this context, one divides the unit cube into \(m^d\) equally sized axes-aligned cubes, and places one random point in each of these cubes. Each of the points is chosen according to a uniform distribution on the respective sub-cube, and the points are all independently distributed. Thus, point sets obtained from jittered sampling are on the one hand highly structured, and on the other hand also feature a certain extent of randomness which is sometimes helpful when using the points for applications. Indeed, when using the points in an equal-weight quadrature rule, one can consider jittered sampling as a special case of randomized quasi-Monte Carlo methods. It is of interest to quantify the extent of uniform distribution of the point sets in jittered sampling, and one way to do this is to study their \(L_2\) discrepancy. For a point set \(P_N\) with \(N\) points in \([0,1]^d\), its \(L_2\)-discrepancy is defined as \[ L_2 (P_N):=\left(\int_{[0,1]^d} \left(\frac{|P \cap [\boldsymbol{0},\boldsymbol{x})|}{N}-\lambda_d ([\boldsymbol{0},\boldsymbol{x}))\right)^2 \mathrm{d}\boldsymbol{x}\right)^{1/2}, \] where \([\boldsymbol{0},\boldsymbol{x})\) denotes the axes-parallel half-open box with lower left corner in \(\boldsymbol{0}\) and upper left corner in \(\boldsymbol{x}\), where \(|P \cap [\boldsymbol{0},\boldsymbol{x})|\) denotes the number of points of \(P\) in \([\boldsymbol{0},\boldsymbol{x})\), and where \(\lambda_d\) denotes the \(d\)-dimensional Lebesgue measure. The main result of the paper shows an exact formula for the expected value of the \(L_2\) discrepancy of \(N=m^d\) points obtained from jittered sampling, namely \[ \mathbb{E} \left[ (L_2 (P))^2\right]=\frac{1}{m^{2d}}\left(\left(\frac{m}{2}\right)^d - \left(\frac{m}{2}-\frac{1}{6}\right)^d\right), \] and, as a consequence, \(\mathbb{E} \left[L_2 (P)\right]=\mathcal{O}\left(m^{-(d+1)/2}\right)\). Furthermore, results of a similar flavor are shown for a modified version of the \(L_2\) discrepancy due to Hickernell.