Let $x\_1,\dots,x\_n,y\_1,\dots,y\_n\in \mathbb{R}$ and such that $x\_i\neq x\_j$ and $y\_i\neq y\_j$ if $i\neq j$. Let $a,b$ be elements of the probability n-simplex. Define the measures $\mu\triangleq \sum\_{i=1}^n a\_i \delta\_{x\_i}$ and $\nu\triangleq \sum\_{i=1}^n b\_i \delta\_{y\_i}$. Are there known, (not too lax) upper-bounds for
$$
W\_p(\mu,\nu) \leq M\left(x\_1,\dots,x\_n,y\_1,\dots,y\_n,a,b\right)
$$
for some continuous function $M$; known in closed-form such that
$$
M(x\_1,\dots,x\_n,x\_1,\dots,x\_n,a,b)=0.
$$


Where $W\_p$ is the Wasserstein-1 distance, for some $1\leq p<\infty$?



Closed-form upper-bounds for Wasserstein distance between finite measures
Let
$$F(x):=\mu((-\infty,x])=\sum\_i a\_i\,1(x\_i\le x)
=\sum\_{j=1}^n s\_j\,1(x\_{n:j}\le x<x\_{n:j+1}),$$
where $x\_{n:1}<\cdots<x\_{n:n}$ are the values $x\_1,\dots,x\_n$ put in the increasing order (with $x\_{n:n+1}:=\infty$),
$$s\_j:=\sum\_{i=1}^j a\_{n:i},$$
and $a\_{n:1},\dots,a\_{n:n}$ are the values $a\_1,\dots,a\_n$ put in the increasing order of the $x\_k$'s, so that, if $x\_{n:i}=x\_k$ for some $k$, then $a\_{n:i}=a\_k$.
So, $F$ is the cdf of the probability measure $\mu$. Similarly considered is the function $G$ defined as the cdf of the probability measure $\nu$.


Consider then the generalized inverse/quantile function $F^{-1}\colon(0,1)\to\mathbb R$ defined by
$$F^{-1}(u):=\inf\{x\in\mathbb R\colon F(x)\ge u) \\
=\max\{x\in\mathbb R\colon F(x)\ge u) \\
=\sum\_{j=1}^n x\_{n:j}\,1(s\_{j-1}<u\le s\_j)$$
for $u\in(0,1)$, with the similarly defined and considered $G^{-1}$. Let $U$ be a random variable (r.v.) uniformly distributed on $(0,1)$. Then the distributions of the r.v.'s $X:=F^{-1}(U)$ and $Y:=G^{-1}(U)$ will be $\mu$ and $\nu$, respectively. Finally, let
$$M(x\_1,\dots,x\_n,y\_1,\dots,y\_n,a,b):=M(\mu,\nu) \\ 
:=(E|X-Y|^p)^{1/p}
=\Big(\int\_0^1|F^{-1}(u)-G^{-1}(u)|^p\,du\Big)^{1/p}.$$
Then
$$W\_p(\mu,\nu)\le M(x\_1,\dots,x\_n,y\_1,\dots,y\_n,a,b)$$
and  

$$M(x\_1,\dots,x\_n,x\_1,\dots,x\_n,a,a)=0,$$
as desired.




---


*Remark:* The upper bound $M(\mu,\nu)$ given above is actually the exact value of the Wasserstein distance for $p\ge1$, according to the last sentence of [Theorem 2.1](http://www.math.cmu.edu/%7Emthorpe/OTNotes) -- thank you alesia for this reference.


