# Hausdorff distance is a lower (or upper bound) for what probability metric?

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$$.

# Question

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

# Edit

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.

• I guess the $L^\infty$ Wasserstein distance? – Anthony Quas Sep 8 '18 at 20:06
• @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 – dohmatob Sep 10 '18 at 8:35
• "On Choosing and Bounding Probability Metrics" and "Hausdorff metric structure of the space of probability distributions" – 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\})$.

• 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. – dohmatob Sep 10 '18 at 0:11
• 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). – Martin Kell Sep 10 '18 at 8:19
• Okay (upvoted). – dohmatob Sep 10 '18 at 8:32
• I wonder whether your examples work in a Polish space... – dohmatob Sep 10 '18 at 8:37
• 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... – dohmatob Sep 10 '18 at 9:53