2
$\begingroup$

I am stuck on the following problem. I have a discrete distribution $\mu_0$ (it is actually an empirical distribution). I have some $\mu_i$ (again discrete, some empirical distribution). I have some bound on the Wasserstein distance $W_2(\mu_0, \mu_i).$ I now want to consider a simple mixture of $\mu_i,$ that is, $\nu=\sum\limits_{i=1}^{m}\lambda_i\mu_i$ where $\sum\lambda_i=1, \lambda_i>0.$

My goal is to bound $W_2^2(\mu_0, \nu).$ I felt that it would be easy to get a bound on $W_2^2(\mu_0, \nu)$ in terms of $W_2^2(\mu_0, \mu_i),$ but I am unable to prove anything. I want something like $$W_2^2(\mu_0, \nu)\le \sum \lambda_i^2 W_2^2(\mu_0, \mu_i).$$

This does not look terribly hard, but I am stuck. Can anyone please say if it is true or not? If anyone can give a simple demonstration of why this is true, it would be great.

$\endgroup$

1 Answer 1

6
$\begingroup$

$\newcommand\Ga{\Gamma}$ $\newcommand\ga{\gamma}$ $\newcommand\la{\lambda}$ Let $\Ga(\mu,\rho)$ denote the set of all measures with marginals $\mu$ and $\rho$. For each $i$, take any real $c_i>W_2(\mu_0,\mu_i)^2$, so that $$\int d(x,y)^2\ga_i(dx\times dy)<c_i$$ for some $\ga_i\in\Ga(\mu_0,\mu_i)$. Let $$\ga:=\sum_i\la_i\ga_i.$$ Then $\ga\in\Ga(\mu_0,\nu)$ and hence $$W_2(\mu_0,\nu)^2\le\int d(x,y)^2\ga(dx\times dy) =\sum_i\la_i \int d(x,y)^2\ga_i(dx\times dy)<\sum_i\la_i c_i.$$ Letting now $c_i\downarrow W_2(\mu_0,\mu_i)^2$ for each $i$ such that $W_2(\mu_0,\mu_i)^2<\infty$, we get $$W_2(\mu_0,\nu)^2\le\sum_i\la_i W_2(\mu_0,\mu_i)^2.$$


The inequality you proposed, $$W_2(\mu_0,\nu)^2\le\sum_{i=1}^k\la_i^2 W_2(\mu_0,\mu_i)^2,\tag{1}$$ cannot hold in general. Indeed, suppose that for some probability measure $\rho$ we have $0<W_2(\mu_0,\rho)<\infty$. Let $\mu_i:=\rho$ and $\la_i:=1/k$ for all $i=1,\dots,k$. Then $\nu=\rho$ and the left-hand side of (1) is a constant $>0$, whereas its right-hand side goes to $0$ as $k\to\infty$.

$\endgroup$
9
  • 1
    $\begingroup$ Thanks! Yes, I realised that we can not hope for $\lambda_i^2$ in the right hand side. I could finally get the result with $\lambda_i$ but your argument is neater. $\endgroup$
    – Raghav
    Feb 12, 2020 at 2:57
  • 2
    $\begingroup$ Also note that this argument works for any cost function! $\endgroup$
    – Dirk
    Feb 12, 2020 at 8:21
  • 1
    $\begingroup$ @Dirk : That's right. $\endgroup$ Jun 18, 2020 at 0:14
  • 1
    $\begingroup$ @Zorn'sLama : That's right. $\endgroup$ Jun 18, 2020 at 0:14
  • 1
    $\begingroup$ @Elbebe : No, I don't know any reference to this. You can cite MathOverflow questions and answers by click on the "cite" buttons below them. $\endgroup$ Oct 23, 2020 at 18:38

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.