In a metric space $X=(X, d)$, given a probability measure $\mu$ and two subsets $A$ and $B$ of positive measure, it's not hard to prove that

$$ d(A, B) \le W(\mu|_A, \mu|_B), $$ where

  • $d(A, B):= \inf_{a \in A,\;b \in B}d(x,y)$ is the distance between $A$ and $B$.
  • $\mu|_A$ defined by $\mu|_A(C):= \mu(A\cap C)/\mu(A)$ is the conditional measure induced by $A$
  • $W(\mu|_A,\mu|_B)$ is the Wasserstein distance between $\mu|_A$ and $\mu|_B$.

Now, consider the Hausdorff distance between $A$ and $B$, defined by $$ d_H(A,B) := \max\left(\sup_{b \in B}\inf_{a \in A}d(a,b),\sup_{a \in A}\inf_{b \in B}d(a,b)\right) = \inf\{\epsilon \ge 0 | A \subseteq B^\epsilon \text{ and } B\subseteq A^\epsilon\}, $$ where $A^\epsilon := \{x \in X | \exists a \in A\text{ with }d(a,x)\le \epsilon\} = \cup_{a \in A}\operatorname{Ball}_\epsilon(a)$ is the $\epsilon$-blowup of $A$.


Is $d_H(A,B)$ a lower bound (or upper bound) for some probability metric ? Which one ? Between what and what ?


A user mentioned "$L^\infty$ Wasserstein distance" in the comments. This comment seems to have gone unnoticed until now. Indeed, Exercise 36 of OTAM asks to prove that $d_H(supp(\mu),supp(\nu)) \le W_\infty(\mu,\nu)$ for every pair of measures $\mu$ and $\nu$ on a Polish space. This solves one half of my question. The other half has been solved (in the negative) by another user.

  • 2
    $\begingroup$ I guess the $L^\infty$ Wasserstein distance? $\endgroup$ – Anthony Quas Sep 8 '18 at 20:06
  • $\begingroup$ @ThomasKojar Both of your links are broken: the first one basically points to a book in a bookshop, while the 2nd yields a 404... I think I know about the second one. A link that works is: math.hmc.edu/~su/papers.dir/metrics.pdf $\endgroup$ – dohmatob Sep 10 '18 at 8:35
  • $\begingroup$ "On Choosing and Bounding Probability Metrics" and "Hausdorff metric structure of the space of probability distributions" $\endgroup$ – OOESCoupling Sep 13 '18 at 18:49

A general note is that the answer depends heavily on the properties of $\mu$.

First a note that in general $d_H(A,B) \not \le C \cdot W_p(\mu|_A,\mu|_B)$ for $p\in[1,\infty)$ and some $C>0$. Though it's true for the case $p = \infty$. Here the example: Let $\mu_\lambda = (1-\lambda) \delta_x + \lambda \delta_y$ for distinct $x,y \in X$. Choose $A=\{x\}$ and $B=\{x,y\}$. Then $\mu_\lambda|_A$ is $\delta_x$ and $\mu_\lambda|_B$ is $\mu_\lambda$. Thus $d_H(A,B) = d(x,y)$ and $W_p(\mu|_A,\mu|_B) = \lambda^{\frac{1}{p}}d(x,y)$.

For the case $p=\infty$, i.e. $W_\infty(\mu,\nu) = \inf \|d\|_{L^\infty(\pi)} $, it is true.

But there is no lower bound for the Hausdorff distance $d_H(\cdot,\cdot)$ w.r.t. to any Wasserstein distance $W_p$ if there is at least one non-isolated point (as $W_p \le W_\infty$ it suffices to get counterexamples for $p=\infty$).

Choose $x_n \to x$ and $\mu = \frac{1}{2}\delta_x + \sum_{n\in \mathbb{B}} \lambda_n \delta_{x_n}$ for some $\lambda_n \ge 0$ with $\sum_{n\in \mathbb{B}} \lambda_n = \frac{1}{2}$. Assume, in addition, $\lambda_1 > 2 \lambda_n$ for $n>1$. Now Choose $A = \{x, x_1\}$ and $B_n = \{x_n,x_1\}$. Then $d_H(A,B_n) = d(x,x_n) \to 0$. However, $W_\infty(\mu|_A, \mu|_{B_n}) \ge \inf \{d(x,x_1),d(x_n,x_1)\}$ because $\mu|_A(\{x\}) > \frac{1}{2} > \mu|_{B_n}(\{x_n\})$.

  • $\begingroup$ Your counter example is plane wrong, since in fact $d(A,B) := \inf_{a \in A,\; b \in B}d(a,b) \le d(x,x) = 0$. BTW, my claim is true, and an elementary proof is as follows: every joint distribution with $\mu|_A$ and $\mu|_B$ as marginals must be supported on $A \times B$ (do your see why ?). Therefore for every $p \in [1,\infty)$, by the very definition of $W_p$, one has $W_p^p(\mu|_A,\mu|_B) := \inf_{\pi \in \Pi(\mu|_A,\mu|_B)}\int_{X\times X}d(x,y)^pd\pi(x,y) = \inf_{\pi \in \Pi(\mu|_A,\mu|_B)}\int_{A \times B}d(x,y)^pd\pi(x,y) \ge d(A,B)^p$. Thus $W_p(\mu|_A,\mu|_B) \ge d(A,B)$ as claimed. $\endgroup$ – dohmatob Sep 10 '18 at 0:11
  • $\begingroup$ Sorry, it's just a typo. It should have been $d_H$. Answer is now adjusted. The examples show that there can be neither upper nor lower bounds for d_H w.r.t. to the Wasserstein distances (except for $p=\infty$ with the natural upper bound). $\endgroup$ – Martin Kell Sep 10 '18 at 8:19
  • 1
    $\begingroup$ Okay (upvoted). $\endgroup$ – dohmatob Sep 10 '18 at 8:32
  • $\begingroup$ I wonder whether your examples work in a Polish space... $\endgroup$ – dohmatob Sep 10 '18 at 8:37
  • 1
    $\begingroup$ What do you mean by "you need to assign a metric" ? Note that in the context of the above question, Polish would mean the space is complete and separable. I have a feeling your counter-examples would fail here, but I may be wrong... $\endgroup$ – dohmatob Sep 10 '18 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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