Discrepancy of stratified samples from partitions of the unit cube

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\)-discrepancy expected discrepancy jittered sampling Monte Carlo method sets of positive reach stratified 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

m a t h b f O m e g a = (O m e g a_{1}, l d o t s, O m e g a_{N})

be a partition of

[0, 1]^{d}

and let the

i

th point in

m a t h c a l P

be chosen uniformly in the

i

th set of the partition (and stochastically independent of the other points),

i = 1, l d o t s, 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

m a t h c a l L_{p}

-discrepancy,

m a t h b b E m a t h c a l L_{p} (m a t h c a l P_{m a t h b f O m e g a})^{p}

, of a point set

m a t h c a l P_{m} a t h b f O m e g a

generated from any equivolume partition

m a t h b f O m e g a

is always strictly smaller than the expected

m a t h c a l 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

m a t h c a l 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

.

Review text

Jittered sampling is a classical variance reduction method in Monte Carlo simulation. Rather than sampling a certain number of random elements from the whole space, the space is first partitioned into as many parts as the desired number of sampling points, and then one point is randomly picked from each of these parts. The classical setting for this is random sampling from the \(d\)-dimensional unit cube, with the partition coming from a regular grid. In the present paper, the author study general jittered sampling, where the sets in the partition are not assumed to satisfy any structural properties, or only weak properties such as convexity (rather than being all congruent boxes, as in classical jittered sampling). They compare the quality of different systems of partitions, which they quantify in terms of the expected \(L^p\) discrepancy of the jittered sampling points, and give a partial answer to the problem which partition minimizes this expected discrepancy (for a given cardinality of the point set).

Recommendations

Cites work

Cited in

(10)

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)