Probability theory
Scaling and non-standard matching theorems
Comptes Rendus. Mathématique, Volume 356 (2018) no. 6, pp. 692-695.

Consider the standard Gaussian measure μ on R2. Consider independent r.v.s (Xi)iN distributed according to μ, and an independent copy (Yi)iN of these r.v.s. We prove that, for some number C and N large, we have

(logN)2CEinfπiNd(Xi,Yπ(i))2C(logN)2,(1)
where the infimum is over all permutations π of {1,,N}. The striking point of this result is the factor (logN)2. Indeed, if instead of μ we consider the uniform distribution on the unit square, it is well known that the proper factor is logN. The upper bound was proved by Michel Ledoux (2017) [3].

Considérons une suite indépendente (Xi)iN de variables aléatoires distribuées comme la mesure gaussienne canonique μ sur R2 et une copie independente (Yi)iN de cette même suite. Pour une certaine constante universelle C et N2, nous avons les inégalités

(logN)2CEinfπiNd(Xi,Yπ(i))2C(logN)2(1)
où l'infimum est pris sur toutes les permutations π de {1,,N}. La borne supérieure a été prouvée par Michel Ledoux (2017) [3], qui conjecturait que l'inégalité (1) était correcte avec un facteur logN et non pas (logN)2. C'est précisement l'apparence de ce facteur (logN)2 qui est non standard.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2018.04.018
Talagrand, Michel 1

1 23, rue Louis-Pouey, 92800 Puteaux, France
@article{CRMATH_2018__356_6_692_0,
     author = {Talagrand, Michel},
     title = {Scaling and non-standard matching theorems},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {692--695},
     publisher = {Elsevier},
     volume = {356},
     number = {6},
     year = {2018},
     doi = {10.1016/j.crma.2018.04.018},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2018.04.018/}
}
TY  - JOUR
AU  - Talagrand, Michel
TI  - Scaling and non-standard matching theorems
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 692
EP  - 695
VL  - 356
IS  - 6
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2018.04.018/
DO  - 10.1016/j.crma.2018.04.018
LA  - en
ID  - CRMATH_2018__356_6_692_0
ER  - 
%0 Journal Article
%A Talagrand, Michel
%T Scaling and non-standard matching theorems
%J Comptes Rendus. Mathématique
%D 2018
%P 692-695
%V 356
%N 6
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2018.04.018/
%R 10.1016/j.crma.2018.04.018
%G en
%F CRMATH_2018__356_6_692_0
Talagrand, Michel. Scaling and non-standard matching theorems. Comptes Rendus. Mathématique, Volume 356 (2018) no. 6, pp. 692-695. doi : 10.1016/j.crma.2018.04.018. http://www.numdam.org/articles/10.1016/j.crma.2018.04.018/

[1] Ajtai, M.; Komlós, J.; Tusnády, G. On optimal matchings, Combinatorica, Volume 4 (1984) no. 4, pp. 259-264

[2] Ambrosio, L.; Stra, F.; Trevisan, D. A PDE approach to a 2-dimensional matching problem, Probab. Theory Relat. Fields (2016) (in press)

[3] Ledoux, M. On optimal matching of Gaussian samples, Zap. Nauč. Semin. POMI, Volume 457 (2017) (Veroyatnost' i Statistika 25 226–264)

[4] Talagrand, M. Upper and Lower Bounds for Stochastic Processes http://michel.talagrand.net/ULB.pdf (new edition in preparation, available at)

[5] Yukich, J. Some generalizations of the Euclidean two-sample matching problem, Probability in Banach Spaces, 8, Progress in Probability, vol. 30, Birkhäuser, 1992, pp. 55-66

Cited by Sources: