Hostname: page-component-5cf477f64f-n7lw4 Total loading time: 0 Render date: 2025-04-04T01:01:26.144Z Has data issue: false hasContentIssue false
  • English
  • Français

Matchings and the variance of Lipschitz functions

Published online by Cambridge University Press:  22 September 2009

Franck Barthe  and
Neil O'Connell
Franck Barthe
Affiliation:
Institut de Mathématiques de Toulouse, CNRS UMR 5219, Université Paul Sabatier, 31062 Toulouse Cedex 09, France; barthe@math.univ-toulouse.fr
Neil O'Connell
Affiliation:
Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK.
Get access

Abstract

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-Lipschitzfunctions with maximal variance. We give an exact solution for random variables which havenormal law, or are uniformly distributed on the Euclidean ball.

Keywords

Matching problemlarge deviationsvariancespectral gapEuclidean ball.
Type
Research Article
Information
ESAIM: Probability and Statistics , Volume 13 , July 2009 , pp. 400 - 408
Copyright
© EDP Sciences, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ajtai, M., Komlós, J. and Tusnády, G., On optimal matchings. Combinatorica 4 (1984) 259–264. CrossRef
Bobkov, S.G. and Götze, F., Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal. 163 (1999) 1–28. CrossRef
Dudley, R.M., The speed of mean Glivenko-Cantelli convergence. Ann. Math. Stat. 40 (1969) 40–50. CrossRef
Ganesh, A. and O'Connell, N., Large and moderate deviations for matching problems and empirical discrepancies. Markov Process. Relat. Fields 13 (2007) 85–98.
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.
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).
C. Müller, Spherical harmonics IV. Springer-Verlag, Berlin-Heidelberg-New York (1966).
Müller, C. and Weissler, F., Hypercontractivity for the heat semigroup for ultraspherical polynomials and on the n-sphere. J. Funct. Anal. 48 (1982) 252–283. CrossRef
S.T. Rachev, Probability Metrics and the Stability of Stochastic Models. Wiley (1991).
P.W. Shor, Random planar matching and bin packing , Ph.D. thesis, M.I.T., 1985.
Talagrand, M., Matching theorems and empirical discrepancy computations using majorizing measures. J. Amer. Math. Soc. 7 (1994) 455–537. CrossRef
Talagrand, M., Transportation cost for Gaussian and other product measures. Geom. Funct. Anal. 6 (1996) 587–600. CrossRef
Large de, L. Wuviations, moderate deviations and LIL for empirical processes. Ann. Probab. 22 (1994) 17–27.