Discrepancy of stratified samples from partitions of the unit cube

2020/08/27 by Kiderlen, Markus, Pausinger, Florian · 2 citations
#11K38 #FOS: Mathematics #Number Theory (math.NT) #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2008.12026

Abstract

We extend the notion of jittered sampling to arbitrary partitions and study the discrepancy of the related point sets. Let \mathbfΩ=(Ω₁,…,Ω_N) be a partition of [0,1]^d and let the ith point in P 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 L_p-discrepancy, 𝔼 L_p(P_\mathbfΩ)^p, of a point set P_\mathbfΩ generated from any equivolume partition \mathbfΩ is always strictly smaller than the expected L_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 L_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.

Cited by

• On a Class of Partitions with Lower Expected Star Discrepancy and Its Upper Bound than Jittered Sampling
• Expected star discrepancy based on stratified sampling

Related

• On a partition with a lower expected \L₂-discrepancy than\n classical jittered sampling
• Partitions for stratified sampling
• On the expected L2-discrepancy of jittered sampling
• Expected L₂-discrepancy bound for a class of new stratified sampling models
• Star discrepancy for new stratified random sampling I: optimal expected star discrepancy