Let $X = (X,d)$ be a metric space (assumed to be Polish, if necessary), and $\Omega$ be a nonempty closed subset of $X \times X$ veryfing:

  • $\forall x,x' \in X, (x,x') \in \Omega$ iff $(x',x) \in \Omega$
  • $\forall x \in X, (x,x) \in \Omega$.

Let $\mu$ be a probability measure on $X$. Given a measurable subset $E$ of $X$ with $\mu(E) > 0$, define

$$ \overline{E} := \{x \in X \mid c(x, E) = 0\} = \{x \in X \mid E \cap N_x \ne\emptyset\}, $$

where $N_x := \{x' \in X \mid (x, x') \in \Omega\}$ is the 'neighborhood" of $x$.


I'm interested in lower bounds for $\mu(\overline{E})$ as a function of $\mu(E)$ and the size of the neigborhoods $N_x$.

Since these neighborhoods might have different sizes, by size one could mean one of

  • Average radius: $(1/2)\mathbb E_{x\sim\mu}\text{diam}(N_x)$
  • Minimum radius: $(1/2)\inf_{x \in X}\text{diam}(N_x)$
  • Maxium radius: $(1/2)\sup_{x \in X}\text{diam}(N_x)$
  • The "size" of $\Omega$
  • ...

N.B. Thanks for any input (insight, reformulation, reference, solution, etc.) that can make me make progress on the above problem.

Motivating example

Let $\varepsilon$ and consider the closed set $\Omega = \Omega_\varepsilon := \{(x,x') \in X^2 \mid d(x,x') \le \varepsilon\}$.

It is easy to check that in this case, we have

  • $N_x = \text{Ball}(x;\varepsilon) := \{x' \in X \mid d(x,'x) \le \varepsilon\}$, and so all different measures of the "size of $N_x$" evoked above are equal to $\varepsilon$.

  • $\overline{E} = E^\varepsilon := \{x \in X \mid d(x,E) \le \varepsilon\}$, the $\varepsilon$-blowup of $E$.

Thus $\mu(\overline{E}) = \mu(E^\varepsilon)$, which is completely controlled by the isoperimetric profile of $\mu$. For example if $X$ is a finite dimensional euclidean space and $\mu$ is the standard Gaussian distribution thereupon, then $\mu(\overline{E}) = \mu(E^\varepsilon) \ge 1 - e^{-\frac{1}{2}(\varepsilon-\varepsilon_0)^2}$ for all $\varepsilon \ge \varepsilon_0 := \sqrt{2\log(1/\mu(E))}$.

Some observations

Let $\mu$ and $\nu$ be nonnegative measures on $X$ such that $\int_X d(x,x_0) d\mu(x) < \infty$ and $\int_X d(x,x_0) d\nu(x) < \infty$ for some $x_0 \in X$.

Consider the quantity $t \in [0, 1]$ defined by

$$ t := \min_{\gamma \in \Pi(\mu,\nu)}\gamma(X^2\setminus \Omega) $$

It is not hard to see that $t$ is the optimal transport distance between $\mu$ and $\nu$, for the lower-semicontinuous binary transportation cost given by $c(x,x') = 1[\![(x,x') \not\in \Omega]\!]$. Indeed,

$$ \begin{split} OT_c(\mu,\nu) &:= \min_{\gamma \in \Pi(\mu,\nu)}\int_{X^2} c(x,x')d\gamma(x,x') = \min_{\gamma \in \Pi(\mu,\nu)}\int_{X^2\setminus\Omega} d\gamma(x,x')\\ &=\min_{\gamma \in \Pi(\mu,\nu)}\gamma(X^2\setminus\Omega) =: t \end{split} $$ Also note that $\Omega = \text{supp}(c) := \{(x,x') \in X^2 \mid c(x,x') = 1\}$.

Related questions


Your Answer

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

Browse other questions tagged or ask your own question.