Discrepancy of stratified samples from partitions of the unit cube
share
We extend the notion of jittered sampling to arbitrary partitions and study the discrepancy of the related point sets. Let 𝐎𝐦𝐞𝐠𝐚=(Ω_1,…,Ω_N) be a partition of [0,1]^d and let the ith point in 𝒫 be chosen uniformly in the ith set of the partition (and stochastically independent of the other points), i=1,…,N. For the study of such sets we introduce the concept of a uniformly distributed triangular array and compare this notion to related notions in the literature. We prove that the expected ℒ_p-discrepancy, 𝔼ℒ_p(𝒫_𝐎𝐦𝐞𝐠𝐚)^p, of a point set 𝒫_𝐎𝐦𝐞𝐠𝐚 generated from any equivolume partition 𝐎𝐦𝐞𝐠𝐚 is always strictly smaller than the expected ℒ_p-discrepancy of a set of N uniform random samples for p>1. For fixed N we consider classes of stratified samples based on equivolume partitions of the unit cube into convex sets or into sets with a uniform positive lower bound on their reach. It is shown that these classes contain at least one minimizer of the expected ℒ_p-discrepancy. We illustrate our results with explicit constructions for small N. In addition, we present a family of partitions that seems to improve the expected discrepancy of Monte Carlo sampling by a factor of 2 for every N.
READ FULL TEXT