1
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\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$ – Thomas Kojar Sep 13 '18 at 18:49
3
$\begingroup$

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\})$.

$\endgroup$
  • $\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
  • $\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
  • $\begingroup$ 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. $\endgroup$ – Martin Kell Sep 10 '18 at 8:51

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.

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