# On a certain measure concentration problem involving neighborhoods

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

# Question

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