Discrepancy of stratified samples from partitions of the unit cube

Markus Kiderlen, Florian Pausinger*

*Corresponding author for this work

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

4 Citations (Scopus)
28 Downloads (Pure)

Abstract

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.

Original languageEnglish
JournalMonatshefte fur Mathematik
Volume195
Issue2
Pages (from-to)267-306
Number of pages40
ISSN0026-9255
DOIs
Publication statusPublished - Jun 2021

Keywords

  • Jittered sampling
  • L-discrepancy
  • Sets of positive reach
  • Stratified sampling

Fingerprint

Dive into the research topics of 'Discrepancy of stratified samples from partitions of the unit cube'. Together they form a unique fingerprint.

Cite this