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$


  • Is there any relationship (equality, inequality, etc.) between $c_\Omega(\mu,\nu)$ and $d_N(\mu,\nu)$ ?


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


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

  • $\begingroup$ Wow! Thanks very much for such a indepth answer. $\endgroup$ – dohmatob Sep 27 '19 at 12:57
  • $\begingroup$ BTW, we both agree that your arguments carry over to the case where $\Omega$ is constructed from a general system $N_x$, and no just balls. Right ? $\endgroup$ – dohmatob Sep 27 '19 at 12:58
  • $\begingroup$ You're welcome! I have worked with similar manipulations in relation to optimal partial transport. The argument extends to the general systems of closed neighborhoods, except that I am not sure that the existence of transport maps (last argument) has been proved in that setting. $\endgroup$ – Lénaïc Chizat Sep 29 '19 at 18:40
  • $\begingroup$ OK, thanks. Could you recommend any good refs on the subject of "optimal partial transport" ? $\endgroup$ – dohmatob Sep 29 '19 at 21:28
  • 1
    $\begingroup$ A good reference is Figalli's paper. By the way, in my answer I used the definition of TV-norm that coincides with L1 norm for densities (which is twice the TV-norm sometimes used by probabilists). $\endgroup$ – Lénaïc Chizat Sep 30 '19 at 7:25

Your Answer

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

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