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

Question

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

Answer 1

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