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.



Definition of Wasserstein distance through cumulative distribution
$\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.


