Upper Bound on the Wasserstein Distance

Question

I'm interested to know if it's possible to construct an upper bound on the Wasserstein distance in terms of the Kolgomorov distance.

The Wasserstein distance can we written as $$W_{1}\left(F, G\right)=\int_{-\infty}^{\infty}\left|F(x)-G(x)\right| d x$$ for distribution functions $F$ and $G$.

suppose that I have access to an upper bound on the Kolgomorov distance, ie $$\sup_{x \in \mathbb{R}}|F(x) - G(x)| \le K$$ for some $K > 0$. Is it then possible to find a found a bound on $W_{1}\left(F, G\right)$?

This is the $L^1$ distance between the distribution functions: it's not the [Wasserstein distance](https://en.wikipedia.org/wiki/Wasserstein_metric). There are obvious bounds in both directions and they both hold--you cannot weaken them in general. So: is your question about the $L^1$ distance or is it about the actual Wasserstein distance? And if it is the latter, how do you account for the fact that the units of measurement of the sup norm (aka $L^\infty$ norm), or "Kolmogorov distance," differ from the units for the Wasserstein distance? — whuber, Jan 30 '20 at 21:56
The $W_1$ expression is the Wasserstein distance between two distributions. See [in section 2 of this paper](https://arxiv.org/pdf/1902.10709.pdf) for example. Regardless of what you want to call it, this is the expression I'm interested in. I'm not sure what you mean by the units being different. I'd just like to know if its possible to bound the expression for $W_1$ given the fact that I have a bound for the maximum distance between the distribution functions at any point. — doug, Jan 30 '20 at 22:32

whuber · Accepted Answer · 2020-01-30T23:03:43.473

There are no effective bounds except when $K=0.$ (When $K=0,$ $F=G$ everywhere and both distances are necessarily $0.$)

Denote the Kolmogorov metric by $|\quad|_\infty$ and the Wasserstein metric by $|\quad|_1.$ (This is standard notation in mathematics.)

Let $X$ be a random variable with a Bernoulli$(K)$ distribution and set $Y(\epsilon)=(1+\epsilon)X$ for any $\epsilon\ge 0.$ Let $F$ be the distribution function (CDF) of $X$ and $G(\epsilon)$ the distribution function of $Y(\epsilon).$

$F$ and $G(\epsilon)$ differ only on the interval $[1,1+\epsilon)$ where the former equals $1$ and the latter equals $1-K.$ Thus

$$|F-G(\epsilon)|_\infty = \sup\{0,|1 - (1-K)|\}=K\le K$$

for all such $\epsilon,$ satisfying the conditions of the question. But since

$$|F-G(\epsilon)|_1 = \int_1^{1+\epsilon}|1 - (1-K)| \mathrm{d}x = K\epsilon,$$

as $\epsilon$ ranges from $0$ upwards the possible Kolmogorov distances range from $0$ upwards. Thus the best possible bounds are $0$ and $\infty.$

Here's some intuition.

First, the Kolmogorov metric is a probability whereas the Wasserstein metric is expressed in units of $x,$ so the two metrics aren't even comparable. Since the latter can be arbitrarily large, we ought to suspect there is no upper bound.

Second, that thought suggests problems could arise by keeping the graphs of $F$ and $G$ within $K$ of each other (vertically) while somehow adjusting the area between them (the Wasserstein distance).

If we make $F$ and $G$ close everywhere except throughout a short interval where first one of them leaps upward and then, a little later (at higher values of $x$) the second leaps upward, this area can be made arbitrarily small.
But if we put a distance of $K$ between $F$ and $G$ over a wide range of $x,$ the area will be proportional to $K$ times that range, which can be made arbitrarily large.

The family of examples in this answer is one of the simplest that exhibits these behaviors, but it should be clear that many such families could be constructed. Unless severe restrictions are imposed on $F$ and $G,$ then, the same result will hold.

Upper Bound on the Wasserstein Distance

1 Answers1