Wasserstein distance between two empirical measures

inequalityoptimal-transportprobability theory

Suppose that $\{X_i\}_{1\leq i\leq N}$ and $\{Y_i\}_{1\leq i\leq N}$ are $\mathbb{R}$-valued random variables. I found in some manuscripts the inequality $$\mathbb{E}\left[W^2_2\left(\frac{1}{N}\sum_{i=1}^N \delta_{X_i}, \frac{1}{N}\sum_{i=1}^N \delta_{Y_i}\right)\right] \leq \mathbb{E}\left[\frac{1}{N}\sum_{i=1}^N |X_i-Y_i|^2\right] \quad (*).$$ I believe this is not that obvious… May I know how can one justify this upper bound on the squared Wasserstein distance (with exponent $2$)?

Best Answer

First proof the "deterministic" case $$W^2_2\left(\frac{1}{N}\sum_{i=1}^N \delta_{x_i}, \frac{1}{N}\sum_{i=1}^N \delta_{y_i}\right)\leq \frac{1}{N}\sum_{i=1}^N |x_i-y_i|^2 \qquad (**)$$.

This is easy by the definition of the Wasserstein distance as infimum of costs of transport plans (=couplings) between the measures $\mu:= \frac{1}{N}\sum_{i=1}^N \delta_{x_i}$ and $\nu:=\frac{1}{N}\sum_{i=1}^N \delta_{y_i}$ w.r.t. the cost function $c(x,y)=|x-y|^2$.

The right hand side of $(**)$ is exactly the cost $\int_{\mathbb{R} \times \mathbb{R}} c(x,y)\,\mathrm{d}\gamma(x,y)$ of the coupling $ \gamma := \frac{1}{N}\sum_{i=1}^N \delta_{(x_i,y_i)}$, i.e. you "transport" each $x_i$ to $y_i$.

Now, given random variable $X_1,\dots,X_N,Y_1,\dots,Y_N$ you just need to integrate both sides of $(**)$ w.r.t. the joint law of these RV to get $(*)$.

Answer to the question why $\frac{1}{N}\sum_{i=1}^N \delta_{(x_i,y_i)}$ is a valid coupling:

One has to show that the pushforward of $\frac{1}{N}\sum_{i=1}^N \delta_{(x_i,y_i)}$ unter the projection on the $x$-component is $\frac{1}{N}\sum_{i=1}^N \delta_{x_i}$ (and an analouge statement for the $y$-component). For each $A \subset \mathbb{R}$ measureable it holds $$\frac{1}{N}\sum_{i=1}^N \delta_{(x_i,y_i)}(A \times \mathbb{R}) = \frac{1}{N} \Big[\text{number of $i$ s.t. $x_i \in A$ }\Big] = \frac{1}{N}\sum_{i=1}^N \delta_{x_i}(A) $$.

Related Question