Definition of Wasserstein distance through cumulative distribution

Question

Let $X$ and $Y$ be random variables on the same probability space. The $\infty$-Wasserstein distance between $X$ and $Y$ is defined as

$$d_{\infty}(X, Y) = \inf \|X_1 - Y_1\|_{L_{\infty}},$$

where the infimum is over all random variables $X_1$ and $Y_1$ with same distribution as $X$ and $Y$, respectively.

Let $F_X$ and $F_Y$ be the cumulative distributions of $X$ and $Y$. I need help proving that

$$d_{\infty}(X, Y) = \inf\{\epsilon > 0 : F_X(t - \epsilon) \leq F_Y(t) \leq F_X(t + \epsilon) \mbox{ for all } t \in \mathbb{R}\}$$

Can someone help me?

Reference: Aubrun and Szarek, Alice and Bob Meet Banach: The Interface of Asymptotic Geometric Analysis and Quantum Information Theory, pg 161.

Answer 1

$\newcommand\ep\epsilon\newcommand\R{\mathbb R}$Let $d:=d_\infty(X,Y)$, $\|\cdot\|:=\|\cdot\|_{L_\infty}$, $$E:=\{\ep>0\colon F_X(t-\ep)\le F_Y(t)\le F_X(t+\ep) \text{ for all } t \in \R\},$$ $$D:=\inf E.$$ We need to show that $d=D$.

Take any real $c>d$. Then for some random variables (r.v.'s) $X_1$ and $Y_1$ with the same distributions as $X$ and $Y$, respectively, we have $\|X_1-Y_1\|<c$ and hence $X_1-c<Y_1$ almost surely. So, for all real $t$ $$F_Y(t)=P(Y_1\le t)\le P(X_1-c\le t)=F_X(t+c)$$ and similarly $F_X(t-c)\le F_Y(t)$, so that $c\in E$ and hence $D\le c$, for any real $c>d$. So, $$D\le d.\tag{1}$$

On the other hand, let $$X_1:=F_X^{-1}(U)\quad\text{and}\quad Y_1:=F_Y^{-1}(U),$$ where $U$ is any r.v. uniformly distributed on the interval $(0,1)$ and $$F^{-1}(u):=\inf\{x\in\R\colon F(x)\ge u\}=\min\{x\in\R\colon F(x)\ge u\}$$ for any cumulative distribution function $F$ and any $u\in(0,1)$. Then $X_1$ and $Y_1$ have the same distributions as $X$ and $Y$, respectively. Take any $\ep\in E$. Then it is easy to see that $|F_X^{-1}(u)-F_Y^{-1}(u)|\le\ep$ for all $u\in(0,1)$, whence $\|X_1-Y_1\|\le\ep$. So, $d\le\|X_1-Y_1\|\le\ep$, for any $\ep\in E$. So, $$d\le\inf E=D.$$ In view of (1), we get $d=D$, as desired.