1–LABEL:LastPageFeb. 24, 2018Sep. 14, 2018

# Free Complete Wasserstein Algebras

Radu Mardare  Department of Computer Science, Aalborg University
<EMAIL_ADDRESS>,  Prakash Panangaden  School of Computer Science, McGill
University<EMAIL_ADDRESS>and  Gordon D. Plotkin  Laboratory for
Foundations of Computer Science, School of Informatics, University of
Edinburgh<EMAIL_ADDRESS>
###### Abstract.

We present an algebraic account of the Wasserstein distances $W_{p}$ on
complete metric spaces, for $p\geq 1$. This is part of a program of a
quantitative algebraic theory of effects in programming languages. In
particular, we give axioms, parametric in $p$, for algebras over metric spaces
equipped with probabilistic choice operations. The axioms say that the
operations form a barycentric algebra and that the metric satisfies a property
typical of the Wasserstein distance $W_{p}$. We show that the free complete
such algebra over a complete metric space is that of the Radon probability
measures with finite moments of order $p$, equipped with the Wasserstein
distance as metric and with the usual binary convex sums as operations.

##  1\. Introduction

The denotational semantics of probabilistic programs generally makes use of
one or another monad of probability measures. In [16, 8], Lawvere and Giry
provided the first example of such a monad, over the category of measurable
spaces; Giry also gave a second example, over Polish spaces. Later, in [13,
12], Jones and Plotkin provided a monad of evaluations over directed complete
posets. More recently, in [10], Heunen, Kammar, et al provided such a monad
over quasi-Borel spaces.

Metric spaces (and nonexpansive maps) form another natural category to
consider. The question then arises as to what metric to take over probability
measures, and the Kantorovich-Wasserstein, or, more generally, the Wasserstein
distances of order $p>1$ (generalising from $p=1$), provide natural choices. A
first result of this kind was given in [2], where it was shown that the
Kantorovich distance provides a monad over the subcategory of 1-bounded
complete separable metric spaces.

One purpose of such monads is to make probabilistic choice operations
available, and so an algebraic account of the monads in terms of these
operations is of interest; we focus here on such results in the metric
context. Barycentric algebras axiomatise probabilistic choice. They have
binary convex combination operations $x+_{r}y$, for $r\in[0,1]$; one can think
of $x+_{r}y$ as choosing to continue with $x$ with probability $r$ and with
$y$ with probability $1-r$. The operations are required to obey appropriate
laws.

In this paper we show that the Wasserstein distance of order $p$ yields a
monad $P_{p}$ on the category of complete metric spaces and nonexpansive maps
and that this monad can be characterised as the free algebra monad for
barycentric algebras over complete metric spaces where the barycentric
operations are required to be nonexpansive and are subject to an appropriate
Wasserstein condition. The probability measures in $P_{p}(X)$ are required to
be Radon (equivalently, tight) and to have finite $p$-moment. The important
Kantorovich case of this result, where $p=1$, was essentially already
established in [6], as it is an immediate consequence of Theorem 5.2.1 there.

In [17] a somewhat different direction was taken where monads on (extended)
metric spaces are defined algebraically, using a quantitative analogue of
equational logic where equations give an upper bound on the distance between
two elements, and algebras are extended metric spaces equipped with
nonexpansive operations. One then seeks to characterise the action of the
monad on as wide a variety of spaces as possible.

This is part of a program begun in [17] to establish a quantitative algebraic
theory of effects in programming languages. In particular, in [17] we gave
axioms, parametric in $p$, for algebras equipped with probabilistic choice
operations and showed the free complete such algebras over a complete
1-bounded separable metric space X are the probability measures on $X$ with
the Wasserstein distance, equipped with the usual binary convex sum
operations. Comparing this result to the results in this paper and in [6], it
is worth remarking that probability measures on 1-bounded spaces automatically
have finite moments, and probability measures on separable complete spaces are
automatically Radon.

In Section 2, we discuss the Wasserstein distance, $W_{p}$ of order $p$
between probability measures on a metric space $X$. In Theorem 5 we show that
the distance is a metric on the Radon probability measures with finite moments
of order $p$. To do so, we make use of a result in [4] that the triangle
inequality holds for all probability measures if $X$ is separable. Here, and
throughout the paper, we reduce the general case to the separable case using a
lemma, due to Basso, which states that the support of any probability measure
on a metric space is separable.

Next, in Theorem 6 we show that if $X$ is complete then the Wasserstein metric
of order $p$ on the Radon probability measures with finite moments of order
$p$ is also complete and is generated by the probability measures with finite
support. To do this, we make use of the well-known result that if $X$ is
complete and separable then the Wasserstein metric of order $p$ on all
probability measures over $X$ with finite moments of order $p$ is also
complete and separable, being generated by the rational measures with finite
support in a countable basis of $X$ (see, e.g., [24, Theorem 6.18] and the
bibliographic discussion there). The section concludes with a side-excursion,
a discussion of weak convergence: Theorem 10 generalises the characterisation
of the topology induced by the Wasserstein metrics in terms of weak
convergence given by [24, Theorem 6.9] from complete separable spaces to all
complete spaces.

In Section 3 we discuss the algebraic aspect of these spaces. In particular,
in Theorem 16 we show that the Radon probability measures with finite moments
of order $p$ on a complete metric space $X$, equipped with the $W_{p}$ metric
and binary convex sums, form the free complete Wasserstein algebra of order
$p$ over $X$. To do this, we first characterise the free Wasserstein algebra
of order $p$ over a metric space; the characterisation follows
straightforwardly from the well-known characterisation of the free barycentric
algebra over a set as the natural such algebra on the finite probability
measures on the set. Having done so, we pass to the case of complete metric
spaces using a general theorem on completions of metric algebras, combined
with Theorem 6.

Finally, we discuss some loose ends. First, there is a certain disconnect
between our work and that of [17] in that here we use standard metric spaces,
whereas there the more general framework of extended metric spaces is employed
where distances can be infinite. We sketch how to bridge this disconnect at
the end of Section 3. Second, there are other natural algebraic approaches to
probability. Convex spaces are an algebraic formulation of finite convex
combinations $\sum_{i=1}^{n}r_{i}x_{i}$. Midpoint algebras have a midpoint
operation $x\oplus y$: one can think of $x\oplus y$ as providing a fair choice
between $x$ and $y$, and so being equivalent to $x+_{0.5}y$. We sketch how our
algebraic characterisation of the Wasserstein monads on complete metric spaces
can be rephrased in terms of either of these alternative approaches.

We affectionately dedicate this paper to Furio Honsell on the occasion of his
60th birthday.

##  2\. The Wasserstein distance

We begin with some technical preliminaries on Radon probability measures and
couplings and their support. For general background on probability measures on
topological and metric spaces see [7, 19]. By probability measure we mean a
Borel probability measure. Given such a probability measure $\mu$ on a
Hausdorff space $X$, we say that a Borel set $B$ is _compact inner regular
(for $\mu$)_ if:

$\mu(B)=\mathrm{sup}\\{\mu(C)\mid C\mbox{ compact},C\subseteq B\\}$

Then $\mu$ is _Radon_ if all Borel sets are compact inner regular for it, and
_tight_ if $X$ is compact inner regular for it (equivalently, if for any Borel
set $B$ and $\varepsilon>0$ there is a compact set $C$ such that
$\mu(B\backslash C)<\varepsilon$). Every Radon measure is tight, every tight
probability measure on a metric space is Radon, and every probability measure
on a separable complete metric space is tight.

The _support_ of a probability measure $\mu$ on a topological space $X$ is

$\mathrm{supp}(\mu)=_{\mathbf{def}}\\{x\in X\mid\mu(U)>0\mbox{ for all open
$U$ containing $x$}\\}$

Note that the support is always a closed set. If $\mu$ is Radon then
$\mathrm{supp}(\mu)$ has measure 1. If the support of $\mu$ is finite then
$\mu$ is Radon and can be written uniquely, up to order, as a finite convex
sum of Dirac measures, viz:

$\mu=\sum_{s\in\mathrm{supp}(\mu)}\mu(s)\delta(s)$

(writing $\mu(s)$ instead of $\mu(\\{s\\})$). We say that $\mu$ is _rational_
if all the $\mu(s)$ are.

The following very useful lemma is due to Basso [1]. It enables us, as he did,
to establish results about probability measures on metric spaces by applying
results about probability measures on separable metric spaces to their
supports.

######  Lemma 1.

Every probability measure on a metric space has separable support.

######  Proof 2.1.

Let $\mu$ be a probability measure on a metric space. For every
$\varepsilon>0$ let $C_{\varepsilon}$ be a maximal set of points in
$\mathrm{supp}(\mu)$ with the property that all points are at distance
$\geq\varepsilon$ apart. As any two open balls with centre in
$C_{\varepsilon}$ and radius $\frac{1}{2}\varepsilon$ are disjoint and each
such ball has $\mu$-measure $>0$, $C_{\varepsilon}$ is countable (were it
uncountable, we would have an uncountable collection of reals with any
denumerable subset summable, and no such collection exists). By the maximality
of $C_{\varepsilon}$, any point in $\mathrm{supp}(\mu)$ is at distance
$<\varepsilon$ from some point in $C_{\varepsilon}$. It follows that the
countable set $\bigcup_{n\geq 0}C_{2^{-n}}$ is dense in $\mathrm{supp}(\mu)$.

A _coupling_ $\gamma$ between two probability measures $\mu$ and $\nu$ on a
topological space $X$ is a probability measure on $X^{2}$ whose left and right
marginals (= pushforwards along the projections) are, respectively, $\mu$ and
$\nu$. We gather some facts about such couplings:

######  Lemma 2.

Let $\gamma$ be a coupling between two probability measures $\mu$ and $\nu$ on
a topological space $X$. Then:

$\mathrm{supp}(\gamma)\subseteq\mathrm{supp}(\mu)\times\mathrm{supp}(\nu)$

Further, if $\mu$ and $\nu$ are tight, so is $\gamma$. Moreover, in the case
that $X$ is a metric space, if $\mu$ and $\nu$ are Radon, so is $\gamma$.

######  Proof 2.2.

For the first part, suppose that $(x,y)\in\mathrm{supp}(\gamma)$ and let $U$
be an open neighbourhood of $x$. Then $U\times Y$ is an open neighbourhood of
$(x,y)$ and so $\mu(U)=\gamma(U\times Y)>0$. So $x\in\mathrm{supp}(\mu)$.
Similarly $y\in\mathrm{supp}(\nu)$.

For the second part, choose $\varepsilon>0$. As $\mu$ and $\nu$ are tight, $X$
and $Y$ are compact inner regular for them. So there are compact sets
$C\subseteq X$ and $D\subseteq Y$ such that $\mu(X\backslash
C)<\frac{1}{2}\varepsilon$ and $\nu(Y\backslash D)<\frac{1}{2}\varepsilon$.
Then we have:

$\begin{array}[]{lcl}\gamma((X\times Y)\backslash(C\times
D))&=&\gamma((X\times Y)\backslash((C\times Y)\cap(X\times D)))\\\
&=&\gamma(((X\times Y)\backslash(C\times Y))\cup((X\times Y)\backslash(X\times
D)))\\\ &=&\gamma(((X\backslash C)\times Y)\cup(X\times(Y\backslash D)))\\\
&\leq&\gamma((X\backslash C)\times Y)+\gamma(X\times(Y\backslash D))\\\
&=&\mu(X\backslash C)+\nu(Y\backslash D)\\\ &<&\varepsilon\end{array}$

So, as $\varepsilon$ was arbitrary, $X\times Y$ is compact inner regular for
$\gamma$, as required. The last part is immediate as all tight probability
measures on metric spaces are Radon.

We now turn to the Wasserstein distance. A probability measure $\mu$ on a
metric space $X$ is said to have _finite moment of order $p$_, where $p\geq
1$, if, for some (equivalently all) $x_{0}\in X$, the integral

$\int d(x_{0},-)^{p}\mathrm{d}\mu$

is finite To see that the existence of the $p$-th moment does not depend on
the choice of $x_{0}$, recollect the inequality $(a+b)^{p}\leq
2^{p-1}(a^{p}+b^{p})$ for $a,b\in\mathbb{R}_{+}$ and $p\geq 1$. Then, for any
$x,y,z\in X$, we have:

$\displaystyle d(x,y)^{p}$ $\displaystyle\leq 2^{p-1}(d(x,z)^{p}+d(z,y)^{p})$
(1)

and the conclusion follows, taking $z=x_{0}$ and $y$ to be any other choice.
Note that finite probability measures with finite support have finite moments
of all orders.

One can obtain examples of measures with countable support, and with or
without finite moments, by using the fact that the Dirichlet series
$\zeta(s)=\sum_{n\geq 1}\frac{1}{n^{s}}$ converges for reals $s>1$ and
diverges for $s=1$. Taking the natural numbers as a metric space with the
usual Euclidean metric $d(m,n)=|m-n|$, one sees that, for $q\geq 1$, the
discrete probability measure $D_{q}$ where
$D_{q}(n)=\zeta(q+1)^{-1}\frac{1}{n^{q+1}}$ for $n\geq 1$ and $D_{q}(0)=0$,
has finite $p$-moment if, and only if, $p<q$.

The Wasserstein distance of order $p$, $\mathrm{W}_{p}$ is defined between
probability measures with finite moments of order $p$ by:

$\mathrm{W}_{p}(\mu,\nu)=\left(\inf_{\gamma}\int
d^{p}_{X}\mathrm{d}\gamma\right)^{1/p}$

where $\gamma$ runs over the couplings between $\mu$ and $\nu$. To see that it
is well-defined for probability measures with finite $p$-moment, one again
invokes (1), this time to get an integrable upper bound on $d^{p}_{X}$ as
follows:

$\int d^{p}_{X}\mathrm{d}\gamma\leq 2^{p-1}(\int
d(-,x_{0})^{p}\mathrm{d}\gamma+\int
d(x_{0},-)^{p}\mathrm{d}\gamma)=2^{p-1}(\int d(-,x_{0})^{p}\mathrm{d}\mu+\int
d(x_{0},-)^{p}\mathrm{d}\nu)$

The Wasserstein distance in monotonic in $p$, that is,
$\mathrm{W}_{p}(\mu,\nu)\leq\mathrm{W}_{q}(\mu,\nu)$ for $1\leq p\leq q$ and
$\mu,\nu$ with finite moments of order $q$. This is an immediate consequence
of the inequality $(\int f^{p}\mathrm{d}\mu)^{1/p}\leq(\int
f^{q}\mathrm{d}\mu)^{1/q}$, which holds for any probability measure $\mu$ and
any $f\geq 0$ with $f^{q}$ integrable w.r.t. $\mu$ (this inequality is itself
a straightforward consequence of Hölder’s inequality).

We need two lemmas relating probability measures on a metric space with
probability measures on a closed subset of the space. Let $C$ be a closed
subset of a metric space $X$. We write $\mathrm{i}_{*}(\mu)$ for the
pushforward of a finite measure $\mu$ on $C$ along the inclusion
$\mathrm{i}:C\rightarrow X$ of $C$ in $X$, so
$\mathrm{i}_{*}(\mu)(B)=\mu(B\cap C)$; and we write $\mathrm{r}(\nu)$ for the
restriction of a finite measure $\nu$ on $X$ to a finite measure on $C$, so
$\mathrm{r}(\nu)(B)=\nu(B)$. Note that $\mathrm{r}(\mathrm{i}_{*}(\mu))=\mu$.

######  Lemma 3.

Let $C$ be a closed subset of a metric space $X$.

  1. (1)

If $\mu$ is a Radon probability measure on $C$, then $\mathrm{i}_{*}(\mu)$ is
a Radon probability measure on $X$ with the same support as $\mu$. Further,
$\mathrm{i}_{*}(\mu)$ has finite moment of order $p$ if $\mu$ does.

  2. (2)

If $\nu$ is a Radon probability measure on $X$ with support included in $C$
then $\mathrm{r}(\nu)$ is a Radon probability measure on $C$, and we have:

$\nu=\mathrm{i}_{*}(\mathrm{r}(\nu))$

If, further, $\nu$ has finite moment of order $p$, so does $\mathrm{r}(\nu)$.

######  Proof 2.3.

  1. (1)

Let $\mu$ be a Radon probability measure on $C$, and note that $C$ must then
be non-empty. It is straightforward to check that $\mathrm{i}_{*}(\mu)$ is a
Radon probability measure on $X$ with the same support as $\mu$. Next,
choosing $x_{0}\in C$, as

$\int d_{X}(x_{0},-)^{p}\mathrm{d}(\mathrm{i}_{*}\mu)=\int
d_{C}(x_{0},-)^{p}\mathrm{d}\mu$

we see that $\mathrm{i}_{*}(\mu)$ has finite moment of order $p$ if $\mu$
does.

  2. (2)

Let $\nu$ be a Radon probability measure on $X$ with support included in $C$.
It is straightforward to check that $\mathrm{r}(\nu)$ is a Radon probability
measure on $C$. Regarding the equality, for any Borel set $B$ of $X$ we have:

$\mathrm{i}_{*}(\mathrm{r}(\nu))(B)=\mathrm{r}(\nu)(B\cap C)=\nu(B\cap
C)=\nu(B)$

with the last equality holding as $\nu$ is Radon and the support of $\nu$ is
included in $C$. Finally, $\mathrm{r}(\nu)$ has finite moment of order $p$ if
$\nu$ does, as, choosing $x_{0}\in C$, we have:

$\displaystyle\int d_{C}(x_{0},-)^{p}\mathrm{d}(\mathrm{r}(\nu))=\int
d_{X}(x_{0},-)^{p}\mathrm{d}(\mathrm{i}_{*}(\mathrm{r}(\nu)))=\int
d_{X}(x_{0},-)^{p}\mathrm{d}\nu$

######  Lemma 4.

Let $C$ be a closed subset of a metric space $X$. Then

  1. (1)

For any Radon probability measures $\mu,\nu$ on $X$ with finite moments of
order $p$ we have:

$\mathrm{W}_{p}(\mu,\nu)=\mathrm{W}_{p}(\mathrm{i}_{*}(\mu),\mathrm{i}_{*}(\nu))$

  2. (2)

For any Radon probability measures $\mu,\nu$ on $X$ with finite moments of
order $p$ whose support is included in $C$, we have:

$\mathrm{W}_{p}(\mu,\nu)=\mathrm{W}_{p}(\mathrm{r}(\mu),\mathrm{r}(\nu))$

######  Proof 2.4.

  1. (1)

Let $\gamma$ be a coupling between $\mu$ and $\nu$. Then
$(\mathrm{i}\times\mathrm{i})_{*}(\gamma)$ is a coupling between
$\mathrm{i}_{*}(\mu)$ and $\mathrm{i}_{*}(\nu)$, as
$(\pi_{0})_{*}((\mathrm{i}\times\mathrm{i})_{*}(\gamma))=\mathrm{i}_{*}((\pi_{0})_{*}(\gamma))=\mathrm{i}_{*}(\mu)$,
and similarly for $\nu$. We also have:

$\int d^{p}_{X}\mathrm{d}((\mathrm{i}\times\mathrm{i})_{*}\gamma)=\int
d^{p}_{C}\mathrm{d}\gamma$

As $\gamma$ was chosen arbitrarily, we therefore have:

$\mathrm{W}_{p}(\mu,\nu)\geq\mathrm{W}_{p}(\mathrm{i}_{*}(\mu),\mathrm{i}_{*}(\nu))$

For the reverse inequality, let $\gamma$ be a coupling between
$\mathrm{i}_{*}(\mu)$ and $\mathrm{i}_{*}(\nu)$. By Lemma 3.1,
$\mathrm{i}_{*}(\mu)$ and $\mathrm{i}_{*}(\nu)$ are Radon. So, by Lemma 2,
$\gamma$ is also Radon. Also, $\mathrm{supp}(\gamma)\subseteq C\times C$,
since $\mathrm{supp}(\mathrm{i}_{*}(\mu))\subseteq C$ and
$\mathrm{supp}(\mathrm{i}_{*}(\nu))\subseteq C$. So, by Lemma 3.2,
$\mathrm{r}(\gamma)$ is a Radon probability measure on $C^{2}$ and
$\gamma=(\mathrm{i}\times\mathrm{i})_{*}(\mathrm{r}(\gamma))$.

Further, $\mathrm{r}(\gamma)$ is a coupling between $\mu$ and $\nu$, for:

$\begin{array}[]{lcll}\mathrm{r}(\gamma)(B\times C)&=&\gamma(B\times C)\\\
&=&\gamma((B\times X)\cap(C\times C))\\\ &=&\gamma(B\times X)\quad(\mbox{as
$\mathrm{supp}(\gamma)\subseteq C\times C$})\\\ &=&\mu(B)\\\
&=&\mathrm{r}(\mu)(B)\end{array}$

and similarly for $\nu$. We then have:

$\int d^{p}_{X}\mathrm{d}\gamma=\int
d^{p}_{X}\mathrm{d}((\mathrm{i}\times\mathrm{i})_{*}(\mathrm{r}\gamma))=\int
d^{p}_{C}\mathrm{d}(\mathrm{r}\gamma)$

As $\gamma$ was chosen arbitrarily, we therefore have, as required:

$\mathrm{W}_{p}(\mathrm{i}_{*}(\mu),\mathrm{i}_{*}(\nu))\geq\mathrm{W}_{p}(\mu,\nu)$

  2. (2)

Using part (1), we have:

$\displaystyle\mathrm{W}_{p}(\mu,\nu)=\mathrm{W}_{p}(\mathrm{i}_{*}(\mathrm{r}(\mu)),\mathrm{i}_{*}(\mathrm{r}(\nu)))=\mathrm{W}_{p}(\mathrm{r}(\mu),\mathrm{r}(\nu))$

With these technical lemmas established, we can now prove two theorems on
spaces of Radon probability measures. For any metric space $X$ and $p\geq 1$,
define $P_{p}(X)$ to be the set of Radon probability measures on $X$ with
finite moments of order $p$, equipped with the $W_{p}$ distance. For the first
theorem we use the result in [4] that the triangle inequality holds for all
probability measures if $X$ is separable.

######  Theorem 5.

Let $X$ be a metric space. Then $P_{p}(X)$ is a metric space.

######  Proof 2.5.

First $\mathrm{W}_{p}(\mu,\mu)=0$ for any $\mu\in P_{p}(X)$ as
$\Delta_{*}\mu$, the pushforward of $\mu$ along the diagonal
$\Delta:X\rightarrow X\times X$, is a coupling between $\mu$ and itself. For
the converse, choose $\mu,\nu\in P_{p}(X)$, and suppose
$\mathrm{W}_{p}(\mu,\nu)=0$. Then $\mathrm{W}_{1}(\mu,\nu)=0$, as $W_{q}$ is
monotonic in $q$. It follows that $\mu=\nu$ as $W_{1}$ is a metric on
$P_{1}(X)$ (see, e.g., [5, 1]).

Symmetry is evident. To show the triangle inequality, suppose that
$\mu,\nu,\omega\in P_{p}(X)$. Let $C$ be the closed set
$\mathrm{supp}(\mu)\cup\mathrm{supp}(\nu)\cup\mathrm{supp}(\omega)$, separable
by Lemma 1. Then $\mathrm{r}(\mu)$, $\mathrm{r}(\nu)$ and $\mathrm{r}(\omega)$
are probability measures on the separable space $C$, and so by [4], we have
$\mathrm{W}_{p}(\mathrm{r}(\mu),\mathrm{r}(\omega))\leq\mathrm{W}_{p}(\mathrm{r}(\mu),\mathrm{r}(\nu))+\mathrm{W}_{p}(\mathrm{r}(\nu),\mathrm{r}(\omega))$.
Then, by Lemmas 4.2 and 3.2, we see that
$\mathrm{W}_{p}(\mu,\omega)\leq\mathrm{W}_{p}(\nu,\omega)+\mathrm{W}_{p}(\nu,\omega)$,
as required.

For the second theorem we use the result that the metric space of all
probability measures with finite moments of order $p$ on a complete and
separable space is also complete and separable, being generated by the
rational measures with finite support in a countable basis of the space.

######  Theorem 6.

Let $X$ be a complete metric space. Then $P_{p}(X)$ is a complete metric space
generated by the finitely supported probability measures on $X$.

######  Proof 2.6.

To show that $P_{p}(X)$ is complete, let $\langle\mu_{i}\rangle_{i}$ be a
Cauchy sequence in $P_{p}(X)$. Let $C$ be the closure in $P_{p}(X)$ of
$\bigcup_{i}\mathrm{supp}(\mu_{i})$. By Lemma 1, each set
$\mathrm{supp}(\mu_{i})$ is separable, and so $C$ is itself separable, being
the closure of a countable union of separable sets. Further, $C$ is complete
as it is a closed subset of a complete space. So $P_{p}(C)$ is complete.
Applying Lemmas 3.2 and 4.2, we see that
$\langle\mathrm{r}(\mu_{i})\rangle_{i}$ is a Cauchy sequence in $P_{p}(C)$.
Let $\mu$ be its limit there. As Lemma 4.1 shows that $\mathrm{i}_{*}$ is an
isometric embedding, we see that
$\langle\mathrm{i}_{*}(\mathrm{r}(\mu_{i}))\rangle_{i}$ is a Cauchy sequence
in $P_{p}(C)$ with limit $\mathrm{i}_{*}(\mu)$. But, by Lemma 3.2,
$\langle\mathrm{i}_{*}(\mathrm{r}(\mu_{i}))\rangle_{i}$ is
$\langle\mu_{i}\rangle_{i}$ .

To see that the finitely supported probability measures are dense in
$P_{p}(X)$, choose $\mu\in P_{p}(X)$ and $\varepsilon>0$. Then, taking $C$ to
be the separable closed set $\mathrm{supp}(\mu)$, we have $\mathrm{r}(\mu)\in
P_{p}(C)$. Then, as $P_{p}(C)$ is generated by the rational measures with
finite support, there is a finitely supported probability measure $\alpha\in
P_{p}(C)$ at distance $\leq\varepsilon$ from $\mathrm{r}(\mu)$, and so we see
that $\mathrm{i}_{*}(\alpha)$ is at distance $\leq\varepsilon$ from $\mu$.
Finally, $\mathrm{i}_{*}(\alpha)$ is finitely supported as, by Lemma 3.1, it
has the same support as $\alpha$.

It is interesting to consider how the different Wasserstein metrics generate
the various $P_{p}(X)$ starting from the same basis, i.e., the probability
measures with finite support. As $W_{p}$ is monotonic in $p$ when $p\leq q$,
any sequence Cauchy in the $W_{q}$ metric is also Cauchy in the $W_{p}$
metric. So the difference must be that sequences of probability measures with
finite support can be Cauchy in the $W_{p}$ metric, but not in the $W_{q}$
metric when $p<q$. Examples of this phenomenon can be found by building on
Example 2:

Set

$D_{q,m}(n)=\left\\{\begin{array}[]{ll}0&(n=0)\\\
\zeta(q+1)^{-1}\frac{1}{n^{q+1}}&(1\leq n\leq m)\\\
1-\zeta(q+1)^{-1}\sum^{m}_{i=1}\frac{1}{n^{q+1}}&(n=m+1)\\\
0&(n>m+1)\end{array}\right.$

Note that $D_{q,m}$ and $D_{q}$ agree for $1\leq n\leq m$, but the rest of the
mass of $D_{q}$ is concentrated on $D_{q,m}$ at $m+1$. Then the sequence
$D_{q,m}$ converges to $D_{q}$ in the $W_{p}$ metric when $p<q$, but is not
Cauchy w.r.t. $W_{p}$ when $p=q$.

We pause our development to examine the topologies induced by the Wasserstein
metrics. In the case of separable such spaces it is known that these metrics
topologise a suitable notion of weak convergence, see [23, Theorem 7.12]. It
turns out that we can again use our techniques and generalise these results to
all complete metric spaces.

Given a metric space $X$ and probability measures $\mu_{i}$ ($i\geq 0$) and
$\mu$ on $X$, we say that the $\mu_{i}$ _converge weakly_ to $\mu$, and write
$\mu_{i}\longrightarrow\mu$ if, for all continuous bounded
$f:X\rightarrow\mathbb{R}$, we have $\int
f\mathrm{d}\mu_{i}\longrightarrow\int f\mathrm{d}\mu$; an equivalent
formulation is that $\underline{\lim}_{i}\,\mu_{i}(U)\geq\mu(U)$ for every
open set $U$ (see [19, Theorem 6]).

######  Lemma 7.

Let $C\subseteq X$ be a closed subset of a metric space and let $\mu_{i}$
($i\geq 0$) and $\mu$ be probability measures on $C$. Then we have:

$\mu_{i}\longrightarrow\mu\quad\iff\quad\mathrm{i}_{*}(\mu_{i})\longrightarrow\mathrm{i}_{*}(\mu)$

where $\iota:C\rightarrow X$ is the inclusion map.

######  Proof 2.7.

We use the equivalent formulation of weak convergence in terms of measures of
open sets. In one direction, suppose that $\mu_{i}\longrightarrow\mu$. Then
$\mathrm{i}_{*}(\mu_{i})\longrightarrow\mathrm{i}_{*}(\mu)$, since for every
open subset $U\subseteq X$, and any probability measure $\nu$ on $C$, we have
$\mathrm{i}_{*}(\nu)(U)=\nu(U\cap X)$. In the other direction, suppose that
$\mathrm{i}_{*}(\mu_{i})\longrightarrow\mathrm{i}_{*}(\mu)$. Then
$\mu_{i}\longrightarrow\mu$ since for any open set $U$ of $C$ there is an open
set $V$ of $X$ such that $U=V\cap C$ and then, for any probability measure
$\nu$ on $C$, we have $\nu(U)=\mathrm{i}_{*}(\nu)(V)$.

######  Lemma 8.

Let $C$ be a separable closed subset of a complete metric space $X$, and let
$\mathrm{i}:C\rightarrow X$ be the inclusion map. Then, for any probability
measures $\alpha_{i}$ ($i\geq 0$) and $\alpha$ on $C$, and any $x_{0}\in C$,
the following are equivalent, and hold independently of the choice of
$x_{0}\in C$:

  1. (1)

$\mathrm{i}_{*}(\alpha_{i})\longrightarrow\mathrm{i}_{*}(\alpha)$ and $\int
d_{X}(x_{0},-)^{p}\mathrm{d}\mathrm{i}_{*}(\alpha_{i})\longrightarrow\int
d_{X}(x_{0},-)^{p}\mathrm{d}\mathrm{i}_{*}(\alpha)$.

  2. (2)

$\alpha_{i}\longrightarrow\alpha$ and $\int
d_{C}(x_{0},-)^{p}\mathrm{d}\alpha_{i}\longrightarrow\int
d_{C}(x_{0},-)^{p}\mathrm{d}\alpha$.

  3. (3)

For all continuous functions $f:C\rightarrow\mathbb{R}$ such that $|f(x)|\leq
c(1+d_{C}(x_{0},x)^{p})$ for all $x\in C$, for some $c\in\mathbb{R}$, one has
$\int f\mathrm{d}\alpha_{i}\longrightarrow f\mathrm{d}\alpha$.

  4. (4)

For all continuous functions $f:X\rightarrow\mathbb{R}$ such that $|f(x)|\leq
c(1+d_{X}(x_{0},x)^{p})$ for all $x\in X$, for some $c\in\mathbb{R}$, one has
$\int f\mathrm{d}\mathrm{i}_{*}(\alpha_{i})\longrightarrow
f\mathrm{d}\mathrm{i}_{*}(\alpha)$.

######  Proof 2.8.

As $C$ is separable and complete, by [23, Theorem 7.12], (2) and (3) are
equivalent. and hold independently of the choice of $x_{0}\in C$. As, further,
(4) trivially implies (1), it suffices to prove that (1) implies (2) and (3)
implies (4), for any $x_{0}\in C$. The first of these implications follows
using Lemma 7 and the fact that $\int
d_{C}(x_{0},-)^{p}\mathrm{d}\alpha_{i}=\int
d_{X}(x_{0},-)^{p}\mathrm{d}\mathrm{i}_{*}(\alpha_{i})$, for all $i\geq 0$,
and similarly for $\alpha$. For the second of these implications, one again
uses Lemma 7 and notes that if $f:X\rightarrow\mathbb{R}$ is a continuous
function such that $|f(x)|\leq c(1+d_{X}(x_{0},x)^{p})$ for all $x\in X$, for
some $c\in\mathbb{R}$, then $f\mathrm{i}:C\rightarrow\mathbb{R}$ is a
continuous function such that $|(f\mathrm{i})(x)|\leq
c(1+d_{C}(x_{0},x)^{p})$, for all $X\in C$ and that $\int
f\mathrm{d}\mathrm{i}_{*}(\alpha_{i})=\int(f\mathrm{i})\mathrm{d}\alpha_{i}$,
and similarly for $\alpha$.

######  Theorem 9.

Let $X$ be a complete metric space and choose $\mu_{i}$ ($i\geq 0$) and $\mu$
in $P_{p}(X)$. Then the following two conditions hold independently of the
choice of $x_{0}\in X$ and are equivalent:

  1. (1)

$\mu_{i}\longrightarrow\mu$ and $\int
d(x_{0},-)^{p}\mathrm{d}\mu_{i}\longrightarrow\int
d(x_{0},-)^{p}\mathrm{d}\mu$,

  2. (2)

For all continuous functions $f:X\rightarrow\mathbb{R}$ such that $|f(x)|\leq
c(1+d(x_{0},x)^{p})$ for all $x\in X$, for some $c\in\mathbb{R}$, one has
$\int f\mathrm{d}\mu_{i}\longrightarrow f\mathrm{d}\mu$.

######  Proof 2.9.

First, choose $a,b\in X$. Next, choose a separable closed set $C\subseteq X$
containing $a$ and $b$ and including the supports of the $\mu_{i}$ ($i\geq 0$)
and $\mu$. Then, taking $\alpha_{i}=r(\mu_{i})$ ($i\geq 0$) and
$\alpha=r(\mu)$ in Lemma 8, we see that (1) and (2) hold independently of the
choice of $x_{0}\in C$ (e.g., whether choosing $a$ or $b$) and are equivalent
for any such choice as $\mu_{i}=\mathrm{i}_{*}(\alpha_{i})$, for all $i\geq
0$, and $\mu=\mathrm{i}_{*}(\alpha)$. As $a$ and $b$ were chosen arbitrarily
from $X$, the conclusion follows.

If either of the two equivalent conditions of Theorem 9 hold for $\mu_{i}$
($i\geq 0$) and $\mu$ in $P_{p}(X)$ and any choice of $x_{0}\in X$, where $X$
is a complete metric space, we say that the $\mu_{i}$ _converge $p$-weakly_ to
$\mu$, and write $\mu_{i}\longrightarrow_{p}\mu$.

######  Theorem 10.

For any complete metric space $X$, the Wasserstein distance $W_{p}$ metricises
$p$-weak convergence in $P_{p}(X)$.

######  Proof 2.10.

Choose $\mu_{i}$ ($i\geq 0$) and $\mu$ in $P_{p}(X)$ to show that
$\mu_{i}\longrightarrow_{p}\mu$ iff $\mu_{i}$ converges to $\mu$ w.r.t. the
Wasserstein distance $W_{p}$ in $X$. To this end, let $C\subseteq X$ be a
closed separable set containing the supports of the $\mu_{i}$ and $\mu$ (and
so necessarily nonempty), and set $\alpha_{i}=r(\mu_{i})$ and $\alpha=r(\mu)$
and let $x_{0}$ be an element of $C$. By [24, Theorem 6.9] we have that
$\alpha_{i}\longrightarrow_{p}\alpha$ iff $\alpha_{i}$ converges to $\alpha$
w.r.t. the Wasserstein distance $W_{p}$ in $C$. So it suffices to show (i)
that $\mu_{i}\longrightarrow_{p}\mu$ iff
$\alpha_{i}\longrightarrow_{p}\alpha$, and (ii) that $\mu_{i}$ converges to
$\mu$ w.r.t. the Wasserstein distance $W_{p}$ in $X$ iff $\alpha_{i}$
converges to $\alpha$ w.r.t. the Wasserstein distance $W_{p}$ in $C$.

That (i) holds follows from the definition of $p$-weak convergence and the
equivalence between parts (1) and (2) of Lemma 8 applied to the $\alpha_{i}$,
$\alpha$, and $x_{0}$. That (ii) holds follows from the fact that, by Lemma
4.1, the inclusion of $C$ in $X$ is an isometric embedding.

##  3\. Wasserstein algebras

We begin with an account of barycentric algebras. We then move on to
quantitative algebras, by which we mean algebras over metric spaces. After
some general considerations on these we move on to Wasserstein algebras of
order $p$, and our main theorem, characterising the Wasserstein monads
$P_{p}$.

A _barycentric algebra_ (or _abstract convex set_) is a set $X$ equipped with
binary operations $+_{r}$ for every real number $r\in[0,1]$ such that the
following equational laws hold:

$\displaystyle x+_{1}y$ $\displaystyle=x$ (B1) $\displaystyle x+_{r}x$
$\displaystyle=x$ (B2) $\displaystyle x+_{r}y$ $\displaystyle=y+_{1-r}x$ (SC)
$\displaystyle(x+_{p}y)+_{r}z$
$\displaystyle=x+_{pr}(y+_{\frac{r-pr}{1-pr}}z)\ \ \ \mbox{ provided }r<1,p<1$
(SA)

SC stands for _skew commutativity_ and SA for _skew associativity_.
Homomorphisms of barycentric algebras are termed _affine_.

One can inductively define finite convex sums in a barycentric algebra by:

$\sum_{i=1}^{n}r_{i}x_{i}=x_{1}+_{r_{1}}\sum_{i=2}^{n}\frac{r_{i}}{1-r_{1}}x_{i}$

for $n>2$, $r_{1}\neq 1$, with the other cases being evident. Note that affine
maps preserve such finite convex sums. Finite convex sums have been
axiomatised as _convex spaces_ (or _convex algebras_) where the sums are
required to obey the _projection_ axioims:

$\sum_{i=1}^{n}\delta_{ik}x_{i}=x_{k}$

where $\delta_{ik}$ is the Kronecker symbol, and the _barycentre_ axioms:

$\sum_{i=1}^{n}r_{i}\big{(}\sum_{k=1}^{m}s_{ik}x_{k}\big{)}=\sum_{k=1}^{m}\big{(}\sum_{i=1}^{n}r_{i}s_{ik}\big{)}x_{k}$

With the above definition of finite sums, barycentric algebras form convex
spaces, and indeed the two categories of algebras are equivalent under this
correspondence.

Probability measures on a measurable space, and subclasses of them, naturally
form barycentric algebras under the standard binary pointwise convex
combination operations:

$(\mu+_{r}\nu)(B)=r\mu(B)+(1-r)\nu(B)$

In particular, for any set $X$, the barycentric algebra $P_{f}(X)$ of
probability measures over $X$ with finite support is the free barycentric
algebra over $X$, with universal arrow the Dirac delta function (see [18,
20]); if $f:X\rightarrow B$ is a map to a barycentric algebra $B$, then the
unique extension of $f:X\rightarrow B$ along $\delta$ is given by:

$\overline{f}(\mu)=\sum_{s\in\mathrm{supp}(\mu)}\mu(s)f(s)$

Barycentric algebras originate with the work of M.H. Stone in [21], and convex
spaces with that of T. Šwirszcz in [22]. For further bibliographic references
and historical discussion, see, e.g., [14].

Turning to quantitative algebras, we work with the category of metric spaces
and nonexpansive maps, and its subcategory of complete metric spaces. These
categories have all finite products with the one-point metric space as the
final object and with the max metric on binary products $X\times Y$, where:

$d_{X\times Y}(\langle x,y\rangle,\langle
x^{\prime},y^{\prime}\rangle)=\max\\{d_{X}(x,x^{\prime}),d_{Y}(y,y^{\prime})\\}$

We remark that nonexpansive maps are continuous.

A _finitary signature_ $\Sigma$ is a collection of operation symbols $f$ and
an assignment of an arity $n\in\mathbb{N}$ to each; given such a signature, we
write $f:n$ to indicate that $f$ is an operation symbol of arity $n$. A
_(metric space) quantitative $\Sigma$-algebra $(X,f_{X}\;(f\in\Sigma))$_ is
then a metric space $X$ equipped with a nonexpansive function
$f_{X}:X^{n}\rightarrow X$ for each operation symbol $f:n$. We often omit the
suffix on the operation symbol and also confuse the metric space with the
algebra. A _homomorphism_ $h:X\rightarrow Y$ of $\Sigma$-algebras is a
nonexpansive map $h:X\rightarrow Y$ such that for all $f:n$ and
$x_{1},\ldots,x_{n}\in X$ we have:

$h(f_{X}(x_{1},\ldots,x_{n}))=f_{Y}(h(x_{1}),\ldots,h(x_{n}))$

This defines a category of quantitative $\Sigma$-algebras and homomorphisms;
it has an evident subcategory of complete quantitative $\Sigma$-algebras.

For any $p\geq 1$, a _Wasserstein (barycentric) algebra of order $p$_ is a
quantitative algebra $(X,+_{r}:X^{2}\rightarrow X\,(r\in[0,1]))$ forming a
barycentric algebra such that for all $x,x^{\prime},y,y^{\prime}\in X$ we
have:

$d(x+_{r}y,x^{\prime}+_{r}y^{\prime})^{p}\leq
rd(x,x^{\prime})^{p}+(1-r)d(y,y^{\prime})^{p}$ ($\ast$)

We remark that the hypothesis of non-expansiveness of the $+_{r}$ is redundant
as, setting

$m=\max\\{d(x,x^{\prime}),d(y,y^{\prime})\\}$

we have:

$\begin{array}[]{lcl}d(x+_{r}y,x^{\prime}+_{r}y^{\prime})&\leq&(rd(x,x^{\prime})^{p}+(1-r)d(y,y^{\prime})^{p})^{1/p}\\\
&\leq&(rm^{p}+(1-r)m^{p})^{1/p}\\\ &=&m\end{array}$

We gather some other remarks about convex combinations. Recollect that a
function $f:X\rightarrow Y$ between metric spaces is _$\alpha$ -Hölder
continuous_ if, for all $x,y\in X$, we have $d(fx,fy)\leq Md(x,y)^{\alpha}$
for some constant $M$.

######  Lemma 11.

Let $(X,+_{r}\,(r\in[0,1]))$ be a Wasserstein algebra of order $p$. Then:

  1. (1)

The functions $+_{r}$ are $r^{1/p}$-Lipschitz in their first argument and
$(1-r)^{1/p}$-Lipschitz in their second argument.

  2. (2)

Considered as a function of $r$, $x+_{r}y$ is $1/p$-Hölder continuous.

  3. (3)

The following generalisation of equation ($\ast$ ‣ 3) to finite convex sums
holds:

$\begin{array}[]{lclr}d(\sum_{i=1}^{n}r_{i}x_{i},\sum_{i=1}^{n}r_{i}x^{\prime}_{i})^{p}&\leq&\sum_{i=1}^{n}r_{i}d(x_{i},x^{\prime}_{i})^{p}\end{array}$

######  Proof 3.1.

  1. (1)

Taking $y=y^{\prime}$ ($x=x^{\prime})$ in ($\ast$ ‣ 3) we respectively obtain:

$d(x+_{r}y,x^{\prime}+_{r}y)\leq r^{1/p}d(x,x^{\prime})\quad\mbox{and}\quad
d(x+_{r}y,x+_{r}y^{\prime})\leq(1-r)^{1/p}d(y,y^{\prime})$

as required.

  2. (2)

Fix $x,y\in X$ and choose $r,s\in[0,1]$. Suppose that $s\leq r$ and set
$e=r-s$. Assuming $e\neq 1$, we have

$x+_{r}y=x+_{e}(x+_{s/1-e}y)\mbox{ and }x+_{s}y=y+_{e}(x+_{s/1-e}y)$

So by part 1 we have

$d(x+_{r}y,x+_{s}y)\leq e^{1/p}d(x,y)$

This also holds when $e=1$ as then $r=1$ and $s=0$. As $e=d(r,s)$, we
therefore have:

$d(x+_{r}y,x+_{s}y)\leq d(x,y)d(r,s)^{1/p}$

By symmetry this also holds when $r\leq s$. As $p\geq 1$, $0<1/p\leq 1$, so,
as a function of $r$, $x+_{r}y$ is $1/p$-Hölder continuous, as required.

  3. (3)

This is a straightforward induction.

For any metric space $X$, we turn $P_{p}(X)$ into a barycentric algebra by
equipping it with the standard convex combination operations. It is evident
that $\mu+_{r}\nu$ has finite moment of order $p$ if $\mu$ and $\nu$ do.

######  Lemma 12.

For any metric space $X$, $P_{p}(X)$ forms a Wasserstein algebra of order $p$.

######  Proof 3.2.

We need only show that for any $\mu,\mu^{\prime},\nu,\nu^{\prime}\in P_{p}(X)$
and $r\in[0,1]$ we have:

$\begin{array}[]{lcl}\mathrm{W}_{p}(\mu+_{r}\nu,\mu^{\prime}+_{r}\nu^{\prime})^{p}&\leq&r\mathrm{W}_{p}(\mu,\mu^{\prime})^{p}+(1-r)\mathrm{W}_{p}(\nu,\nu^{\prime})^{p}\end{array}$

(recalling that theWasserstein condition implies nonexpansivness of the
operations). To this end, choose $\mu,\mu^{\prime},\nu,\nu^{\prime}\in
P_{p}(X)$. Let $\alpha$ be a coupling between $\mu$ and $\mu^{\prime}$ and let
$\beta$ be a coupling between $\nu$ and $\nu^{\prime}$. Then
$\alpha+_{r}\beta$ is a coupling between $\mu+_{r}\nu$ and
$\mu^{\prime}+_{r}\nu^{\prime}$, and we have:

$\begin{array}[]{lcl }\int d^{p}_{X}\mathrm{d}(\alpha+_{r}\beta)&=&\ \int
d^{p}_{X}\mathrm{d}\alpha+_{r}\int d^{p}_{X}\mathrm{d}\beta\\\ \end{array}$

The conclusion then follows, as we have:

$\begin{array}[b]{lcl}\mathrm{W}_{p}(\mu+_{r}\nu,\mu^{\prime}+_{r}\nu^{\prime})^{p}&=&\inf_{\gamma}\left(\int
d^{p}_{X}\mathrm{d}\gamma\right)\\\ &\leq&\inf_{\alpha,\beta}\left(\int
d^{p}_{X}\mathrm{d}(\alpha+_{r}\beta)\right)\\\
&=&\inf_{\alpha,\beta}\left(\int d^{p}_{X}\mathrm{d}\alpha+_{r}\int
d^{p}_{X}\mathrm{d}\beta\right)\\\ &=&\inf_{\alpha}\left(\int
d^{p}_{X}\mathrm{d}\alpha\right)+_{r}\inf_{\beta}\left(\int
d^{p}_{X}\mathrm{d}\beta\right)\\\
&=&\mathrm{W}_{p}(\mu,\nu)^{p}+_{r}\mathrm{W}_{p}(\mu^{\prime},\nu^{\prime})^{p}\end{array}$

We next turn to characterising the free Wasserstein algebras of order $p$. For
any metric space X, let $F_{p}(X)$ be the sub-Wasserstein algebra of order $p$
of $P_{p}$ that consists of the finitely supported probability measures.

######  Theorem 13.

For any metric space X, $F_{p}(X)$ is the free Wasserstein algebra of order
$p$ over $X$, with universal arrow the Dirac delta function
$\delta:X\rightarrow F_{p}(X)$.

######  Proof 3.3.

First, $\delta:X\rightarrow F_{p}(X)$ is an isometric embedding, since, for
any $x,y\in X$, the only coupling between $\delta(x)$ and $\delta(y)$ is
$\delta(\langle x,y\rangle)$, and so we have:

$W_{p}(\delta(x)),\delta(y))=(d(x,y)^{p})^{1/p}=d(x,y)$

Next, let $f:X\rightarrow W$ be any nonexpansive affine map to a Wasserstein
algebra $B$ of order $p$. As a set, $F_{p}(X)$ is the free barycentric algebra
over $X$ with unit the Dirac function, and the unique affine map
$\overline{f}:F_{p}(X)\rightarrow W$ extending $f$ along the unit is given by
the formula:

$\overline{f}(\mu)=\sum_{s\in\mathrm{supp}(\mu)}\mu(s)f(s)$

So it only remains to show that $\overline{f}$ is nonexpansive. Let $\mu$,
$\nu$ be finitely supported probability measures with respective finite non-
empty supports $S$ and $T$. Let $\gamma$ be a coupling between them. Then
$\gamma$ has support $\subseteq S\times T$. Consequently we can write it as a
convex sum, as follows:

$\gamma=\sum_{s\in S,t\in T}\gamma(\langle s,t\rangle)\delta(\langle
s,t\rangle)$

As $\mu$ and $\nu$ are the marginals of $\gamma$, we have:

$\mu=\sum_{s\in S,t\in T}\gamma(\langle
s,t\rangle)\delta(s)\quad\mbox{and}\quad\nu=\sum_{s\in S,t\in T}\gamma(\langle
s,t\rangle)\delta(t)$

We can now calculate:

$\begin{array}[]{lcl}d(\overline{f}(\mu),\overline{f}(\nu))&=&d(\overline{f}(\sum_{s\in
S,t\in T}\gamma(\langle s,t\rangle)\delta(s)),\overline{f}(\sum_{s\in S,t\in
T}\gamma(\langle s,t\rangle)\delta(t)))\\\ &=&d(\sum_{s\in S,t\in
T}\gamma(\langle s,t\rangle)\overline{f}(\delta(s)),\sum_{s\in S,t\in
T}\gamma(\langle s,t\rangle)\overline{f}(\delta(t)))\\\ &=&d(\sum_{s\in S,t\in
T}\gamma(\langle s,t\rangle)f(s),(\sum_{s\in S,t\in T}\gamma(\langle
s,t\rangle)f(t))\\\ &&\hskip 165.0pt(\mbox{as $f=\overline{f}\delta$})\\\
&\leq&\left(\sum_{s\in S,t\in T}\gamma(\langle
s,t\rangle)d(f(s),f(t))^{p}\right)^{1/p}\\\ &&\hskip 165.0pt(\mbox{by
Lemma~{}\hyperref@@ii[was3]{\ref*{was}.\ref*{was3}}})\\\
&\leq&\left(\sum_{s\in S,t\in T}\gamma(\langle
s,t\rangle)d(s,t)^{p}\right)^{1/p}\\\ &&\hskip 165.0pt(\mbox{as $f$ is
nonexpansive})\\\ &=&\left(\int
d^{p}_{X}\mathrm{d}\gamma\right)^{1/p}\end{array}$

As $\gamma$ was an arbitrary coupling between $\mu$ and $\nu$ we therefore
have

$d(\overline{f}(\mu),\overline{f}(\nu))\leq W_{p}(\mu,\nu)$

as required.

To characterise the free complete Wasserstein algebras of order $p$, we need
two lemmas, one on the completion of metric spaces, and the other on the
completion of quantitative $\Sigma$-algebras. The usual completion
$\overline{X}$ of a metric space $X$ by equivalence classes $[\mathbf{x}]$ of
Cauchy sequences is the free complete metric space over $X$, with universal
arrow the isometric embedding $c_{X}:X\rightarrow\overline{X}$, where
$c_{X}(x)=[\langle x\rangle_{n\in\mathbb{N}}]$. That is, for any complete
metric space $Y$ and nonexpansive function $f:X\rightarrow Y$ there is a
unique nonexpansive function $\overline{f}:\overline{X}\rightarrow Y$
extending $f$ along $c_{X}$. This function is given by the formula:

$\overline{f}([\mathbf{x}])=\lim_{n}f(\mathbf{x}_{n})$

There is a simple criterion for when an isometric embedding of a metric space
in another is a universal arrow:

######  Lemma 14.

Let $\theta:X\rightarrow Y$ be an isometric embedding of metric spaces with
$Y$ complete, and $\theta(X)$ generating $Y$. Then $Y$ is the free complete
metric space over $X$, with universal arrow $\theta$.

######  Proof 3.4.

We can assume without loss of generality that $\theta$ is an inclusion
mapping. We show that $\overline{\theta}$ is an isometry. To show it is onto,
choose $y\in Y$. As $X$ generates $Y$, $y$ is a limit of some Cauchy sequence
$\mathbf{x}$ in $X$ and we have

$\overline{\theta}([\mathbf{x}])=\lim_{n}\theta(\mathbf{x}_{n})=\lim_{n}\mathbf{x}_{n}=y$

as required.

To show $\overline{\theta}$ preserves distances, we calculate:

$d(\overline{\theta}([\mathbf{x}]),\overline{\theta}([\mathbf{y}])=d(\lim_{n}\mathbf{x}_{n},\lim_{n}\mathbf{y}_{n})=\lim_{n}d(\mathbf{x}_{n},\mathbf{y}_{n})=d([\mathbf{x}],[\mathbf{y}])$

So $\overline{\theta}$ is indeed an isometry. It follows that $\theta$ is a
universal arrow as $c_{X}$ is, and we are done.

The criterion of Lemma 14 extends to $\Sigma$-algebras:

######  Lemma 15.

Let $X$, $Y$ be quantitative $\Sigma$-algebras and let $\theta:X\rightarrow Y$
be both an algebra homomorphism and an isometric embedding. Suppose that $Y$
is complete as a metric space, and $\theta(X)$ generates $Y$ as a metric
space. Then $Y$ is the free complete quantitative $\Sigma$-algebra over $X$,
with universal arrow $\theta$.

######  Proof 3.5.

We can assume without loss of generality that $\theta$ is an inclusion
mapping. Let $h:X\rightarrow Z$ be any nonexpansive homomorphism from $X$ to a
complete quantitative algebra $Z$. By Lemma 1, $h$ extends to a unique
nonexpansive map $\overline{h}:Y\rightarrow Z$, and we only have to show that
this is a homomorphism. Taking a binary operation $f$ as an example, let $x,y$
be in $Y$. As $X$ generates $Y$ as a metric space there are Cauchy sequences
$\mathbf{x}$ and $\mathbf{y}$ in $X$ with respective limits $x$ and $y$, and
we calculate:

$\begin{array}[b]{lcl}\overline{h}(f_{Y}(x,y))&=&\overline{h}(f_{Y}(\lim_{n}\mathbf{x}_{n},\lim_{n}\mathbf{y}_{n}))\\\
&=&\overline{h}(\lim_{n}f_{Y}(\mathbf{x}_{n},\mathbf{y}_{n}))\\\
&=&\lim_{n}\overline{h}(f_{Y}(\mathbf{x}_{n},\mathbf{y}_{n}))\\\
&=&\lim_{n}\overline{h}(f_{X}(\mathbf{x}_{n},\mathbf{y}_{n}))\\\
&=&\lim_{n}h(f_{X}(\mathbf{x}_{n},\mathbf{y}_{n}))\\\
&=&\lim_{n}f_{Z}(h(\mathbf{x}_{n}),h(\mathbf{y}_{n}))\\\
&=&f_{Z}(\lim_{n}h(\mathbf{x}_{n}),\lim_{n}h(\mathbf{y}_{n}))\\\
&=&f_{Z}(\lim_{n}\overline{h}(\mathbf{x}_{n}),\lim_{n}\overline{h}(\mathbf{y}_{n}))\\\
&=&f_{Z}(\overline{h}(\lim_{n}\mathbf{x}_{n}),\overline{h}(\lim_{n}\mathbf{y}_{n}))\\\
&=&f_{Z}(\overline{h}(x),\overline{h}(y))\\\ \end{array}$

We can now prove our main theorem on free complete Wasserstein algebras of
order $p$:

######  Theorem 16.

For any complete metric space X, $P_{p}(X)$ is the free complete Wasserstein
algebra of order $p$ over $X$, with universal arrow the Dirac delta function.

######  Proof 3.6.

Theorem 6 and Lemma 12 tell us that $P_{p}(X)$ is a complete Wasserstein
algebra of order $p$. It therefore remains to prove it is the free one over
$X$, with unit the Dirac delta function.

First, by Theorem 13, $F_{p}(X)$ is the free Wasserstein algebra of order $p$
over $X$, with universal arrow the Dirac function.

Second, $P_{p}(X)$ is the free complete Wasserstein algebra of order $p$ over
$F_{p}(X)$, with universal arrow the inclusion. To see this, first note that
$F_{p}(X)$ is a sub-quantitative algebra of $P_{p}(X)$ that, by Theorem 6,
generates $P_{p}(X)$, So, by Lemma 15, $P_{p}(X)$ is the free complete
quantitative algebra with signature the $+_{r}$ over $F_{p}(X)$, with
universal arrow the inclusion. It is therefore, in particular, the free
complete Wasserstein algebra of order $p$ over $F_{p}(X)$, with universal
arrow the inclusion.

Combining these two free algebra assertions, we see that, as required,
$P_{p}(X)$ is the free complete Wasserstein algebra of order $p$ over $X$,
with universal arrow the Dirac delta function.

There is a disconnect between the present work and that in [17] where extended
metrics are used. We sketch the straightforward extension of the above
freeness results to extended metric spaces. An extended metric is a function
$d:X^{2}\rightarrow\overline{\mathbb{R}}_{+}$ to the extended reals, defined
in the usual way, but using the natural extension of addition to
$\overline{\mathbb{R}}_{+}$, where $x+\infty=\infty+x=\infty$ and the natural
extension of the order where $x\leq\infty$; see [3] for information on such
spaces. The topology on an extended metric space $(X,d)$ is defined in the
usual way using open balls. Nonexpansive functions are defined in the usual
way, and are continuous. Cauchy sequences are defined in the usual way, as are
then complete extended metric spaces. The completion of an extended metric
space is defined as usual and the function $c_{X}:X\rightarrow\overline{X}$ so
obtained is an isometry and is universal.

The analogue of Lemma 14 then goes through, with the same proof, as does that
of Lemma 15, with the evident definitions of quantitative $\Sigma$-algebras
over extended metric spaces and their homomorphisms. Next, the Wasserstein
algebras of order $p$ over an extended metric space are also defined as
before, and the extension of Lemma 12 to extended metric spaces then goes
through, with the same proofs, as do the following extensions of Theorems 13
and 16:

######  Theorem 17.

For any metric space X, $F_{p}(X)$ is the free extended metric Wasserstein
algebra of order $p$ over $X$, with universal arrow the Dirac delta function
$\delta:X\rightarrow F_{p}(X)$.

######  Theorem 18.

For any complete metric space X, $P_{p}(X)$ is the free complete extended
metric Wasserstein algebra of order $p$ over $X$, with universal arrow the
Dirac delta function.

We remark that in [17] the Wasserstein algebras of order $p$ are axiomatised
using quantitative equational logic. This logic makes use of quantitative
equations, which have the form $t=_{r}u$, where $t$ and $u$ are terms built as
usual from a finitary signature, and $r\in[0,1]$. If $t$ and $u$ denote
elements $a$ and $b$ of an extended metric space $X$, then $t=_{r}u$ holds if,
and only if, $d_{X}(a,b)\leq r$. The following axiom scheme of quantitative
equational logic axiomatises the Wasserstein algebras of order $p$:

$x=_{q_{1}}y,x^{\prime}=_{q_{2}}y^{\prime}\vdash
x+_{r}x^{\prime}=_{e}y+_{r}y^{\prime}$

where $q_{1},q_{2},q,e$ range over rationals in $[0,1]$ such that
$rq_{1}^{p}+(1-r)q_{2}^{p}\leq e^{p}$.

Our discussion has been in terms of barycentric algebras, but, as common in
algebra, other axiomatisations are possible. As an immediate example, noting
that the categories of barycentric algebras and convex spaces are equivalent,
let us define Wasserstein convex spaces of order $p$ to be quantitative convex
spaces which obey the natural Wasserstein condition of order $p$ for convex
spaces, viz that, for all $n\geq 1$ we have:

$\begin{array}[]{lclr}d(\sum^{n}_{i=1}r_{i}x_{i},\sum^{n}_{i=1}r_{i}x^{\prime}_{i})^{p}&\leq&\sum^{n}_{i=1}r_{i}d(x_{i},x^{\prime}_{i})^{p}\end{array}$

Then the categories of Wasserstein barycentric algebras of order of $p$ and
Wasserstein convex spaces of order of $p$ are equivalent, as are their
subcategories of algebras over complete metric spaces. One then immediately
obtains from the above work characterising free Wasserstein barycentric
algebras of order of $p$ corresponding results characterising free Wasserstein
convex spaces of order of $p$.

The situation is more complex if we consider instead midpoint (or mean-value
or medial mean) algebras, see, e.g., [15, 9]. These algebras are the
commutative, idempotent, medial groupoids. That is, they have a binary
operation, which we write as $\oplus$, subject to the following laws:

$\displaystyle x\oplus y$ $\displaystyle=y\oplus x$ (C) $\displaystyle x\oplus
x$ $\displaystyle=x$ (I) $\displaystyle(x\oplus u)\oplus(v\oplus z)$
$\displaystyle=(x\oplus v)\oplus(u\oplus z)$ (M)

One can define binary convex combinations $x+_{r}y$ in these algebras where
$r\leq 1$ is a dyadic fraction (i.e., one of the form $\frac{m}{2^{n}}$), and
they obey analogues of the barycentric axioms. The free such algebra over a
set consists of all finite probability distributions with dyadic weights, see
[11, Theorems 2.14 and 2.15].

Every barycentric algebra evidently yields a midpoint algebra by setting
$x\oplus y=x+_{0.5}y$, and we then have a full and faithful functor to the
category of midpoint algebras, which acts as the identity on morphisms;
however it is not an equivalence of categories, as not every midpoint algebra
can be extended to a barycentric algebra with the same carrier 111The free
midpoint algebra over two generators ($a$ and $b$, say) cannot be so extended.
It consists of all formal dyadic fractional convex combinations of $a$ and
$b$. If, for the sake of contradiction, there was such an extension then we
would have $a+_{r}b=a+_{s}b$ for some $r$ and $s$ with $r$ not a dyadic
fraction and $s$ a dyadic fraction. But, according to a lemma of Neumann (see
[18, Lemma 4]), if the equation $a+_{r}b=a+_{s}b$ holds for two different
$r,s\in(0,1)$ in a barycentric algebra, then it holds for all different
$r,s\in(0,1)$ in that algebra. So, in our case, taking $r,s\in(0,1)$ to be two
different dyadic fractions we obtain the desired contradiction..

The situation changes when we move to quantitative algebras. Define
Wasserstein midpoint algebras of order $p$ to be quantitative midpoint
algebras which satisfy the condition

$\displaystyle d(x\oplus y,x^{\prime}\oplus y^{\prime})^{p}$
$\displaystyle\leq d(x,x^{\prime})^{p}\oplus d(y,y^{\prime})^{p}$

Then, following the argument of Theorem 13, we see that, for any metric space
X, $F_{p}(X)$, with its natural midpoint algebra structure, is the free
Wasserstein midpoint algebra of order $p$ over $X$. Next, note that, for
complete $X$, $P_{p}(X)$ is even generated by the finite probability
distributions with dyadic fractional weights, as, by Lemma, $x+_{r}y$ is
Hölder continuous in $r$, and so, if a sequence $r_{n}$ in $[0,1]$ converges
to $r$, then the sequence $x+_{r_{n}}y$ is Cauchy and converges to $x+_{r}y$.
With that, now following the argument of Theorem 16, we see that $P_{p}(X)$
forms the free complete Wasserstein midpoint algebra of order $p$ over $X$.

The construction of midpoint algebras from barycentric algebras yields a full
and faithful functor from the category of Wasserstein barycentric algebras of
order $p$ over complete metric spaces to Wasserstein midpoint algebras of
order $p$ over complete metric spaces. We now sketch a proof that this is in
fact an equivalence of categories. It suffices to show that every complete
Wasserstein midpoint algebra of order $p$ can be extended to a complete
Wasserstein barycentric algebra of order $p$ with the same carrier. Let $A$ be
such a midpoint algebra. There is a unique nonexpansive morphism
$h:P_{p}(A)\rightarrow A$ of Wasserstein midpoint algebras of order $p$
extending the identity on $A$ along the unit. Using this, one inherits the
Hölder continuity of $+_{r}$ on $A$, for dyadic $r$ from that on $P_{p}(A)$.
Then one can define $x+_{r}y\in A$ for $x,y\in A$ as the limit of the sequence
$x+_{r_{n}}y$ where $r_{n}$ is a chosen sequence of dyadic fractions
converging to $r$, noting that the sequence $x+_{r_{n}}y$ is Cauchy by Hölder
continuity.

## References

  * [1] G. Basso, A Hitchhiker’s guide to Wasserstein distances, available at: http://n.ethz.ch/~gbasso/, 2015.
  * [2] F. van Breugel, The metric monad for probabilistic nondeterminism, Unpublished note, available at http://www.cse.yorku.ca/~franck/research/drafts/monad.pdf, 2005\.
  * [3] D. Burago, Y.D. Burago, and S. Ivanov, _A course in metric geometry_ , Vol. 33, American Mathematical Society, 2001.
  * [4] P. Clement and W. Desch, An elementary proof of the triangle inequality for the Wasserstein metric, _Proceedings of the American Mathematical Society_ , 136(1), 333–339, 2008.
  * [5] D.E. Edwards, A simple proof in Monge-Kantorovich duality theory, _Studia Math._ , 200(1), 67–77, 2010.
  * [6] T. Fritz and P. Perrone, A Probability Monad as the Colimit of Finite Powers, arXiv: 1712.05363, 2017.
  * [7] D.H. Fremlin, _Measure Theory, Volume 4: Topological Measure Spaces_ , Torres Fremlin, 2006.
  * [8] M. Giry, A categorical approach to probability theory, _Categorical aspects of topology and analysis_ , Lecture Notes in Mathematics, Vol. 915, 68–85, Springer, 1982.
  * [9] R. Heckmann, Probabilistic domains, _Proc. 19th. International Colloquium on Trees in Algebra and Programming_ , Lecture Notes in Computer Science, Vol. 787, 142–156, Springer, 1994.
  * [10] C. Heunen, O. Kammar, S. Staton, and H. Yang, A convenient category for higher-order probability theory, _Proc. 32nd. Annual Symposium on Logic in Computer Science_ , 1–12, IEEE, 2017.
  * [11] J. Ježek and T. Kepka, Free commutative idempotent abelian groupoids and quasigroups, _Acta Universitatis Carolinae, Mathematica et Physica_ , 17(2), 13–19, 1976.
  * [12] C. Jones, _Probabilistic non-determinism_ , Ph.D. Thesis, Department of Computer Science, The University of Edinburgh, 197 pages, available at https://www.era.lib.ed.ac.uk/handle/1842/413, 1990\.
  * [13] C. Jones and G.D. Plotkin, A probabilistic powerdomain of evaluations, _Proc. 4th. Annual Symposium on Logic in Computer Science_ , pp. 186–195, IEEE, 1989.
  * [14] K. Keimel and G.D. Plotkin, Mixed powerdomains for probability and nondeterminism, _Logical Methods in Computer Science_ , 13(1:2), 1–84, 2017.
  * [15] S. Kermit, Cancellative medial means are arithmetic, _Duke Math J._ , 37, 439–445,1970.
  * [16] F.W. Lawvere, The category of probabilistic mappings, Preprint, available at https://ncatlab.org/nlab/files/lawvereprobability1962.pdf, 1962.
  * [17] R. Mardare, P. Panangaden, and G.D. Plotkin, Quantitative Algebraic Reasoning, _Proc. 31st Annual Symposium on Logic in Computer Science_ , 700–709, 2016.
  * [18] W.D. Neumann,  On the quasivariety of convex subsets of affine spaces,  Archiv der Mathematik, 21:11–16, 1970.
  * [19] K.R. Parthasarathy, _Probability measures on metric spaces_ , Academic Press, 1967.
  * [20] A.B. Romanowska and J.D.H. Smith, _Modes_ , World Scientific, Singapore, 2002.
  * [21] M.H. Stone, Postulates for the barycentric calculus, _Annali di Matematica Pura ed Applicada_ , Serie IV, 29, 25–30, 1942.
  * [22] T. Šwirszcz, Monadic functors and convexity, emphBulletin de l’Académie Polonaise des Sciences, Ser. Sci. Math. Astronom. Phys, 22, 39–42, 1974.
  * [23] C. Villani, _Topics in optimal transportation_ , Vol. 58 of Graduate Studies in Mathematics, American Mathematical Society, 2003.
  * [24] C. Villani, _Optimal transport: old and new_ , Vol. 338, Springer Science & Business Media, 2008.