# 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 ?

• 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" – Thomas Kojar 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
• In order to be able to state your question in a Polish space you need to assign a metric. After thinking over night, I believe the second counterexample can be adjusted to any $\mu$. The idea is to exhaust a small ball around $x$ by open sets which become eventually dense but have arbitrary small $\mu$-measure (this is the sequence $x_n$). Picking some ball disjoint from the chosen one (this corrensponds to $x_1$), it's possible to get the same counterexample. – Martin Kell Sep 10 '18 at 8:51