Discrepancy of stratified samples from partitions of the unit cube

DOI10.1007/S00605-021-01538-4MaRDI QIDQ2031030zbMATH OpenOpenAlexFDO

Authors Markus Kiderlen, Florian Pausinger

Publication date 8 June 2021

Published in Monatshefte für Mathematik (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2008.12026, https://pureadmin.qub.ac.uk/ws/files/232836411/Kiderlen_Pausinger2021_Article_DiscrepancyOfStratifiedSamples.pdf

zbMATH Keywords

\(L^p\)-discrepancyexpected discrepancyjittered samplingMonte Carlo methodsets of positive reachstratified sampling

Mathematics Subject Classification ID

Partitions of sets (05A18) Irregularities of distribution, discrepancy (11K38) Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D99)

Abstract: We extend the notion of jittered sampling to arbitrary partitions and study the discrepancy of the related point sets. Let $mathbfOmega=(Omeg{a}_1,ldots,Omeg{a}_N)$ be a partition of $[0,1{]}^d$ and let the $i$th point in $mathcalP$ be chosen uniformly in the $i$th set of the partition (and stochastically independent of the other points), $i=1,ldots,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 $mathcal{L}_p$-discrepancy, $mathbbEmathcal{L}_p(mathcal{P}_{mathbfOmega}{)}^p$, of a point set $mathcal{P}_{m}athbfOmega$ generated from any equivolume partition $mathbfOmega$ is always strictly smaller than the expected $mathcal{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 $mathcal{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$.

Recommendations

• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• On the discrepancy of jittered sampling
• A sharp discrepancy bound for jittered sampling
• Optimal jittered sampling for two points in the unit square
• Statistical properties of generalized discrepancies

Cites work

• 50 years sets with positive reach -- a survey
• \(\lambda\)-equidistributed sequences of partitions and a theorem of the De Bruijn-Post type
• A generalization of Kakutani's splitting procedure
• A lower bound for the discrepancy of a random point set
• A Modified Monte-Carlo Quadrature
• An inequality for differences of distribution functions
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Calculation of discrepancy measures and applications
• Computing discrepancies of Smolyak quadrature rules
• Covering numbers, dyadic chaining and discrepancy
• Curvature Measures
• Efficient algorithms for computing the L₂-discrepancy
• Explicit constructions in the classical mean squares problem in irregularities of point distribution
• Explicit constructions of point sets and sequences with low discrepancy
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3565828 (Why is no real title available?)
• scientific article; zbMATH DE number 3393648 (Why is no real title available?)
• Monte Carlo Variance of Scrambled Net Quadrature
• Note on irregularities of distribution
• On irregularities of distribution
• On the discrepancy of jittered sampling
• On the Distribution of the Number of Successes in Independent Trials
• On the strong law for arrays and for the bootstrap mean and variance
• Optimal \(\mathcal {L}_{2}\) discrepancy bounds for higher order digital sequences over the finite field \(\mathbb {F}_{2}\)
• Optimal jittered sampling for two points in the unit square
• Probability theory. A comprehensive course
• Randomization of Number Theoretic Methods for Multiple Integration
• Randomized quasi-Monte Carlo: an introduction for practitioners
• Sampling
• Scrambled net variance for integrals of smooth functions
• The distribution of leading digits and uniform distribution mod 1
• The inverse of the star-discrepancy depends linearly on the dimension
• Variance reduction via lattice rules
• Variance with alternative scramblings of digital nets
• Weak convergence results for the Kakutani interval splitting procedure.

Cited in

(10)

• Optimal jittered sampling for two points in the unit square
• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• scientific article; zbMATH DE number 912595 (Why is no real title available?)
• A sharp discrepancy bound for jittered sampling
• On the discrepancy of jittered sampling
• On the expected \(\mathcal{L}_2\)-discrepancy of jittered sampling
• Expected integration approximation under general equal measure partition
• Partitions for stratified sampling
• Improved expected L₂-discrepancy formulas on jittered sampling
• On the expected \(\mathcal{L}_2\)-discrepancy of stratified samples from parallel lines

This page was built for publication: Discrepancy of stratified samples from partitions of the unit cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2031030)