TY - JOUR
T1 - Discrepancy of stratified samples from partitions of the unit cube
AU - Kiderlen, Markus
AU - Pausinger, Florian
N1 - Publisher Copyright:
© 2021, The Author(s).
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2021/6
Y1 - 2021/6
N2 - 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 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 Lp-discrepancy, ELp(PΩ)p, of a point set PΩ generated from any equivolume partition Ω is always strictly smaller than the expected Lp-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 Lp-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.
AB - 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 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 Lp-discrepancy, ELp(PΩ)p, of a point set PΩ generated from any equivolume partition Ω is always strictly smaller than the expected Lp-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 Lp-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.
KW - Jittered sampling
KW - L-discrepancy
KW - Sets of positive reach
KW - Stratified sampling
UR - http://www.scopus.com/inward/record.url?scp=85102285947&partnerID=8YFLogxK
U2 - 10.1007/s00605-021-01538-4
DO - 10.1007/s00605-021-01538-4
M3 - Journal article
AN - SCOPUS:85102285947
SN - 0026-9255
VL - 195
SP - 267
EP - 306
JO - Monatshefte fur Mathematik
JF - Monatshefte fur Mathematik
IS - 2
ER -