Monotone Transport Maps and Plans in 1D

In this article, we will introduce monotone transport maps and plans in 1D.

Definition 2.1 Given a nondecreasing and right continuous function $F:\mathbb{R}\to[0,1]$, its pseudo-inverse is the function $F^{[-1]}:[0,1]\to\overline{\mathbb{R}}$ given by
$$
F^{[-1]}(x)=\inf\{t\in\mathbb{R}\mid F(t)\ge x\}.
$$
Thanks to right continuity of $F$, the infimum is minimum as soon as the set is nonempty.

Lemma 2.1 We have

1. $F^{[-1]}(x)\le a \iff F(a)\ge x$,
2. $F^{[-1]}(x)>a \iff F(a)<x$.

Proof : We only prove (1). If $F^{[-1]}(x)\le a$, then the set
$$
\{t\in\mathbb{R}\mid F(t)\ge x\}\neq\varnothing
$$
and then the infimum is minimum. Suppose $F(a)<x$, then for each $b\le a$, $F(b)\le F(a)<x$, hence
$$
b\notin\{t\in\mathbb{R}\mid F(t)\ge x\}\Rightarrow (-\infty,a]\subset\{t\in\mathbb{R}\mid F(t)<x\}.
$$
Hence by definition, $F^{[-1]}(x)>a$, which gives a contradiction. Conversely, if $F(a)\ge x$, it is obvious that $F^{[-1]}(x)\le a$. $\square$

Proposition 2.1 If $\mu\in\mathcal{P}(\mathbb{R})$ and $F_\mu^{[-1]}$ is the pseudo-inverse of its cumulative distribution function $F_\mu$, then

$$
(F_\mu^{[-1]}) _{\sharp}\big(\mathcal{L}^1\llcorner[0,1]\big) =\mu.
$$

Moreover, given $\mu,\nu\in\mathcal{P}(\mathbb{R})$, if we set
$$
\eta:=\big(F_\mu^{[-1]},F_\nu^{[-1]}\big)_{\sharp}\big(\mathcal{L}^1\llcorner[0,1]\big),
$$
then $\eta\in\Pi(\mu,\nu)$ and
$$
\eta\big((-\infty,a]\times(-\infty,b]\big)=F_\mu(a)\wedge F_\nu(b).
$$

Proof :
$$
\mathcal{L}^1\big(\{x\in[0,1]\ ;\ F_\mu^{[-1]}(x)\le a\}\big)
=\mathcal{L}^1\big(\{x\in[0,1]\ ;\ x\le F_\mu(a)\}\big)=F_\mu(a).
$$
Hence
$$
\{(-\infty,a)\ ;\ a\in\mathbb{R}\}\subset \mathcal{G}:=\{A\in\mathcal{B}(\mathbb{R})\ ;\ (\mathcal{L}^1\llcorner[0,1])((F_\mu^{[-1]})^{-1}(A))=\mu(A)\}.
$$
By monotone class theorem, we get $\mathcal{G}=\mathcal{B}(\mathbb{R})$, which gives the desired result. Moreover $\eta\in\Pi(\mu,\nu)$ is just a consequence of the above statement.

Further,
$$
\eta((-\infty,a]\times(-\infty,b])
=\mathcal{L}^1\big(\{x\in[0,1]\ ;\ F_\mu^{[-1]}(x)\le a,\ F_\nu^{[-1]}(x)\le b\}\big)
$$
and by Lemma 2.1 this equals
$$
\mathcal{L}^1\big(\{x\in[0,1]\ ;\ x\le F_\mu(a),\ x\le F_\nu(b)\}\big)
=F_\mu(a)\wedge F_\nu(b),
$$
which is the desired equality. $\square$

Definition 2.2 We will call the transport plan

$$
\eta:=\big(F_\mu^{[-1]},F_\nu^{[-1]}\big) _{\sharp}\big(\mathcal{L}^1\llcorner[0,1]\big)
$$

the co-monotone transport plan between $\mu$ and $\nu$ and denote it by
$$
\gamma_{\mathrm{mon}}:=\eta.
$$

Lemma 2.2 If $\mu\in\mathcal{P}(\mathbb{R})$ is atomless, then $(F_\mu)_{\sharp}\mu=\mathcal{L}^1\llcorner[0,1]$. As a consequence, for every $\ell\in[0,1]$, the set $\{x:F_\mu(x)=\ell\}$ is $\mu$-negligible.

Proof : First, $F_\mu$ is continuous since $\mu$ is atomless. Hence for $a\in(0,1)$, the set
$$
\{x\ ;\ F_\mu(x)\le a\}=(-\infty,x_a],
$$
where $F_\mu(x_a)=a$. Hence
$$
\mu\big(F_\mu^{-1}((-\infty,a])\big)=\mu((-\infty,x_a])=F_\mu(x_a)=a.
$$
Therefore

$$
(F_\mu) _{\sharp}\mu=\mathcal{L}^1\llcorner[0,1].
$$

As a consequence, for $\ell\in[0,1]$, the set
$$
\{x\ ;\ F_\mu(x)=\ell\}
$$
is $\mu$-negligible. Otherwise, if
$$
\mu(\{x\ ;\ F_\mu(x)=\ell\})>0,
$$
then
$$
0=\mathcal{L}^1(\{\ell\})=(F_\mu)_{\sharp}\mu(\{\ell\})>0,
$$
which is a contradiction. $\square$

Theorem 2.1 Given $\mu,\nu\in\mathcal{P}(\mathbb{R})$, suppose that $\mu$ is atomless. Then there exists a unique nondecreasing map $T_{\mathrm{mon}}:\mathbb{R}\to\mathbb{R}$ such that
$$
(T_{\mathrm{mon}})_{\sharp}\mu=\nu.
$$

Proof : Define
$$
T_{\mathrm{mon}}(x):=F_\nu^{[-1]}(F_\mu(x)).
$$
By Lemma 2.2, it is easy to see that $T_{\mathrm{mon}}$ is well-defined. The fact that $T_{\mathrm{mon}}$ is monotone nondecreasing is obvious. Now, we only need to show $(T_{\mathrm{mon}})_{\sharp}\mu=\nu$.

In fact,

$$
(T_{\mathrm{mon}}) _{\sharp}\mu
=(F_\nu^{[-1]}\circ F_\mu) _{\sharp}\mu
=(F_\nu^{[-1]}) _{\sharp}\big((F_\mu) _{\sharp}\mu\big)
=(F_\nu^{[-1]}) _{\sharp}\big(\mathcal{L}^1\llcorner[0,1]\big)=\nu.
$$

Finally, we need to show the uniqueness. From monotonicity,
$$
T^{-1}((-\infty,T(x)])\supset (-\infty,x].
$$
We deduce
$$
F_\mu(x)=\mu((-\infty,x])\le \mu\big(T^{-1}((-\infty,T(x)])\big)
=\nu((-\infty,T(x)])=F_\nu(T(x)),
$$
which means
$$
T(x)\ge F_\nu^{[-1]}(F_\mu(x)).
$$
Suppose $T(x)>F_\nu^{[-1]}(F_\mu(x))$. This means there exists $\varepsilon_0>0$ such that
$$
F_\nu(T(x)-\varepsilon)\ge F_\mu(x)\qquad\text{for all }\varepsilon\in(0,\varepsilon_0).
$$
On the other hand, from
$$
T^{-1}((-\infty,T(x)-\varepsilon])\subset (-\infty,x],
$$
we get
$$
F_\nu(T(x)-\varepsilon)=\nu((-\infty,T(x)-\varepsilon])
=\mu\big(T^{-1}((-\infty,T(x)-\varepsilon])\big)\le \mu((-\infty,x])=F_\mu(x).
$$
Therefore
$$
F_\nu(T(x)-\varepsilon)=F_\mu(x)\qquad\text{for every }\varepsilon\in(0,\varepsilon_0).
$$
Thus $F_\nu(T(x)-\varepsilon)$ is the value that $F_\nu$ takes on an interval where it is constant. These intervals are countable, hence the values of $F_\nu$ on those intervals are also countable. We can call $\ell_i$ these values. As a consequence, the points $x$ where
$$
T(x)>F_\nu^{[-1]}(F_\mu(x))
$$
are contained in
$$
\bigcup_i \{x\ ;\ F_\mu(x)=\ell_i\},
$$
which is $\mu$-negligible. Thus, $T(x)=F_\nu^{[-1]}(F_\mu(x))$ $\mu$-a.e. $\square$

Lemma 2.3 Let $\gamma\in\Pi(\mu,\nu)$ be a transport plan between two measures $\mu,\nu\in\mathcal{P}(\mathbb{R})$. Suppose that it satisfies the property:
$$
(x,y),(x’,y’)\in\operatorname{Supp}(\gamma),\ x<x’ \Rightarrow y\le y’. \tag{1}
$$
Then we have $\gamma=\gamma_{\mathrm{mon}}$. In particular, there is a unique $\gamma$ satisfying (1). Moreover, if $\mu$ is atomless, then $\gamma=T_{\mathrm{mon}}$.

Proof : First, we need to prove
$$
\gamma((-\infty,a]\times(-\infty,b])=F_\mu(a)\wedge F_\nu(b).
$$
Consider
$$
A:=(-\infty,a]\times(b,+\infty),\qquad B:=(a,+\infty)\times(-\infty,b].
$$
Claim: It is not possible to have both $\gamma(A)>0$ and $\gamma(B)>0$.

Indeed, if not, $\gamma(A)>0$ and $\gamma(B)>0$, then for some $(x,y)\in A$ and $(x’,y’)\in B$ we have
$$
x<x’,\qquad y>y’,
$$
with $(x,y),(x’,y’)\in\operatorname{Supp}(\gamma)$, which contradicts (1). Therefore,
$$
\gamma((-\infty,a]\times(-\infty,b])
=\gamma\big(((-\infty,a]\times\mathbb{R})\setminus A\big)
\wedge
\gamma\big((\mathbb{R}\times(-\infty,b])\setminus B\big)
$$
and hence
$$
\gamma((-\infty,a]\times(-\infty,b])=F_\mu(a)\wedge F_\nu(b).
$$
Hence $\gamma=\gamma_{\mathrm{mon}}$.

Now, assume $\gamma$ is atomless, then we can define $I_x$ as the minimal interval such that
$$
\operatorname{Supp}(\gamma)\cap(\{x\}\times\mathbb{R})\subset \{x\}\times I_x.
$$
The assumption (1) shows that the interior of all these intervals are disjoint. There can be at most countable points such that $I_x$ is not singleton. Since $\mu$ is atomless, we can define a map $T$ such that $\gamma$ is concentrated on graph of $T$, $\mu$-a.e. By Theorem 2.1, $T=T_{\mathrm{mon}}$. $\square$

Reference

Santambrogio, Filippo. Optimal transport for applied mathematicians. Birkäuser, NY 55.58-63 (2015): 94.

The cover image of this article was taken in Sydney, Australia.