Large and Moderate Deviations for Matching Problems and Empirical Discrepancies
2007, v.13, №1, 85-98
We study the two-sample matching problem and its connections with the Monge - Kantorovich problem of optimal transportation of mass. We exploit this connection to obtain moderate and large deviation principles. For the classical problem on the unit square we present a conjecture which, if true, yields an explicit formula for the rate function.
Keywords: matching problems,empirical processes,empirical discrepancies,large deviations,marriage lemma,Monge - Kantorovich problem