Let $\mathcal X$ be a Polish space, and let $(N\_x)\_{x \in \mathcal X}$ be a system of closed neighborhoods in $\mathcal X$. Define $\Omega := \{(x,x') \in \mathcal X^2 \mid N\_x \cap N\_{x'} = \emptyset\}$, assumed to be open in $\mathcal X^2$. For example in a Banach space $\mathcal X$, an example would be $N\_x = x + \varepsilon\mathbb B$ with $\varepsilon > 0$, and this would lead to $\Omega := \{(x,x') \in \mathcal X^2 \mid \|x-x'\| > 2\varepsilon\}$.


Now, let $\mu$ and $\nu$ be probability measures, and consider the quantity $c\_\Omega(\mu,\nu)$ defined by


$$
c\_\Omega(\mu,\nu) := \inf\_{\gamma \in \Pi(\mu,\nu)}\gamma(\Omega).
$$
This is nothing but the transportation distance between $\mu$ and $\nu$, for the binary ground cost given by $c\_\Omega(x,x') = 1$ if $(x,x') \in \Omega$; 
$c\_\Omega(x,x') = 0$ else.


Finally, define
$$
d\_N(\mu,\nu) := \inf\_{a\_1, a\_2} \text{TV}({a\_1}\_{\#}\mu,{a\_2}\_{\#}\nu),
$$
where the infimum is take over all measurable $a\_1, a\_2:\mathcal X \rightarrow \mathcal X$ such that $a\_1(x), a\_2(x) \in N\_x$ for all $x \in \mathcal X$, and $a\_{\#}\mu$ denotes the *pushforward* of $\mu$ under $a$


Question
========


* Is there any relationship (equality, inequality, etc.) between $c\_\Omega(\mu,\nu)$ and $d\_N(\mu,\nu)$ ?


Observations
============


By *data-processing inequality*, $\text{TV}(a\_{\#}\mu,a\_{\#}\nu) \le \text{TV}(\mu,\nu)$ and so $d\_N(\mu,\nu) \le \text{TV}(\mu,\nu)$.



Relationship between a certain binary optimal transport and total-variation of modified distributions

> 
> **Claim.** Let us define a relaxation of $d\_N$ as $\tilde d\_N(\mu,\nu)=\inf\_{\gamma\_a,\gamma\_b} TV(\pi^2\_\#\gamma\_a,\pi^1\_\#\gamma\_b)$ subject to $\pi^1\_\# \gamma\_a = \mu$ and $\pi^2\_\# \gamma\_b =\nu$ and $\gamma\_a,\gamma\_b$ are concentrated on $D\_\epsilon = \{(x,x')\in \mathcal{X}^2; \Vert x-x'\Vert\leq \epsilon\}$ (here $\pi^i$ is the projection on the $i$-th factor of $\mathcal{X}^2$). Then it holds
>  $$
> 2 c\_{\Omega}(\mu,\nu) = \tilde d\_N(\mu,\nu) \leq d\_N(\mu,\nu) \tag{1},
> $$
> 
> 
> 


where the inequality is an equality if $\mu$ and $\nu$ are absolutely continuous, but might be strict otherwise (e.g. on the real line, $\mu=\frac13 \delta\_{-2\epsilon}+\frac13 \delta\_{0}+\frac13 \delta\_{2\epsilon}$ and $\nu=\frac12 \delta\_{-\epsilon}+\frac12 \delta\_\epsilon$ has $d\_N(\mu,\nu)=2/6$ and $\tilde d\_N(\mu,\nu)=0$). 


**Proof.** The constructions are a bit tedious to describe, so I will not go through every detail. We consider the intermediate quantity 
$$
E(\mu,\nu):=\inf\_{\gamma\in \Pi\_{\leq}(\mu,\nu)\\ \mathrm{spt}(\gamma)\subset D\_{2\epsilon}} 1 - \gamma(\mathcal{X}^2) \tag{2}
$$
where $\Pi\_{\leq}$ denotes the set of partial transport plans, i.e. probabilities on $\mathcal{X}^2$ with marginals smaller than $\mu$ and $\nu$ respectively.


First, let us show that $c\_\Omega=E$. Let $\gamma \in \Pi(\mu,\nu)$ and let $\tilde \gamma$ be its restriction to $D\_{2\epsilon}$. Then $\tilde \gamma$ is feasible for $E$ and it holds $\gamma(\Omega)=1-\tilde\gamma(\mathcal{X^2})$ so $E\leq c\_\Omega$. Conversely, let $\gamma$ be feasible for $E$ and consider any $\tilde \gamma\in \Pi(\mu-\pi^1\_\#\gamma, \nu-\pi^2\_\#\gamma)$. Then $\gamma +\tilde \gamma$ is feasible for $c\_\Omega$ and $(\gamma+\tilde \gamma)(\Omega)= \tilde \gamma(\Omega)\leq \tilde \gamma(\mathcal{X^2}) = 1-\gamma(\mathcal{X}^2)$ so $c\_\Omega\leq E$ and thus $c\_\Omega=E$.


Let us show now that $E=\tilde d\_N$. Consider the maps $T\_a,T\_b,D$ defined by $$T\_a(x,y)=(x,(x+y)/2),\quad T\_b(x,y)=((x+y)/2,y),\quad D(x)=(x,x).$$ Let $\gamma$ be feasible for $E$ and consider $\gamma\_a = (T\_a)\_\# \gamma + D\_\# (\mu-\pi^1\_\#\gamma)$ and $\gamma\_b = (T\_b)\_\# \gamma + D\_\# (\nu-\pi^2\_\#\gamma)$. Then $(\gamma\_a,\gamma\_b)$ is feasible for $\tilde d$ and $TV(\pi^2\_\#\gamma\_a,\pi^1\_\#\gamma\_b)\leq (\mu-\pi^1\_\#\gamma)(\mathcal{X})+ (\nu-\pi^2\_\#\gamma)(\mathcal{X}) = 2(1-\gamma(\mathcal{X}^2))$ because the second marginal of $(T\_a)\_\# \gamma$ and the first marginal of $(T\_b)\_\# \gamma$ agree by construction. Thus $d\_N\leq 2E$. Conversely, let $\gamma\_a,\gamma\_b$ be feasible for $\tilde d\_N$, and let $\tilde \gamma\_a\leq \gamma\_a$ and $\tilde \gamma\_b\leq \gamma\_b$ be such that $\pi^2\_\#\tilde \gamma\_a = \pi^1\_\#\gamma\_b = (\pi^2\_\# \gamma\_a)\wedge (\pi^1\_\# \gamma\_b)$ where $\wedge$ is the "pointwise" minimum of two measures (they can be built with the disintegration theorem). Now build $\tilde \gamma$ feasible for $E$ by gluing together $\tilde \gamma\_a$ and $\tilde \gamma\_b$, see [1, Lem. 5.5]. It holds 
$$
TV(\pi^2\_\#\gamma\_a ,\pi^1\_\# \gamma\_b ) = 2(1-\pi^2\_\#\gamma\_a \wedge \pi^1\_\# \gamma\_b)(\mathcal{X}) = 2(1-\tilde \gamma(\mathcal{X}^2)) \tag{3}.
$$
Thus $2E\leq \tilde d\_N$ hence $2E=\tilde d\_N$.


The fact that $\tilde d\_N\leq d\_N$ in general is due to the fact to any transport map $a$ satisfying $\Vert a(x) -x\Vert\leq \epsilon$ corresponds a deterministic transport plan $(\mathrm{id}, a)\_\# \mu$ supported on $D\_\epsilon$. Finally, the fact that $\tilde d\_N=d\_N$ when $\mu$ and $\nu$ are absolutely continuous is a consequence of the existence of an optimal transport map for the $W\_\infty$ distance, see [1, Thm. 3.24]. Indeed, if $(\gamma\_a,\gamma\_b)$ is feasible for $\tilde d\_N$, then $W\_\infty(\mu,\pi^2\_\#\gamma\_a)\leq \epsilon$ and there exists a measurable map $a\_1:\mathcal{X}\to\mathcal{X}$ such that $\Vert a\_1(x)-x\Vert\leq \epsilon$ $\mu$-a.e. and $(a\_1)\_\# \mu = \pi^2\_\#\gamma\_a$ (one can build $a\_2$ similarly).


[1] *Santambrogio, Filippo*, [**Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling**](http://dx.doi.org/10.1007/978-3-319-20828-2)


