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](https://www.math.u-psud.fr/~filippo/OTAM-cvgmt.pdf) 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.



Hausdorff distance is a lower (or upper bound) for what probability metric?
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\})$.


