nLab Kantorovich monad

Idea

The Kantorovich monad is a probability monad on the category of complete metric spaces and 1-Lipschitz (or Lipschitz) maps. Its functor part assigns to each complete metric space $X$ the space of Radon probability measures with finite first moment, equipped with the Kantorovich-Wasserstein distance.

Its algebras are closed convex subsets of Banach spaces.

The construction was first given by van Breugel for the compact case (see vB ‘05).

There is an ordered version of the Kantorovich monad, making use of the stochastic order. Its algebras are closed convex subsets of ordered Banach spaces?.

Wasserstein spaces

Let $X$ be a metric space. A probability measure on $X$ has finite first moment if

$$\int_{X\times X} d(x,y) \, dp(x)\,dp(y) \;\lt\; +\infty,$$

where $d(-,-)$ denotes the distance.

Let $p$ and $q$ be Radon probability measures on $X$ of finite first moment. The Kantorovich-Wasserstein distance is given by

$$d(p,q) \;\coloneqq\; \inf_{r\in\Gamma(p,q)} \int_{X\times X} d(x,y) \,dr(x,y) ,$$

where the infimum (which is attained if $X$ is complete) is taken over the set $\Gamma(p,q)$ of couplings of $p$ and $q$, i.e. the measures on $X\times X$ which admit $p$ and $q$ as their marginals.

Equivalently, the distance can be written as

$$d(p,q) \;=\; \sup_{f\in[X,\mathbb{R}]} \int f\, dp - \int f\, dq,$$

where the supremum (which is usually not attained) is taken over the set of 1-Lipschitz functions $X\to \mathbb{R}$. (This equivalence is an instance of the celebrated Kantorovich duality?.)

The 1-Wasserstein space over $X$ is the space $P X$ of Radon probability measures on $X$ with finite first moment, equipped with the Wasserstein metric.

Properties

• If $X$ is complete, so is $P X$.

• If $X$ is separable, so if $P X$.

• If $X$ is compact, so is $P X$.

More information on Wasserstein spaces can be found in Villani ‘08.

Functor, unit and multiplication

As it is customary for probability monads, the functor assigns to a morphism $f:X\to Y$ (in this case, a Lipschitz or 1-Lipschitz map) the map $P f: P X \to P Y$ induced by the pushforward of measures. The pushforward of a Radon probability measure of finite first moment along a Lipschitz map is again Radon and of finite first moment. Moreover, the resulting map $P f$ is again Lipschitz, with the same Lipschitz constant as $f$. Therefore we have an endofunctor $P$ on the category of complete metric spaces and Lipschitz maps (or 1-Lipschitz).

Again, as it happens in general with probability monads, the unit $\delta:X\to P X$ is given by forming the Dirac measures and the multiplication $E:P P X\to P X$ is given by integration. More formally, given $\xi\in P P X$, the measure $E \xi\in PX$ is defined as the one which assigns to a Borel set $A\subseteq X$ the number

$$E \xi(A) \;\coloneqq\; \int p(A) \,d\xi(p) .$$

The maps $\delta$ and $E$ satisfy the usual axioms of a monad (see F-P ‘19), which is known as the Kantorovich monad.

Algebras

As it is the case for most probability monad, the algebras are convex spaces of a particular kind. For the Kantorovich monad, the objects of the underlying category are complete metric spaces, and so the closed convex subsets of Banach spaces are an ideal candidate: they are metric spaces, they are complete, and they have a well-defined convex combination operation. It turns out that this is exactly the case.

More in detail, every closed convex subset $A$ of a Banach space comes equipped with a map $e:P A\to A$ given by vector-valued integration,

$$p\;\mapsto\; \int a \,dp(a) .$$

The integral exists since $p$ has finite first moment. Conversely, it can be proven that every $P$-algebra is of this form.

The morphisms of algebras are maps between algebras $f:A\to B$ which commute with the integration map. It can be shown that equivalently these are exactly the affine maps, i.e.~those maps which satisfy

$$f\big(\lambda\,x + (1-\lambda)\,y\big) \;=\; \lambda\,f(x) + (1-\lambda)\,f(y).$$

For more details, see F-P ‘19.

Duality

(…)

The ordered case

(Work in progress. For now see F-P ‘18.)

For Lawvere metric spaces

(…)

See also

• monads of probability, measures, and valuations

• Giry monad, Radon monad, extended probabilistic powerdomain

• Kantorovich-Wasserstein distance, optimal transport?

• metric space, complete metric space

• Banach space, ordered Banach space?, convex space

References

• Franck van Breugel, The metric monad for probabilistic nondeterminism, unpublished, 2005. (pdf)

• Tobias Fritz and Paolo Perrone, A probability monad as the colimit of spaces of finite samples, Theory and Applications of Categories 34, 2019. (pdf)

• Tobias Fritz and Paolo Perrone, Stochastic order on metric spaces and the ordered Kantorovich monad, Advances in Mathematics 366, 2020. (arXiv:1808.09898)

• Cedric Villani, Optimal transport: old and new, Springer, 2008.

• Paolo Baldan, Filippo Bonchi, Henning Kerstan and Barbara König, Coalgebraic behavioral metrics, Logical Methods in Computer Science 14(3), 2018. (doi: 10.23638/LMCS-14(3:20)2018)