1
$\begingroup$

I wonder whether this is true: If a distribution is very close (in the Wassertein sense) to another distribution with compact support, then the former must put only tiny amount of mass outside a neighborhood of the support of the latter.

More formally, let $\mu$ be a probability distributions on $\mathbb R^d$ whose support is a compact subset $A$ of $\mathbb R^d$. Recall that for $\epsilon > 0$, the $\epsilon$-blowup of $A$ is defined by $A_\epsilon := \{x \in \mathbb R^d | \operatorname{dist}(x, A) < \epsilon\}$, where $\operatorname{dist}(x, A) := \inf_{y \in A}\|x-y\|$.

Question

Does there exist constants $c_1,c_2 > 0$ such that for every $\epsilon \ge c_2$ and for every other distribution $\nu$ on $\mathbb R^d$ with $W(\mu,\nu) \le \epsilon$, it holds that $$\nu(A_\epsilon) \ge 1- \exp\left(-\frac{c_1^2\epsilon^2}{2}\right)? $$

Notes

Ultimately, I'm looking for anything of the form $\nu(A_\epsilon) \approx 1$. So even if the above Gaussian decreasing error turns out to be false, I'd be happy with something a bit slower (e.g exponential, etc.).

Some wild guesses

  • $c_1 \asymp \operatorname{diam}(A)$
$\endgroup$
5
  • 2
    $\begingroup$ This seems to be incorrect even for trivial distributions. If $\mu = \delta_x$ and $\nu = \delta_y$ where $|x-y|=\epsilon$, then $W(\mu,\nu) = \epsilon$ but $\nu(A_\epsilon) = 0$. $\endgroup$ Aug 15, 2018 at 21:53
  • 2
    $\begingroup$ On the other hand, the "earth moving" analogy suggests that $\nu(A_\delta) \ge 1- \epsilon/\delta$ should be elementary and essentially sharp? Here I am thinking of the $W_1$ distance, did you mean to use $W_1$ or some other $W_p$? $\endgroup$ Aug 15, 2018 at 21:57
  • $\begingroup$ The question is not very well stated. Sorry for the noise. Indeed, by the KR dual representation, $\epsilon \ge W_1(\mu,\nu) := \sup_{\|f\|_{\text{Lip}} \le 1} \mathbb | E_\nu f - \mathbb E_\nu f|$ should imply an inequality of the form you suggest (linear error term), and is essentially tight. $\endgroup$
    – dohmatob
    Aug 16, 2018 at 11:49
  • $\begingroup$ Okay, sounds good. It can also be proved directly from the "primal" definition of $W_1$, by the way. Would you like to post an answer, or shall I? $\endgroup$ Aug 16, 2018 at 13:20
  • $\begingroup$ Go ahead, and I'll up-vote it :). I'll make time and post another answer which gathers a bunch of tiny interesting things that can be said about the problem. $\endgroup$
    – dohmatob
    Aug 16, 2018 at 13:24

1 Answer 1

5
$\begingroup$

The claimed inequality is not true. The simplest possible counterexample works: let $x,y \in \mathbb{R}^n$ with $|x-y| = \epsilon$, and take $\mu = \delta_x$, $\nu = \delta_y$. Then $W_1(\mu,\nu) = \epsilon$. But $A = \{x\}$ and $y \notin A_\epsilon$, so $\nu(A_\epsilon) = 0$.

What is true is the following bound: for any $r > 0$, we have $$\nu(A_r) \ge 1 - r^{-1} W_1(\mu,\nu).$$ To see why, let $\eta$ be any coupling of $\mu$ and $\nu$. Then $$\begin{align*}\int_{\mathbb{R}^n \times \mathbb{R}^n} |x-y|\,\eta(dx,dy) &\ge \int_{A \times A_r^c} |x-y|\,\eta(dx,dy) \\ &\ge \int_{A \times A_r^c} r\,\eta(dx,dy) \\ &= r \eta(A \times A_r^c)\end{align*}$$ since $|x-y| \ge ra$ on $A \times A_r^c$ by definition of $A_r$.

Now since $A$ is the support of $\mu$, we have $\eta(A \times \mathbb{R}^n) = \mu(A) = 1$. Hence $$\begin{align*}\eta(A \times A_r^c) &= \eta((A \times \mathbb{R}^n) \cap (\mathbb{R}^n \times A_r^c)) \\ &= \eta(\mathbb{R}^n \times A_r^c) \\ &= \nu(A_r^c) \\ &= 1 - \nu(A_r). \end{align*}$$ We thus have $$\int_{\mathbb{R}^n \times \mathbb{R}^n} |x-y|\,\eta(dx,dy) \ge r(1-\nu(A_r)).$$ Taking the infimum over all couplings $\eta$ gives $W_1(\mu,\nu) \ge r(1-\nu(A_r))$ which is the desired inequality.

With the earth-moving interpretation, this just says that if the total haulage (in, say, tonne-meters) was $c$, then the amount that had to be moved at least $r$ meters must certainly be at most $c/r$ tonnes.

This bound is sharp, as can be seen by choosing $x,y$ with $|x-y| = r$, and taking $\mu = \delta_x$, $\nu = (1-\epsilon) \delta_x + \epsilon \delta_y$. Then $\nu(A_r)= 1-\epsilon$ while $W_1(\mu,\nu) = \epsilon r$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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