nLab
Kantorovich monad

Contents

Context

Measure and probability theory

Functional analysis

(0,1)(0,1)-Category theory

Contents

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 XX 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 XX be a metric space. A probability measure on XX has finite first moment if

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

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

Let pp and qq be Radon probability measures on XX of finite first moment. The Kantorovich-Wasserstein distance is given by

d(p,q)inf rΓ(p,q) X×Xd(x,y)dr(x,y), 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 XX is complete) is taken over the set Γ(p,q)\Gamma(p,q) of couplings? of pp and qq, i.e. the measures on X×XX\times X which admit pp and qq as their marginals?.

Equivalently, the distance can be written as

d(p,q)=sup f[X,]fdpfdq, 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 XX\to \mathbb{R}. (This equivalence is an instance of the celebrated Kantorovich duality?.)

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

Properties

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:XYf:X\to Y (in this case, a Lipschitz or 1-Lipschitz map) the map Pf:PXPYP 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 PfP f is again Lipschitz, with the same Lipschitz constant as ff. Therefore we have an endofunctor PP on the category of complete metric spaces and Lipschitz maps (or 1-Lipschitz).

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

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

The maps δ\delta and EE 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 AA of a Banach space comes equipped with a map e:PAAe:P A\to A given by vector-valued integration,

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

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

The morphisms of algebras are maps between algebras f:ABf: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(λx+(1λ)y)=λf(x)+(1λ)f(y). 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

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)

Last revised on May 18, 2020 at 08:58:29. See the history of this page for a list of all contributions to it.