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.


1 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.

  • $\begingroup$ Thank you very much for the clear answer! $\endgroup$
    – Seven9
    Jan 18, 2021 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.