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?.
Let $X$ be a metric space. A probability measure on $X$ has finite first moment if
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
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
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.
More information on Wasserstein spaces can be found in Villani ‘08.
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
The maps $\delta$ and $E$ satisfy the usual axioms of a monad (see F-P ‘19), which is known as the Kantorovich monad.
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,
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
For more details, see F-P ‘19.
(…)
(Work in progress. For now see F-P ‘18.)
(…)
Kantorovich-Wasserstein distance, optimal transport?
Banach space, ordered Banach space?, convex space
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)
Last revised on May 18, 2020 at 12:58:29. See the history of this page for a list of all contributions to it.