Aarhus University Seal / Aarhus Universitets segl

Discrepancy of stratified samples from partitions of the unit cube

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

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
Pages (from-to)267-306
Number of pages40
Publication statusPublished - Jun 2021

Bibliographical note

Publisher Copyright:
© 2021, The Author(s).

Copyright 2021 Elsevier B.V., All rights reserved.

    Research areas

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

See relations at Aarhus University Citationformats

ID: 219073584