Matchings and the variance of Lipschitz functions
Institut de Mathématiques de Toulouse,
CNRS UMR 5219, Université Paul Sabatier, 31062 Toulouse Cedex 09, France; email@example.com
2 Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK.
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.
Mathematics Subject Classification: 60D05 / 60F10 / 26D10
Key words: Matching problem / large deviations / variance / spectral gap / Euclidean ball.
© EDP Sciences, SMAI, 2009