Optimal matching and empirical measures

Yukich, J. E.

doi:10.1090/S0002-9939-1989-1000171-8

Optimal matching and empirical measures
HTML articles powered by AMS MathViewer

by J. E. Yukich PDF

Proc. Amer. Math. Soc. 107 (1989), 1051-1059 Request permission

Abstract:

Using results from optimal matching, we find the exact order of convergence for $\beta ({P_n},P)$ and $\rho ({P_n},P)$, where $\beta$ denotes the dual bounded Lipschitz metric, $\rho$ the Prokhorov metric and ${P_n}$ the $n$th empirical measure associated to $P$, the uniform measure on the unit square. The results solve a long-open problem in empirical measures.

References

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
Kenneth S. Alexander, Probability inequalities for empirical processes and a law of the iterated logarithm, Ann. Probab. 12 (1984), no. 4, 1041–1067. MR 757769

On approximate calculation of multiple integrals

4

R. M. Dudley, Distances of probability measures and random variables, Ann. Math. Statist. 39 (1968), 1563–1572. MR 230338, DOI 10.1007/978-1-4419-5821-1_{4}
R. M. Dudley, The speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist. 40 (1968), 40–50. MR 236977, DOI 10.1214/aoms/1177697802
R. M. Dudley, Central limit theorems for empirical measures, Ann. Probab. 6 (1978), no. 6, 899–929 (1979). MR 512411
R. M. Dudley, Empirical and Poisson processes on classes of sets or functions too large for central limit theorems, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 3, 355–368. MR 679680, DOI 10.1007/BF00539835
X. Fernique, Sur le théorème de Kantorovitch-Rubinstein dans les espaces polonais, Seminar on Probability, XV (Univ. Strasbourg, Strasbourg, 1979/1980) Lecture Notes in Math., vol. 850, Springer, Berlin, 1981, pp. 6–10 (French). MR 622552
R. Fortet and E. Mourier, Convergence de la répartition empirique vers la répartition théorique, Ann. Sci. Ecole Norm. Sup. (3) 70 (1953), 267–285 (French). MR 0061325
Peter Gänssler, Note on a result of Dudley on the speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist. 41 (1970), 1339–1343. MR 266310, DOI 10.1214/aoms/1177696908
Evarist Giné and Joel Zinn, Some limit theorems for empirical processes, Ann. Probab. 12 (1984), no. 4, 929–998. With discussion. MR 757767
J. H. B. Kemperman, On the role of duality in the theory of moments, Semi-infinite programming and applications (Austin, Tex., 1981) Lecture Notes in Econom. and Math. Systems, vol. 215, Springer, Berlin-New York, 1983, pp. 63–92. MR 709269

Probabilistic analysis of multidimensional bin packing problems

A. N. Kolmogorov and V. M. Tihomirov, $\varepsilon$-entropy and $\varepsilon$-capacity of sets in function spaces, Uspehi Mat. Nauk 14 (1959), no. 2 (86), 3–86 (Russian). MR 0112032

Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms

P. Massart, About the Prohorov [Prokhorov] distance between the uniform distribution over the unit cube in $\textbf {R}^d$ and its empirical measure, Probab. Theory Related Fields 79 (1988), no. 3, 431–450. MR 959517, DOI 10.1007/BF00342234
Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1982. MR 663728
WanSoo T. Rhee and Michel Talagrand, Exact bounds for the stochastic upward matching problem, Trans. Amer. Math. Soc. 307 (1988), no. 1, 109–125. MR 936807, DOI 10.1090/S0002-9947-1988-0936807-0

Random planar matching and bin packing

P. W. Shor, The average-case analysis of some on-line algorithms for bin packing, Combinatorica 6 (1986), no. 2, 179–200. Theory of computing (Singer Island, Fla., 1984). MR 875840, DOI 10.1007/BF02579171
P. W. Shor and J. E. Yukich, Minimax grid matching and empirical measures, Ann. Probab. 19 (1991), no. 3, 1338–1348. MR 1112419

Speeds of convergence of random probability measures