Matchings and the variance of Lipschitz functions
ESAIM: Probability and Statistics, Tome 13 (2009), pp. 400-408.

We are interested in the rate function of the moderate deviation principle for the two-sample matching problem. This is related to the determination of 1-Lipschitz functions with maximal variance. We give an exact solution for random variables which have normal law, or are uniformly distributed on the euclidean ball.

DOI : 10.1051/ps:2008018
Classification : 60D05, 60F10, 26D10
Mots-clés : matching problem, large deviations, variance, spectral gap, euclidean ball 
@article{PS_2009__13__400_0,
     author = {Barthe, Franck and O{\textquoteright}Connell, Neil},
     title = {Matchings and the variance of {Lipschitz} functions},
     journal = {ESAIM: Probability and Statistics},
     pages = {400--408},
     publisher = {EDP-Sciences},
     volume = {13},
     year = {2009},
     doi = {10.1051/ps:2008018},
     mrnumber = {2554962},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ps:2008018/}
}
TY  - JOUR
AU  - Barthe, Franck
AU  - O’Connell, Neil
TI  - Matchings and the variance of Lipschitz functions
JO  - ESAIM: Probability and Statistics
PY  - 2009
SP  - 400
EP  - 408
VL  - 13
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ps:2008018/
DO  - 10.1051/ps:2008018
LA  - en
ID  - PS_2009__13__400_0
ER  - 
%0 Journal Article
%A Barthe, Franck
%A O’Connell, Neil
%T Matchings and the variance of Lipschitz functions
%J ESAIM: Probability and Statistics
%D 2009
%P 400-408
%V 13
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ps:2008018/
%R 10.1051/ps:2008018
%G en
%F PS_2009__13__400_0
Barthe, Franck; O’Connell, Neil. Matchings and the variance of Lipschitz functions. ESAIM: Probability and Statistics, Tome 13 (2009), pp. 400-408. doi : 10.1051/ps:2008018. http://archive.numdam.org/articles/10.1051/ps:2008018/

[1] M. Ajtai, J. Komlós and G. Tusnády, On optimal matchings. Combinatorica 4 (1984) 259-264. | Zbl

[2] S.G. Bobkov and F. Götze, Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 (1999) 1-28. | Zbl

[3] R.M. Dudley, The speed of mean Glivenko-Cantelli convergence. Ann. Math. Stat. 40 (1969) 40-50. | Zbl

[4] A. Ganesh and N. O'Connell, Large and moderate deviations for matching problems and empirical discrepancies. Markov Process. Relat. Fields 13 (2007) 85-98. | Zbl

[5] M. Ledoux, Sur les déviations modérées des sommes de variables aléatoires vectorielles indépendantes de même loi. Ann. Inst. H. Poincaré, Probab. Statist. 28 (1992) 267-280. | Numdam | MR | Zbl

[6] M. Ledoux, Concentration of measure and logarithmic Sobolev inequalities, in Séminaire de Probabilités, XXXIII, Lect. Notes Math. 1709 120-216. Springer, Berlin (1999). | Numdam | MR | Zbl

[7] C. Müller, Spherical harmonics IV. Springer-Verlag, Berlin-Heidelberg-New York (1966). | MR | Zbl

[8] C. Müller and F. Weissler, Hypercontractivity for the heat semigroup for ultraspherical polynomials and on the n-sphere. J. Funct. Anal. 48 (1982) 252-283. | MR | Zbl

[9] S.T. Rachev, Probability Metrics and the Stability of Stochastic Models. Wiley (1991). | MR | Zbl

[10] P.W. Shor, Random planar matching and bin packing, Ph.D. thesis, M.I.T., 1985.

[11] M. Talagrand, Matching theorems and empirical discrepancy computations using majorizing measures. J. Amer. Math. Soc. 7 (1994) 455-537. | MR | Zbl

[12] M. Talagrand, Transportation cost for Gaussian and other product measures. Geom. Funct. Anal. 6 (1996) 587-600. | MR | Zbl

[13] L. Wu, Large deviations, moderate deviations and LIL for empirical processes. Ann. Probab. 22 (1994) 17-27. | MR | Zbl

Cité par Sources :