AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
One-dimensional empirical measures, order statistics, and Kantorovich transport distances
About this Title
Sergey Bobkov, School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455 and Michel Ledoux, Institut de Mathématiques de Toulouse, Université de Toulouse, F-31062 Toulouse, France — and — Institut Universitaire de France
Publication: Memoirs of the American Mathematical Society
Publication Year:
2019; Volume 261, Number 1259
ISBNs: 978-1-4704-3650-6 (print); 978-1-4704-5401-2 (online)
DOI: https://doi.org/10.1090/memo/1259
Published electronically: November 5, 2019
Keywords: Empirical measure,
Kantorovich distance,
rate of convergence,
finite rate bound,
order statistic,
inverse distribution function,
beta distribution,
log-concave measure.
MSC: Primary 60B10, 60F99, 60G57, 62G30, 60B12; Secondary 62G20
Table of Contents
Chapters
- 1. Introduction
- 2. Generalities on Kantorovich transport distances
- 3. The Kantorovich distance $W_1(\mu _n, \mu )$
- 4. Order statistics representations of $W_p(\mu _n, \mu )$
- 5. Standard rate for ${\mathbb {E}}(W_p^p(\mu _n,\mu ))$
- 6. Sampling from log-concave distributions
- 7. Miscellaneous bounds and results
Appendices
- A. Inverse distribution functions
- B. Beta distributions
Abstract
This work is devoted to the study of rates of convergence of the empirical measures $\mu _n = \frac {1}{n} \sum _{k=1}^n \delta _{X_k}$, $n \geq 1$, over a sample ${(X_k)}_{k \geq 1}$ of independent identically distributed real-valued random variables towards the common distribution $\mu$ in Kantorovich transport distances $W_p$. The focus is on finite range bounds on the expected Kantorovich distances $\mathbb {E}(W_p(\mu _n,\mu ))$ or $\big [ \mathbb {E}(W_p^p(\mu _n,\mu )) \big ]^{1/p}$ in terms of moments and analytic conditions on the measure $\mu$ and its distribution function. The study describes a variety of rates, from the standard one $\frac {1}{\sqrt n}$ to slower rates, and both lower and upper-bounds on $\mathbb {E}(W_p(\mu _n,\mu ))$ for fixed $n$ in various instances. Order statistics, reduction to uniform samples and analysis of beta distributions, inverse distribution functions, log-concavity are main tools in the investigation. Two detailed appendices collect classical and some new facts on inverse distribution functions and beta distributions and their densities necessary to the investigation.- S. Aida and D. Stroock, Moment estimates derived from Poincaré and logarithmic Sobolev inequalities, Math. Res. Lett. 1 (1994), no. 1, 75–86. MR 1258492, DOI 10.4310/MRL.1994.v1.n1.a9
- M. Ajtai, J. Komlós, and G. Tusnády, On optimal matchings, Combinatorica 4 (1984), no. 4, 259–264. MR 779885, DOI 10.1007/BF02579135
- Luigi Ambrosio, Federico Stra, and Dario Trevisan, A PDE approach to a 2-dimensional matching problem, Probab. Theory Related Fields 173 (2019), no. 1-2, 433–477. MR 3916111, DOI 10.1007/s00440-018-0837-x
- Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni, An introduction to random matrices, Cambridge Studies in Advanced Mathematics, vol. 118, Cambridge University Press, Cambridge, 2010. MR 2760897
- Dominique Bakry, Ivan Gentil, and Michel Ledoux, Analysis and geometry of Markov diffusion operators, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 348, Springer, Cham, 2014. MR 3155209
- Keith Ball, Logarithmically concave functions and sections of convex sets in $\textbf {R}^n$, Studia Math. 88 (1988), no. 1, 69–84. MR 932007, DOI 10.4064/sm-88-1-69-84
- Richard E. Barlow, Albert W. Marshall, and Frank Proschan, Properties of probability distributions with monotone hazard rate, Ann. Math. Statist. 34 (1963), 375–389. MR 171328, DOI 10.1214/aoms/1177704147
- Eustasio del Barrio, Evarist Giné, and Carlos Matrán, Central limit theorems for the Wasserstein distance between the empirical and the true distributions, Ann. Probab. 27 (1999), no. 2, 1009–1071. MR 1698999, DOI 10.1214/aop/1022677394
- Eustasio del Barrio, Evarist Giné, and Frederic Utzet, Asymptotics for $L_2$ functionals of the empirical quantile process, with applications to tests of fit based on weighted Wasserstein distances, Bernoulli 11 (2005), no. 1, 131–189. MR 2121458, DOI 10.3150/bj/1110228245
- Eustasio del Barrio and Carlos Matrán, Rates of convergence for partial mass problems, Probab. Theory Related Fields 155 (2013), no. 3-4, 521–542. MR 3034786, DOI 10.1007/s00440-011-0406-z
- Eustasio del Barrio and Carlos Matrán, The empirical cost of optimal incomplete transportation, Ann. Probab. 41 (2013), no. 5, 3140–3156. MR 3127877, DOI 10.1214/12-AOP812
- Franck Barthe and Charles Bordenave, Combinatorial optimization over two random point sets, Séminaire de Probabilités XLV, Lecture Notes in Math., vol. 2078, Springer, Cham, 2013, pp. 483–535. MR 3185927, DOI 10.1007/978-3-319-00321-4_{1}9
- Patrick Billingsley, Convergence of probability measures, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0233396
- S. G. Bobkov, Some extremal properties of the Bernoulli distribution, Teor. Veroyatnost. i Primenen. 41 (1996), no. 4, 877–884 (Russian, with Russian summary); English transl., Theory Probab. Appl. 41 (1996), no. 4, 748–755 (1997). MR 1687168
- S. Bobkov, Extremal properties of half-spaces for log-concave distributions, Ann. Probab. 24 (1996), no. 1, 35–48. MR 1387625, DOI 10.1214/aop/1042644706
- S. G. Bobkov, Remarks on the Gromov-Milman inequality, Vestn. Syktyvkar. Univ. Ser. 1 Mat. Mekh. Inform. 3 (1999), 15–22 (Russian, with English and Russian summaries). MR 1716649
- S. G. Bobkov, Isoperimetric and analytic inequalities for log-concave probability measures, Ann. Probab. 27 (1999), no. 4, 1903–1921. MR 1742893, DOI 10.1214/aop/1022874820
- S. G. Bobkov, Spectral gap and concentration for some spherically symmetric probability measures, Geometric aspects of functional analysis, Lecture Notes in Math., vol. 1807, Springer, Berlin, 2003, pp. 37–43. MR 2083386, DOI 10.1007/978-3-540-36428-3_{4}
- S. G. Bobkov, Gaussian concentration for a class of spherically invariant measures, J. Math. Sci. (N.Y.) 167 (2010), no. 3, 326–339. Problems in mathematical analysis. No. 46. MR 2839024, DOI 10.1007/s10958-010-9922-0
- Sergey G. Bobkov and Gennadiy P. Chistyakov, On concentration functions of random variables, J. Theoret. Probab. 28 (2015), no. 3, 976–988. MR 3413964, DOI 10.1007/s10959-013-0504-1
- S. G. Bobkov and F. Götze, Concentration of empirical distribution functions with applications to non-i.i.d. models, Bernoulli 16 (2010), no. 4, 1385–1414. MR 2759184, DOI 10.3150/10-BEJ254
- S. G. Bobkov, F. Götze, and A. N. Tikhomirov, On concentration of empirical measures and convergence to the semi-circle law, J. Theoret. Probab. 23 (2010), no. 3, 792–823. MR 2679957, DOI 10.1007/s10959-010-0286-7
- S. G. Bobkov and C. Houdré, Isoperimetric constants for product probability measures, Ann. Probab. 25 (1997), no. 1, 184–205. MR 1428505, DOI 10.1214/aop/1024404284
- Serguei G. Bobkov and Christian Houdré, Some connections between isoperimetric and Sobolev-type inequalities, Mem. Amer. Math. Soc. 129 (1997), no. 616, viii+111. MR 1396954, DOI 10.1090/memo/0616
- Sergey Bobkov and Mokshay Madiman, Concentration of the information in data with log-concave distributions, Ann. Probab. 39 (2011), no. 4, 1528–1543. MR 2857249, DOI 10.1214/10-AOP592
- V. I. Bogachev and A. V. Kolesnikov, The Monge-Kantorovich problem: achievements, connections, and prospects, Uspekhi Mat. Nauk 67 (2012), no. 5(407), 3–110 (Russian, with Russian summary); English transl., Russian Math. Surveys 67 (2012), no. 5, 785–890. MR 3058744, DOI 10.1070/rm2012v067n05abeh004808
- Emmanuel Boissard, Simple bounds for convergence of empirical and occupation measures in 1-Wasserstein distance, Electron. J. Probab. 16 (2011), no. 83, 2296–2333. MR 2861675, DOI 10.1214/EJP.v16-958
- François Bolley, Arnaud Guillin, and Cédric Villani, Quantitative concentration inequalities for empirical measures on non-compact spaces, Probab. Theory Related Fields 137 (2007), no. 3-4, 541–593. MR 2280433, DOI 10.1007/s00440-006-0004-7
- Christer Borell, Complements of Lyapunov’s inequality, Math. Ann. 205 (1973), 323–331. MR 323977, DOI 10.1007/BF01362702
- Christer Borell, Convex measures on locally convex spaces, Ark. Mat. 12 (1974), 239–252. MR 388475, DOI 10.1007/BF02384761
- I. S. Borisov and A. V. Shadrin, Some remarks on the Sh. S. Èbralidze inequality, Teor. Veroyatnost. i Primenen. 41 (1996), no. 1, 177–181 (Russian, with Russian summary); English transl., Theory Probab. Appl. 41 (1996), no. 1, 143–146 (1997). MR 1404902
- A. A. Borovkov and S. A. Utev, An inequality and a characterization of the normal distribution connected with it, Teor. Veroyatnost. i Primenen. 28 (1983), no. 2, 209–218 (Russian, with English summary). MR 700206
- Herm Jan Brascamp and Elliott H. Lieb, On extensions of the Brunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation, J. Functional Analysis 22 (1976), no. 4, 366–389. MR 0450480, DOI 10.1016/0022-1236(76)90004-5
- Stamatis Cambanis, Gordon Simons, and William Stout, Inequalities for $Ek(X,Y)$ when the marginals are fixed, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 36 (1976), no. 4, 285–294. MR 420778, DOI 10.1007/BF00532695
- Sourav Chatterjee and Michel Ledoux, An observation about submatrices, Electron. Commun. Probab. 14 (2009), 495–500. MR 2559099, DOI 10.1214/ECP.v14-1504
- Miklós Csörgő and Lajos Horváth, Weighted approximations in probability and statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1993. With a foreword by David Kendall. MR 1215046
- Miklós Csörgő and Pál Révész, Strong approximations of the quantile process, Ann. Statist. 6 (1978), no. 4, 882–894. MR 501290
- Giorgio Dall’Aglio, Sugli estremi dei momenti delle funzioni di ripartizione doppia, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3) 10 (1956), 35–74 (Italian). MR 81577
- S. Dallaporta, Eigenvalue variance bounds for Wigner and covariance random matrices, Random Matrices Theory Appl. 1 (2012), no. 3, 1250007, 28. MR 2967966, DOI 10.1142/S2010326312500074
- Steffen Dereich, Michael Scheutzow, and Reik Schottstedt, Constructive quantization: approximation by empirical measures, Ann. Inst. Henri Poincaré Probab. Stat. 49 (2013), no. 4, 1183–1203 (English, with English and French summaries). MR 3127919, DOI 10.1214/12-AIHP489
- V. Dobrić and J. E. Yukich, Asymptotics for transportation cost in high dimensions, J. Theoret. Probab. 8 (1995), no. 1, 97–118. MR 1308672, DOI 10.1007/BF02213456
- R. L. Dobrušin, Definition of a system of random variables by means of conditional distributions, Teor. Verojatnost. i Primenen. 15 (1970), 469–497 (Russian, with English summary). MR 0298716
- Richard M. Dudley, Real analysis and probability, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1989. MR 982264
- R. M. Dudley, Uniform central limit theorems, Cambridge Studies in Advanced Mathematics, vol. 63, Cambridge University Press, Cambridge, 1999. MR 1720712
- A. Dvoretzky, J. Kiefer, and J. Wolfowitz, Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator, Ann. Math. Statist. 27 (1956), 642–669. MR 83864, DOI 10.1214/aoms/1177728174
- Š. S. Èbralidze, Inequalities for the probabilities of large deviations in terms of pseudomoments, Teor. Verojatnost. i Primenen. 16 (1971), 760–765 (Russian, with English summary). MR 0295417
- N. Etemadi, Maximal inequalities for averages of i.i.d. and $2$-exchangeable random variables, Statist. Probab. Lett. 44 (1999), no. 2, 195–200. MR 1706404, DOI 10.1016/S0167-7152(99)00009-7
- Matthieu Fradelizi, Hyperplane sections of convex bodies in isotropic position, Beiträge Algebra Geom. 40 (1999), no. 1, 163–183. MR 1678528
- Nicolas Fournier and Arnaud Guillin, On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Related Fields 162 (2015), no. 3-4, 707–738. MR 3383341, DOI 10.1007/s00440-014-0583-7
- Janos Galambos, The asymptotic theory of extreme order statistics, 2nd ed., Robert E. Krieger Publishing Co., Inc., Melbourne, FL, 1987. MR 936631
- Evarist Giné and Joel Zinn, Empirical processes indexed by Lipschitz functions, Ann. Probab. 14 (1986), no. 4, 1329–1338. MR 866353
- Nathael Gozlan, A characterization of dimension free concentration in terms of transportation inequalities, Ann. Probab. 37 (2009), no. 6, 2480–2498. MR 2573565, DOI 10.1214/09-AOP470
- Nathael Gozlan and Christian Léonard, A large deviation approach to some transportation cost inequalities, Probab. Theory Related Fields 139 (2007), no. 1-2, 235–283. MR 2322697, DOI 10.1007/s00440-006-0045-y
- N. Gozlan and C. Léonard, Transport inequalities. A survey, Markov Process. Related Fields 16 (2010), no. 4, 635–736. MR 2895086
- M. Gromov and V. D. Milman, A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), no. 4, 843–854. MR 708367, DOI 10.2307/2374298
- Olivier Guédon, Kahane-Khinchine type inequalities for negative exponent, Mathematika 46 (1999), no. 1, 165–173. MR 1750653, DOI 10.1112/S002557930000766X
- Uffe Haagerup, The best constants in the Khintchine inequality, Studia Math. 70 (1981), no. 3, 231–283 (1982). MR 654838, DOI 10.4064/sm-70-3-231-283
- J. Hájek and A. Rényi, Generalization of an inequality of Kolmogorov, Acta Math. Acad. Sci. Hungar. 6 (1955), 281–283 (English, with Russian summary). MR 76207, DOI 10.1007/BF02024392
- Douglas Hensley, Slicing convex bodies—bounds for slice area in terms of the body’s covariance, Proc. Amer. Math. Soc. 79 (1980), no. 4, 619–625. MR 572315, DOI 10.1090/S0002-9939-1980-0572315-5
- L. V. Kantorovich, On mass transportation, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 312 (2004), no. Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 11, 11–14 (Russian); English transl., J. Math. Sci. (N.Y.) 133 (2006), no. 4, 1381–1382. MR 2117876, DOI 10.1007/s10958-006-0049-2
- L. V. Kantorovich, On a problem of Monge, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 312 (2004), no. Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 11, 15–16 (Russian); English transl., J. Math. Sci. (N.Y.) 133 (2006), no. 4, 1383. MR 2117877, DOI 10.1007/s10958-006-0050-9
- L. V. Kantorovich and G. P. Akilov, Functional analysis, 2nd ed., Pergamon Press, Oxford-Elmsford, N.Y., 1982. Translated from the Russian by Howard L. Silcock. MR 664597
- L. V. Kantorovič and G. Š. Rubinšteĭn, On a space of completely additive functions, Vestnik Leningrad. Univ. 13 (1958), no. 7, 52–59 (Russian, with English summary). MR 0102006
- Tae Yoon Kim, On tail probabilities of Kolmogorov-Smirnov statistics based on uniform mixing processes, Statist. Probab. Lett. 43 (1999), no. 3, 217–223. MR 1708089, DOI 10.1016/S0167-7152(98)00254-5
- B. Klartag, A central limit theorem for convex sets, Invent. Math. 168 (2007), no. 1, 91–131. MR 2285748, DOI 10.1007/s00222-006-0028-8
- Michel Ledoux, On Talagrand’s deviation inequalities for product measures, ESAIM Probab. Statist. 1 (1995/97), 63–87. MR 1399224, DOI 10.1051/ps:1997103
- Michel Ledoux, Concentration of measure and logarithmic Sobolev inequalities, Séminaire de Probabilités, XXXIII, Lecture Notes in Math., vol. 1709, Springer, Berlin, 1999, pp. 120–216. MR 1767995, DOI 10.1007/BFb0096511
- Michel Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR 1849347
- Michel Ledoux, Spectral gap, logarithmic Sobolev constant, and geometric bounds, Surveys in differential geometry. Vol. IX, Surv. Differ. Geom., vol. 9, Int. Press, Somerville, MA, 2004, pp. 219–240. MR 2195409, DOI 10.4310/SDG.2004.v9.n1.a6
- L. Lovász and M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures Algorithms 4 (1993), no. 4, 359–412. MR 1238906, DOI 10.1002/rsa.3240040402
- Marcinkiewicz, J., Zygmund, A., Sur les fonctions independantes. Fund. Math., 28 (1937), 60–90. Reprinted in Jozef Marcinkiewicz, Collected papers, edited by Antoni Zygmund, Panstwowe Wydawnictwo Naukowe, Warsaw, 1964, 233–259.
- P. Massart, The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality, Ann. Probab. 18 (1990), no. 3, 1269–1283. MR 1062069
- Elizabeth S. Meckes and Mark W. Meckes, Concentration and convergence rates for spectral measures of random matrices, Probab. Theory Related Fields 156 (2013), no. 1-2, 145–164. MR 3055255, DOI 10.1007/s00440-012-0423-6
- Leonid Pastur and Mariya Shcherbina, Eigenvalue distribution of large random matrices, Mathematical Surveys and Monographs, vol. 171, American Mathematical Society, Providence, RI, 2011. MR 2808038
- Yu. V. Prokhorov, Convergence of random processes and limit theorems in probability theory, Teor. Veroyatnost. i Primenen. 1 (1956), 177–238 (Russian, with English summary). MR 0084896
- S. T. Rachev, The Monge-Kantorovich problem on mass transfer and its applications in stochastics, Teor. Veroyatnost. i Primenen. 29 (1984), no. 4, 625–653 (Russian). MR 773434
- Svetlozar T. Rachev and Ludger Rüschendorf, Mass transportation problems. Vol. I, Probability and its Applications (New York), Springer-Verlag, New York, 1998. Theory. MR 1619170
- Emmanuel Rio, Upper bounds for minimal distances in the central limit theorem, Ann. Inst. Henri Poincaré Probab. Stat. 45 (2009), no. 3, 802–817 (English, with English and French summaries). MR 2548505, DOI 10.1214/08-AIHP187
- Ludger Rüschendorf, The Wasserstein distance and approximation theorems, Z. Wahrsch. Verw. Gebiete 70 (1985), no. 1, 117–129. MR 795791, DOI 10.1007/BF00532240
- Pranab Kumar Sen, Weak convergence of multidimensional empirical processes for stationary $\varphi$-mixing processes, Ann. Probability 2 (1974), no. 1, 147–154. MR 402845, DOI 10.1214/aop/1176996760
- Galen R. Shorack and Jon A. Wellner, Empirical processes with applications to statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986. MR 838963
- V. A. Statuljavičus, Limit theorems for densities and the asymptotic expansions for distributions of sums of independent random variables, Teor. Verojatnost. i Primene 10 (1965), 645–659 (Russian, with English summary). MR 0193660
- V. Strassen, The existence of probability measures with given marginals, Ann. Math. Statist. 36 (1965), 423–439. MR 177430, DOI 10.1214/aoms/1177700153
- M. Talagrand, The transportation cost from the uniform measure to the empirical measure in dimension $\ge 3$, Ann. Probab. 22 (1994), no. 2, 919–959. MR 1288137
- Michel Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes Études Sci. Publ. Math. 81 (1995), 73–205. MR 1361756
- M. Talagrand and J. E. Yukich, The integrability of the square exponential transportation cost, Ann. Appl. Probab. 3 (1993), no. 4, 1100–1111. MR 1241036
- S. S. Vallander, Calculations of the Vasseršteĭn distance between probability distributions on the line, Teor. Verojatnost. i Primenen. 18 (1973), 824–827 (Russian, with English summary). MR 0328982
- V. S. Varadarajan, On the convergence of sample probability distributions, Sankhyā 19 (1958), 23–26. MR 94839
- L. N. Vasershtein, Markov processes over denumerable products of spaces describing large system of automata, Problems Inform. Transmission 5 (1969), no. 3, 47–52. MR 314115, DOI 10.1016/s0016-0032(33)90010-1
- A. M. Vershik, Long history of the Monge-Kantorovich transportation problem, Math. Intelligencer 35 (2013), no. 4, 1–9. MR 3133757, DOI 10.1007/s00283-013-9380-x
- A. M. Vershik, Two ways of defining compatible metrics on the simplex of measures, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 411 (2013), no. Teoriya Predstavleniĭ, Dinamicheskie Sistemy, Kombinatornye Metody. XXII, 38–48, 240 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 196 (2014), no. 2, 138–143. MR 3048267, DOI 10.1007/s10958-013-1645-6
- Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483
- Cédric Villani, Optimal transport, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag, Berlin, 2009. Old and new. MR 2459454
- Ken-ichi Yoshihara, Weak convergence of multidimensional empirical processes for strong mixing sequences of stochastic vectors, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 33 (1975/76), no. 2, 133–137. MR 385962, DOI 10.1007/BF00538353
- Joseph E. Yukich, Probability theory of classical Euclidean optimization problems, Lecture Notes in Mathematics, vol. 1675, Springer-Verlag, Berlin, 1998. MR 1632875
- Vladimir M. Zolotarev, Modern theory of summation of random variables, Modern Probability and Statistics, VSP, Utrecht, 1997. MR 1640024