The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
type: Item
instance of: scholarly article
title: The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
zbMATH Open document ID: 0809.60015
published in: The Annals of Probability
publication date: 1995-03-28T00:00:00Z
review text: Let \(X_ 1, \dots, X_ n\), \(X_ 1', \dots, X_ n'\) be \(2n\) independent variables, uniformly distributed over \([0,1]^ d\), with \(d \geq 3\). The transportation cost from \(X_ 1, \dots, X_ n\) towards \(X_ 1', \dots, X_ n'\) is \[ \theta : = \text{Min}_{\sigma \in S_ n} \frac1n \sum^ n_{i = 1} \varphi \left({X_ i - X_{\sigma (i)}' \over Kn^{-1/d}} \right), \] where \(S_ n\) denotes the \(n\)th symmetric group, \(K\) is a constant depending only upon \(d\), and \(\varphi\) is a convex function from \(\mathbb{R}^ d\) into \([0, \infty]\), null in 0. This work is devoted to prove the following tight result: Under the necessary condition that \(\{\varphi \leq t\}\) has Lebesgue measure greater than \(\text{Log} t\) for any \(t>0\), if \(\varphi\) verifies some mild regularity conditions, then \(\theta \leq 1\) with probability \(\geq 1 - Kn^{-2}\). This theorem extends previous results by Ajtai, Komlós, Tusnády, Leighton, Shor, Yukich, Rhee and the author himself, where the function \(\varphi\) was mainly the Euclidean norm or derived from it. The proof, based on a duality method, is hard, long, highly technical and involved.
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 681388
zbMATH Keywords: optimal matching
zbMATH Keywords: empirical uniform measure
zbMATH Keywords: transportation cost
author: Michel Talagrand
reviewed by: Jacques Franchi
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1176988735
OpenAlex ID: W2065673761
DOI: 10.1214/AOP/1176988735
Recommended article: Transport cost estimates for random measures in dimension one
Recommended article: Q5204143
Recommended article: Transportation Cost Inequalities for Diffusions Under Uniform Distance
Recommended article: On the Transport Dimension of Measures
Recommended article: Transportation cost inequalities for Wasserstein diffusions
Recommended article: On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
Recommended article: Central limit theorems for empirical transportation cost in general dimension
Recommended article: Transportation-cost inequality on path spaces with uniform distance
Recommended article: Transport inequalities and concentration of measure
description: scientific article; zbMATH DE number 681388