On the discrepancy of low-dimensional probability measures
Author:
Christian Weiss
Journal:
Theor. Probability and Math. Statist. 111 (2024), 199-209
MSC (2020):
Primary 60B10, 28A12, 11K38, 11J71
DOI:
https://doi.org/10.1090/tpms/1223
Published electronically:
October 30, 2024
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: Calculating the star-discrepancy of a point set in the $d$-dimensional unit cube with respect to the Lebesgue measure is an NP-hard problem. Still explicit formulas, which allow for an easy implementation, have been derived. These formulas are particularly compact in the case of dimensions $d=1,2$ by the work of Niederreiter, and Bundschuh and Zhu. In this paper, we generalize their formulas to arbitrary measures in the dimension $d=1$ and to a wide class of measures in the dimension $d=2$. In order to give a potential application of such formulas, we reprove from it the fact that the Lebesgue measure is the hardest measure to approximate in the dimension $d=1$.
References
- Christoph Aistleitner, Dmitriy Bilyk, and Aleksandar Nikolov, Tusnády’s problem, the transference principle, and non-uniform QMC sampling, Monte Carlo and quasi–Monte Carlo methods, Springer Proc. Math. Stat., vol. 241, Springer, Cham, 2018, pp. 169–180. MR 3828139, DOI 10.1007/978-3-319-91436-7_{8}
- P. Bundschuh and Y. Zhu, A method for exact calculation of the discrepancy of low-dimensional finite point sets. I, Abh. Math. Sem. Univ. Hamburg 63 (1993), 115–133. MR 1227869, DOI 10.1007/BF02941337
- L. de Clerck, A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley, Monatsh. Math. 101 (1986), no. 4, 261–278. MR 851948, DOI 10.1007/BF01559390
- D. P. Dobkin, D. Eppstein, and D. P. Mitchell, Computing the discrepancy with applications to supersampling patterns, ACM Trans. Graph. 15 (1996), 354–376.
- Samantha Fairchild, Max Goering, and Christian Weiss, Families of well approximable measures, Unif. Distrib. Theory 16 (2021), no. 1, 53–70. MR 4311860, DOI 10.2478/udt-2021-0003
- Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner, Hardness of discrepancy computation and $\epsilon$-net verification in high dimension, J. Complexity 28 (2012), no. 2, 162–176. MR 2900826, DOI 10.1016/j.jco.2011.09.001
- Michael Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity 24 (2008), no. 2, 154–172. MR 2400314, DOI 10.1016/j.jco.2007.08.003
- Michael Gnewuch, Anand Srivastav, and Carola Winzen, Finding optimal volume subintervals with $k$-points and calculating the star discrepancy are NP-hard problems, J. Complexity 25 (2009), no. 2, 115–127. MR 2513611, DOI 10.1016/j.jco.2008.10.001
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 419394
- H. Niederreiter, Discrepancy and convex programming, Ann. Mat. Pura Appl. (4) 93 (1972), 89–97. MR 389828, DOI 10.1007/BF02412017
- H. Niederreiter, Methods for estimating discrepancy, Applications of Number Theory to Numerical Analysis, Academic Press, New York, 1972, pp. 203–236.
- H. Niederreiter, Random number generation and quasi–Monte Carlo methods, Number 63 in CBMS-NSF Series in Applied Mathematics, SIAM, Philadelphia, 1992.
- E. Thiémard, Computing bounds for the star discrepancy, Computing 65 (2000), no. 2, 169–186. MR 1807715, DOI 10.1007/s006070070018
- Eric Thiémard, An algorithm to compute bounds for the star discrepancy, J. Complexity 17 (2001), no. 4, 850–880. Complexity of multivariate problems (Kowloon, 1999). MR 1881674, DOI 10.1006/jcom.2001.0600
- T. M. Tovstik, Calculation of the discrepancy of a finite set of points in the unit $n$-cube, Vestnik St. Petersburg Univ. Math. 40 (2007), no. 3, 250–252. MR 2359999, DOI 10.3103/S1063454107030120
- Peter Winker and Kai-Tai Fang, Application of threshold-accepting to the evaluation of the discrepancy of a set of points, SIAM J. Numer. Anal. 34 (1997), no. 5, 2028–2042. MR 1472208, DOI 10.1137/S0036142995286076
- Yaochen Zhu, A method for exact calculation of the discrepancy of low-dimensional finite points sets. II, Acta Math. Sinica (N.S.) 11 (1995), no. 4, 422–434. A Chinese summary appears in Acta Math. Sinica 39 (1996), no. 5, 720. MR 1434838, DOI 10.1007/BF02248753
References
- Christoph Aistleitner, Dmitriy Bilyk, and Aleksandar Nikolov, Tusnády’s problem, the transference principle, and non-uniform QMC sampling, Monte Carlo and quasi–Monte Carlo methods, Springer Proc. Math. Stat., vol. 241, Springer, Cham, 2018, pp. 169–180. MR 3828139, DOI 10.1007/978-3-319-91436-7_8
- P. Bundschuh and Y. Zhu, A method for exact calculation of the discrepancy of low-dimensional finite point sets. I, Abh. Math. Sem. Univ. Hamburg 63 (1993), 115–133. MR 1227869, DOI 10.1007/BF02941337
- L. de Clerck, A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley, Monatsh. Math. 101 (1986), no. 4, 261–278. MR 851948, DOI 10.1007/BF01559390
- D. P. Dobkin, D. Eppstein, and D. P. Mitchell, Computing the discrepancy with applications to supersampling patterns, ACM Trans. Graph. 15 (1996), 354–376.
- Samantha Fairchild, Max Goering, and Christian Weiss, Families of well approximable measures, Unif. Distrib. Theory 16 (2021), no. 1, 53–70. MR 4311860
- Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner, Hardness of discrepancy computation and $\epsilon$-net verification in high dimension, J. Complexity 28 (2012), no. 2, 162–176. MR 2900826, DOI 10.1016/j.jco.2011.09.001
- Michael Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity 24 (2008), no. 2, 154–172. MR 2400314, DOI 10.1016/j.jco.2007.08.003
- Michael Gnewuch, Anand Srivastav, and Carola Winzen, Finding optimal volume subintervals with $k$-points and calculating the star discrepancy are NP-hard problems, J. Complexity 25 (2009), no. 2, 115–127. MR 2513611, DOI 10.1016/j.jco.2008.10.001
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 419394
- H. Niederreiter, Discrepancy and convex programming, Ann. Mat. Pura Appl. (4) 93 (1972), 89–97. MR 389828, DOI 10.1007/BF02412017
- H. Niederreiter, Methods for estimating discrepancy, Applications of Number Theory to Numerical Analysis, Academic Press, New York, 1972, pp. 203–236.
- H. Niederreiter, Random number generation and quasi–Monte Carlo methods, Number 63 in CBMS-NSF Series in Applied Mathematics, SIAM, Philadelphia, 1992.
- E. Thiémard, Computing bounds for the star discrepancy, Computing 65 (2000), no. 2, 169–186. MR 1807715, DOI 10.1007/s006070070018
- Eric Thiémard, An algorithm to compute bounds for the star discrepancy, J. Complexity 17 (2001), no. 4, 850–880. Complexity of multivariate problems (Kowloon, 1999). MR 1881674, DOI 10.1006/jcom.2001.0600
- T. M. Tovstik, Calculation of the discrepancy of a finite set of points in the unit $n$-cube, Vestnik St. Petersburg Univ. Math. 40 (2007), no. 3, 250–252. MR 2359999, DOI 10.3103/S1063454107030120
- Peter Winker and Kai-Tai Fang, Application of threshold-accepting to the evaluation of the discrepancy of a set of points, SIAM J. Numer. Anal. 34 (1997), no. 5, 2028–2042. MR 1472208, DOI 10.1137/S0036142995286076
- Yaochen Zhu, A method for exact calculation of the discrepancy of low-dimensional finite points sets. II, Acta Math. Sinica (N.S.) 11 (1995), no. 4, 422–434. A Chinese summary appears in Acta Math. Sinica 39 (1996), no. 5, 720. MR 1434838, DOI 10.1007/BF02248753
Similar Articles
Retrieve articles in Theory of Probability and Mathematical Statistics
with MSC (2020):
60B10,
28A12,
11K38,
11J71
Retrieve articles in all journals
with MSC (2020):
60B10,
28A12,
11K38,
11J71
Additional Information
Christian Weiss
Affiliation:
Ruhr West University of Applied Sciences, Department of Natural Sciences, Duisburger Str. 100, D-45479 Mülheim an der Ruhr
ORCID:
0000-0002-3866-6874
Email:
christian.weiss@hs-ruhrwest.de
Keywords:
Star-discrepancy,
approximation of measures,
discrete measures
Received by editor(s):
June 19, 2023
Accepted for publication:
November 6, 2023
Published electronically:
October 30, 2024
Article copyright:
© Copyright 2024
Taras Shevchenko National University of Kyiv
