1
$\begingroup$

Suppose $\mu=\sum_{i=1}^k p_i\delta_{x_i}$ and $\mu'=\sum_{i=1}^k p_i'\delta_{x_i'}$ are two atomic probability measures. Let $W_r(\mu,\mu')$ be the Wasserstein distance between $\mu$ and $\mu'$. Are there any known bounds of the form $$ \sup_i\inf_j|p_i-p_j'| \le C\cdot W_r(\mu,\mu') $$

for some constant $C$ that may depend on quantities such as the number of atoms $k$? It is not hard to prove such a bound for the largest difference between the atoms $\sup_i\inf_jd(x_i,x_j')$, however, I am not sure if it is possible to derive something similar for the probabilities.

Another more concrete perspective: If $W_r(\mu_n,\mu')\to0$ and $\mu_n,\mu'$ all have exactly $k$ atoms, then it is a standard result that there are permutations $\pi_n$ such that $x_{\pi_n(i),n}\to x_i'$ and $p_{\pi(i),n}\to p_i'$. Now suppose $W_r(\mu_n,\mu')\le r_n$ for some sequence $r_n>0$. Does it follow that the rate of convergence of the probabilities is also $r_n$? This is easy to show for the atoms, but I am not sure about the probabilities.

$\endgroup$
  • $\begingroup$ I'm not quite sure I understand the question. Say I take $x_1 = 1, x_2 = 17$, and $x_1' = 42, x_2' = 1+\epsilon$, with $p_1 = 1, p_2 = 0, p_1'=0, p_2'=1$? Then $\mu = \delta_1$ and $\mu' = \delta_{1+\epsilon}$, so that the Wasserstein distance tends to 0, but $|p_1-p_1'| = |p_2-p_2'|=1$ so the LHS of your proposed inequality seems to just be 1. $\endgroup$ – Nate Eldredge May 17 '18 at 0:53
  • $\begingroup$ A thing to keep in mind is that Wasserstein distance is a metric for weak convergence, and not for total variation convergence. So you can't omit all consideration of the distances between the atoms. $\endgroup$ – Nate Eldredge May 17 '18 at 0:55
  • $\begingroup$ @NateEldredge Sorry, this should all be up to some permutation (or alternatively, use the Hausdorff metric on the two sets of probabilities). I clarified this above. In your example, the LHS is now zero. Also, it is okay if the upper bound depends on the distance between the atoms. $\endgroup$ – JohnA May 17 '18 at 1:09
  • $\begingroup$ How about $\mu = \delta_0$, $\mu' = \frac{1}{2} \delta_{-\epsilon} + \frac{1}{2} \delta_{\epsilon}$? The LHS is $\frac{1}{2}$ and again the Wasserstein distance is arbitrarily small. $\endgroup$ – Nate Eldredge May 17 '18 at 1:44
  • 1
    $\begingroup$ So $\mu = \epsilon \delta_{17} + (1-\epsilon) \delta_0$ and $\mu'$ as before. $\endgroup$ – Nate Eldredge May 17 '18 at 2:12

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.