Theory of Probability and Mathematical Statistics
On the discrepancy of low-dimensional probability measures
Christian Weiss
Link
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.
Keywords: Star-discrepancy, approximation of measures, discrete measures
Bibliography: 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
-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
-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
