On the Expected ℒ2-Discrepancy of Stratified Samples from Parallel Lines

Pausinger, Florian

doi:10.2478/udt-2023-0012

Abstract

We study the expected ℒ₂-discrepancy of stratified samples generated from special equi-volume partitions of the unit square. The partitions are defined via parallel lines that are all orthogonal to the diagonal of the square. It is shown that the expected discrepancy of stratified samples derived from these partitions is a factor 2 smaller than the expected discrepancy of the same number of i.i.d uniformly distributed random points in the unit square. We conjecture that this is best possible among all partitions generated from parallel lines.

References

AISTLEITNER, C.: Covering numbers, dyadic chaining and discrepancy,J. Complexity 27 (2011), 531–540.
Search in Google Scholar Back to article
APOSTOL, T. M.: An Elementary View of Euler’s Summation Formula,Amer. Math. Monthly 106 (1999), no. 5, 409–418.
Search in Google Scholar Back to article
CHEN, W. W. L.—SKRIGANOV, M. M.: Explicit constructions in the classical mean squares problem in irregularity of point distribution,J.Reine Angew. Math. 545 (2002), 67–95.
Search in Google Scholar Back to article
CHO, Y.—KIM, S.: Volume of Hypercubes Clipped by Hyperplanes and Combinatorial Identities, Electronic J. Linear Algebra 36 (2020), 228–255.
Search in Google Scholar Back to article
DAVENPORT, H.: Note on irregularities of distribution,Mathematika 3 (1956), 131–135.
Search in Google Scholar Back to article
DICK, J.—PILLICHSHAMMER, F.: Digital Nets and Sequences. Cambridge University Press, Cambridge, 2010.
Search in Google Scholar Back to article
DICK, J.—PILLICHSHAMMER, F.: Explicit constructions of point sets and sequences with low discrepancy,In:Uniform distribution and quasi-Monte Carlo methods, Radon Ser. Comput. Appl. Math. Vol. 15, De Gruyter, Berlin, 2014. pp. 63–86.
Search in Google Scholar Back to article
DICK, J.—PILLICHSHAMMER, F.: Optimal ℒ₂-discrepancy bounds for higher order digital sequences over the finite field 𝔽₂,Acta Arith. 162, (2014) no. 1, 65–99.
Search in Google Scholar Back to article
DOERR, B.: A lower bound for the discrepancy of a random point set,J. Complexity 30 (2014), 16–20.
Search in Google Scholar Back to article
GNEWUCH, M.—PASING, H.—WEISS, C.: A generalized Faulhaber inequality, improved bracketing covers and applications to discrepancy, Math. Comput 90 (2021), no. 332, 2873–2898.
Search in Google Scholar Back to article
HEINRICH, S.—NOVAK, E.—WASILKOWSKI, G.—WOZNIAKOWSKI, H.: The inverse of the star-discrepancy depends linearly on the dimension,Acta Arith. 96 (2001), no. 3, 279–302.
Search in Google Scholar Back to article
KIDERLEN, M.—PAUSINGER, F.: Discrepancy of stratified samples from partitions of the unit cube, Monatsh. Math. 195 (2022), 267–306.
Search in Google Scholar Back to article
KIRK, N.: Several Problems in Discrepancy Theory: Lower Bounds and Stratified Sampling, PhD Thesis, Queen’s University Belfast, 2023.
Search in Google Scholar Back to article
KIRK, N.—PAUSINGER, F.: On the expected ℒ₂-discrepancy of jittered sampling,Unif. Distrib. Theory 18 (2023), no. 1, 65–82.
Search in Google Scholar Back to article
KIDERLEN, M.—PAUSINGER, F.: On a partition with a lower expected ℒ₂−discrepancy than classical jittered sampling,J. Complexity 70 (2022), Article ID 101616, 13 pp.
Search in Google Scholar Back to article
ROTH,K.F.: On irregularities of distribution,Mathematika 1 (1954), 73–79.
Search in Google Scholar Back to article

On the Expected ℒ2-Discrepancy of Stratified Samples from Parallel Lines

Abstract

Paradigm

My account