On the Wasserstein distance between classical sequences and the Lebesgue measure. (English) Zbl 1465.11175
The \(p\)-Wasserstein distance between two measures \(\mu\) and \(\nu\) can be defined as \(W_p(\mu,\nu)=(\inf_{\gamma\in\Gamma(\mu,\nu)}\int_{M\times M} |x-y|^pd\gamma(x,y))^{1/p}\), where \(\Gamma(\mu,\nu)\) denotes the collection of all measures on \(M\times M\) with marginals \(\mu\) and \(\nu\). Informally, the Wasserstein distance is a transportation cost between two measures.
It is easy to show that for any sequence \((x_n)\in\mathbb{T}^d\) we have \(W_2(\frac{1}{N}\sum_{k=1}^N \delta_{x_k},dx)\geq \frac{c_d}{N^{1/d}}\).
Let \(\alpha\in\mathbb{T}^d\) be some badly approximable vector, \(x_n=(n\alpha)\) be corresponding Kronecker sequence. Then it is proved that \(W_2(\frac{1}{N}\sum_{k=1}^N \delta_{x_k},dx)\leq \frac{c_{\alpha,d}}{N^{1/d}}\). This result is best possible (up to constants) as well as uniform in \(N\).
Further, for all differentiable \(f:\mathbb{T}^d\to\mathbb{R}\) we have \(\left|\int_{\mathbb{T}^d}f(x)dx-\frac{1}{N}\sum_{k=1}^N x_k \right|\leq c_{\alpha}||\nabla f||_{L^{\infty}}^{(d-1)/d} ||\nabla f||_{L^2}^{1/d}N^{-1/d}\).
It is easy to show that for any sequence \((x_n)\in\mathbb{T}^d\) we have \(W_2(\frac{1}{N}\sum_{k=1}^N \delta_{x_k},dx)\geq \frac{c_d}{N^{1/d}}\).
Let \(\alpha\in\mathbb{T}^d\) be some badly approximable vector, \(x_n=(n\alpha)\) be corresponding Kronecker sequence. Then it is proved that \(W_2(\frac{1}{N}\sum_{k=1}^N \delta_{x_k},dx)\leq \frac{c_{\alpha,d}}{N^{1/d}}\). This result is best possible (up to constants) as well as uniform in \(N\).
Further, for all differentiable \(f:\mathbb{T}^d\to\mathbb{R}\) we have \(\left|\int_{\mathbb{T}^d}f(x)dx-\frac{1}{N}\sum_{k=1}^N x_k \right|\leq c_{\alpha}||\nabla f||_{L^{\infty}}^{(d-1)/d} ||\nabla f||_{L^2}^{1/d}N^{-1/d}\).
Reviewer: Anton Shutov (Vladimir)
MSC:
| 11L07 | Estimates on exponential sums |
| 11K38 | Irregularities of distribution, discrepancy |
| 41A25 | Rate of convergence, degree of approximation |
| 42B05 | Fourier series and coefficients in several variables |
| 65D30 | Numerical integration |
Keywords:
low discrepancy sequence; Wasserstein distance; integration error; exponential sum; Erdős-Turán inequality; irregularities of distribution; approximation theoryReferences:
| [1] | Ajtai, M.; Koml\'{o}s, J.; Tusn\'{a}dy, G., On optimal matchings, Combinatorica, 4, 4, 259-264 (1984) · Zbl 0562.60012 · doi:10.1007/BF02579135 |
| [2] | Ambrosio, Luigi; Stra, Federico; Trevisan, Dario, A PDE approach to a 2-dimensional matching problem, Probab. Theory Related Fields, 173, 1-2, 433-477 (2019) · Zbl 1480.60017 · doi:10.1007/s00440-018-0837-x |
| [3] | Aronson, D. G., Non-negative solutions of linear parabolic equations, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3), 22, 607-694 (1968) · Zbl 0182.13802 |
| [4] | Bakhvalov, Nikolai Sergeevich, On the approximate calculation of multiple integrals [translation of 0115275], J. Complexity, 31, 4, 502-516 (2015) · Zbl 1320.65041 · doi:10.1016/j.jco.2014.12.003 |
| [5] | Beck, J\'{o}zsef, A two-dimensional van Aardenne-Ehrenfest theorem in irregularities of distribution, Compositio Math., 72, 3, 269-339 (1989) · Zbl 0691.10041 |
| [6] | Beck, J\'{o}zsef; Chen, William W. L., Irregularities of distribution, Cambridge Tracts in Mathematics 89, xiv+294 pp. (1987), Cambridge University Press, Cambridge · Zbl 1156.11029 · doi:10.1017/CBO9780511565984 |
| [7] | Bl\"{u}mlinger, Martin, Asymptotic distribution and weak convergence on compact Riemannian manifolds, Monatsh. Math., 110, 3-4, 177-188 (1990) · Zbl 0717.28001 · doi:10.1007/BF01301674 |
| [8] | louis L. Brown and S. Steinerberger, Positive-definite Functions, Exponential Sums and the Greedy Algorithm: a curious Phenomenon, 1908.11228 · Zbl 1456.11138 |
| [9] | Bolley, Fran\c{c}ois; Guillin, Arnaud; Villani, C\'{e}dric, Quantitative concentration inequalities for empirical measures on non-compact spaces, Probab. Theory Related Fields, 137, 3-4, 541-593 (2007) · Zbl 1113.60093 · doi:10.1007/s00440-006-0004-7 |
| [10] | Burgess, D. A., The distribution of quadratic residues and non-residues, Mathematika, 4, 106-112 (1957) · Zbl 0081.27101 · doi:10.1112/S0025579300001157 |
| [11] | Cassels, J. W. S., Simultaneous diophantine approximation. II, Proc. London Math. Soc. (3), 5, 435-448 (1955) · Zbl 0065.28302 · doi:10.1112/plms/s3-5.4.435 |
| [12] | Chaix, Henri; Faure, Henri, Discr\'{e}pance et diaphonie en dimension un, Acta Arith., 63, 2, 103-141 (1993) · Zbl 0772.11022 · doi:10.4064/aa-63-2-103-141 |
| [13] | Chazelle, Bernard, The discrepancy method, xviii+463 pp. (2000), Cambridge University Press, Cambridge · Zbl 0960.65149 · doi:10.1017/CBO9780511626371 |
| [14] | Davenport, H., Simultaneous Diophantine approximation, Mathematika, 1, 51-72 (1954) · Zbl 0056.04303 · doi:10.1112/S0025579300000528 |
| [15] | Dick, Josef; Pillichshammer, Friedrich, Digital nets and sequences, xviii+600 pp. (2010), Cambridge University Press, Cambridge · Zbl 1282.65012 · doi:10.1017/CBO9780511761188 |
| [16] | Drmota, Michael; Tichy, Robert F., Sequences, discrepancies and applications, Lecture Notes in Mathematics 1651, xiv+503 pp. (1997), Springer-Verlag, Berlin · Zbl 0877.11043 · doi:10.1007/BFb0093404 |
| [17] | Erd\"{o}s, P.; Tur\'{a}n, P., On a problem in the theory of uniform distribution. I, Nederl. Akad. Wetensch., Proc., 51, 1146-1154 = Indagationes Math. 10, 370-378 (1948) (1948) · Zbl 0031.25402 |
| [18] | Erd\"{o}s, P.; Tur\'{a}n, P., On a problem in the theory of uniform distribution. II, Nederl. Akad. Wetensch., Proc., 51, 1262-1269 = Indagationes Math. 10, 406-413 (1948) (1948) · Zbl 0032.01601 |
| [19] | Evans, Lawrence C., Partial differential equations, Graduate Studies in Mathematics 19, xxii+749 pp. (2010), American Mathematical Society, Providence, RI · Zbl 1194.35001 · doi:10.1090/gsm/019 |
| [20] | Faure, Henri, Discrepancy and diaphony of digital \((0,1)\)-sequences in prime base, Acta Arith., 117, 2, 125-148 (2005) · Zbl 1080.11054 · doi:10.4064/aa117-2-2 |
| [21] | Freeden, W., On integral formulas of the (unit) sphere and their application to numerical computation of integrals, Computing, 25, 2, 131-146 (1980) · Zbl 0419.65014 · doi:10.1007/BF02259639 |
| [22] | Garc\'{\i}a Trillos, Nicol\'{a}s; Slep\v{c}ev, Dejan, On the rate of convergence of empirical measures in \(\infty \)-transportation distance, Canad. J. Math., 67, 6, 1358-1383 (2015) · Zbl 1355.60009 · doi:10.4153/CJM-2014-044-6 |
| [23] | Grabner, Peter J., Erd\H{o}s-Tur\'{a}n type discrepancy bounds, Monatsh. Math., 111, 2, 127-135 (1991) · Zbl 0719.11046 · doi:10.1007/BF01332351 |
| [24] | Grabner, Peter J.; Tichy, Robert F., Spherical designs, discrepancy and numerical integration, Math. Comp., 60, 201, 327-336 (1993) · Zbl 0795.65011 · doi:10.2307/2153170 |
| [25] | Grabner, P. J.; Klinger, B.; Tichy, R. F., Discrepancies of point sequences on the sphere and numerical integration. Multivariate approximation, Witten-Bommerholz, 1996, Math. Res. 101, 95-112 (1997), Akademie Verlag, Berlin · Zbl 0889.65017 |
| [26] | graham C. Graham, Irregularity of distribution in Wasserstein distance, 1910.14181 · Zbl 1460.11105 |
| [27] | Grozdanov, Vassil St., On the diaphony of one class of one-dimensional sequences, Internat. J. Math. Math. Sci., 19, 1, 115-124 (1996) · Zbl 0841.11038 · doi:10.1155/S016117129600018X |
| [28] | Hensley, Doug; Su, Francis Edward, Random walks with badly approximable numbers. Unusual applications of number theory, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 64, 95-101 (2004), Amer. Math. Soc., Providence, RI · Zbl 1085.11038 |
| [29] | Hinrichs, A.; Novak, E.; Ullrich, M.; Wo\'{z}niakowski, H., The curse of dimensionality for numerical integration of smooth functions, Math. Comp., 83, 290, 2853-2863 (2014) · Zbl 1345.65014 · doi:10.1090/S0025-5718-2014-02855-X |
| [30] | Hinrichs, Aicke; Novak, Erich; Ullrich, Mario; Wo\'{z}niakowski, Henryk, The curse of dimensionality for numerical integration of smooth functions II, J. Complexity, 30, 2, 117-143 (2014) · Zbl 1286.65040 · doi:10.1016/j.jco.2013.10.007 |
| [31] | Hinrichs, Aicke; Novak, Erich; Ullrich, Mario; Wo\'{z}niakowski, Henryk, Product rules are optimal for numerical integration in classical smoothness spaces, J. Complexity, 38, 39-49 (2017) · Zbl 1354.65043 · doi:10.1016/j.jco.2016.09.001 |
| [32] | Hlawka, Edmund, Funktionen von beschr\"{a}nkter Variation in der Theorie der Gleichverteilung, Ann. Mat. Pura Appl. (4), 54, 325-333 (1961) · Zbl 0103.27604 · doi:10.1007/BF02415361 |
| [33] | Huesmann, Martin; Sturm, Karl-Theodor, Optimal transport from Lebesgue to Poisson, Ann. Probab., 41, 4, 2426-2478 (2013) · Zbl 1279.60024 · doi:10.1214/12-AOP814 |
| [34] | Kuipers, L.; Niederreiter, H., Uniform distribution of sequences, xiv+390 pp. (1974), Wiley-Interscience [John Wiley & Sons], New York-London-Sydney · Zbl 0281.10001 |
| [35] | Leveque, W. J., An inequality connected with Weyl’s criterion for uniform distribution. Proc. Sympos. Pure Math., Vol. VIII, 22-30 (1965), Amer. Math. Soc., Providence, R.I. · Zbl 0136.33901 |
| [36] | Narcowich, F. J.; Sun, X.; Ward, J. D.; Wu, Z., LeVeque type inequalities and discrepancy estimates for minimal energy configurations on spheres, J. Approx. Theory, 162, 6, 1256-1278 (2010) · Zbl 1200.11058 · doi:10.1016/j.jat.2010.01.003 |
| [37] | Novak, Erich, Some results on the complexity of numerical integration. Monte Carlo and quasi-Monte Carlo methods, Springer Proc. Math. Stat. 163, 161-183 (2016), Springer, [Cham] · Zbl 1356.65085 · doi:10.1007/978-3-319-33507-0\_6 |
| [38] | Novak, Erich; Wo\'{z}niakowski, Henryk, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics 6, xii+384 pp. (2008), European Mathematical Society (EMS), Z\"{u}rich · Zbl 1156.65001 · doi:10.4171/026 |
| [39] | O’Neil, Richard, Convolution operators and \(L(p,\,q)\) spaces, Duke Math. J., 30, 129-142 (1963) · Zbl 0178.47701 |
| [40] | Pausinger, Florian; Schmid, Wolfgang Ch., A good permutation for one-dimensional diaphony, Monte Carlo Methods Appl., 16, 3-4, 307-322 (2010) · Zbl 1206.11096 · doi:10.1515/MCMA.2010.015 |
| [41] | Peyre, R\'{e}mi, Comparison between \(\text{W}_2\) distance and \(\dot{\text{H}}^{-1}\) norm, and localization of Wasserstein distance, ESAIM Control Optim. Calc. Var., 24, 4, 1489-1501 (2018) · Zbl 1415.49031 · doi:10.1051/cocv/2017050 |
| [42] | Perron, Oskar, \"{U}ber diophantische Approximationen, Math. Ann., 83, 1-2, 77-84 (1921) · JFM 48.0194.01 · doi:10.1007/BF01464229 |
| [43] | Pro\u{\i}nov, P. D., On irregularities of distribution, C. R. Acad. Bulgare Sci., 39, 9, 31-34 (1986) · Zbl 0616.10042 |
| [44] | Pro\u{\i}nov, Petko D.; Grozdanov, Vasil S., On the diaphony of the van der Corput-Halton sequence, J. Number Theory, 30, 1, 94-104 (1988) · Zbl 0654.10050 · doi:10.1016/0022-314X(88)90028-5 |
| [45] | Santambrogio, Filippo, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications 87, xxvii+353 pp. (2015), Birkh\"{a}user/Springer, Cham · Zbl 1401.49002 · doi:10.1007/978-3-319-20828-2 |
| [46] | Schmidt, Wolfgang M., On badly approximable numbers and certain games, Trans. Amer. Math. Soc., 123, 178-199 (1966) · Zbl 0232.10029 · doi:10.2307/1994619 |
| [47] | Schmidt, Wolfgang M., Diophantine approximation, Lecture Notes in Mathematics 785, x+299 pp. (1980), Springer, Berlin · Zbl 0421.10019 |
| [48] | stein0 S. Steinerberger, Wasserstein Distance, Fourier Series and Applications, 1803.08011 · Zbl 1457.60005 |
| [49] | Steinerberger, Stefan, Dynamically defined sequences with small discrepancy, Monatsh. Math., 191, 3, 639-655 (2020) · Zbl 1471.11222 · doi:10.1007/s00605-019-01360-z |
| [50] | Steinerberger, Stefan, A nonlocal functional promoting low-discrepancy point sets, J. Complexity, 54, 101410, 15 pp. (2019) · Zbl 1423.49002 · doi:10.1016/j.jco.2019.06.001 |
| [51] | stein3 S. Steinerberger, A Wasserstein Inequality and Minimal Green Energy on Compact Manifolds, 1907.09023 |
| [52] | Steinerberger, Stefan, Directional Poincar\'{e} inequalities along mixing flows, Ark. Mat., 54, 2, 555-569 (2016) · Zbl 1406.11065 · doi:10.1007/s11512-016-0241-7 |
| [53] | Su, Francis Edward, Convergence of random walks on the circle generated by an irrational rotation, Trans. Amer. Math. Soc., 350, 9, 3717-3741 (1998) · Zbl 0902.60051 · doi:10.1090/S0002-9947-98-02152-7 |
| [54] | Su, Francis Edward, A LeVeque-type lower bound for discrepancy. Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), 448-458 (2000), Springer, Berlin · Zbl 0970.11031 |
| [55] | Su, Francis Edward, Discrepancy convergence for the drunkard’s walk on the sphere, Electron. J. Probab., 6, no. 2, 20 pp. (2001) · Zbl 0978.60011 · doi:10.1214/EJP.v6-75 |
| [56] | suk A. G. Sukharev, Optimal numerical integration formulas for some classes of functions, Sov. Math. Dokl. 20, 472-475, 1979. · Zbl 0433.65009 |
| [57] | Talagrand, M.; Yukich, J. E., The integrability of the square exponential transportation cost, Ann. Appl. Probab., 3, 4, 1100-1111 (1993) · Zbl 0784.60014 |
| [58] | Talagrand, M., Matching theorems and empirical discrepancy computations using majorizing measures, J. Amer. Math. Soc., 7, 2, 455-537 (1994) · Zbl 0810.60036 · doi:10.2307/2152764 |
| [59] | Talagrand, M., The transportation cost from the uniform measure to the empirical measure in dimension \(\ge3\), Ann. Probab., 22, 2, 919-959 (1994) · Zbl 0809.60015 |
| [60] | Villani, C\'{e}dric, Topics in optimal transportation, Graduate Studies in Mathematics 58, xvi+370 pp. (2003), American Mathematical Society, Providence, RI · Zbl 1106.90001 · doi:10.1090/gsm/058 |
| [61] | Zinterhof, P., \"{U}ber einige Absch\"{a}tzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden, \"{O}sterreich. Akad. Wiss. Math.-Naturwiss. Kl. S.-B. II, 185, 1-3, 121-132 (1976) · Zbl 0356.65007 |
| [62] | Zinterhof, P.; Stegbuchner, H., Trigonometrische Approximation mit Gleichverteilungsmethoden, Studia Sci. Math. Hungar., 13, 3-4, 273-289 (1981) (1978) · Zbl 0421.42001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
