Let $\mathsf{Stoch}$ denote the Kleisli category of the Giry monad. That is, $\mathsf{Stoch}$ is a category whose objects are measurable spaces and for which a morphism $f\in\mathsf{Stoch}(X,Y)$ is a map sending points in $X$ to probability measures on $Y$; see nLab: Giry monad for details.

Let $\mathsf{Met}$ denote the symmetric monoidal category of metric spaces $(X,d)$ and short maps (functions $f\colon X\to Y$ satisfying $d(x_1,x_2)\geq d(fx_1,fx_2)$ for all $x_1,x_2\in X$).

Question: Is there a way to enrich $\mathsf{Stoch}$ in $\mathsf{Met}$?

In other words, I'm looking for a way to endow each hom-set $\mathsf{Stoch}(X,Y)$ with a metric space structure in such a way that the composition operation is short: $$ d(f_1,f_2)+d(g_1,g_2) \geq d(g_1\circ f_1, g_2\circ f_2) $$

The upshot would be that when working in $\mathsf{Stoch}$, diagrams would not simply either commute or not commute; they would commute up to some distance, and this distance would behave sensibly under "diagram chasing".


A way to enrich $\mathsf{Stoch}$ could be as follows.

Let $X$ be a measurable space and let $PX$ be the space of probability measures over $X$. We can equip $PX$ with the total variational distance, which is given by the following equivalent forms. $$ d(p,q) \;=\; \sup_{A\subseteq X} |p(A) - q(A)| \;=\; \sup_{f:X\to[0,1]} \left| \int_X f\, dp - \int_X f\; dq \right| . $$ Above, and in what follows, the subsets $A\subseteq X$ and the functions $f:X\to\Bbb{R}$ are assumed measurable.

Now first of all let $f:X \to Y$ be a measurable (deterministic) function. Denote by $f_*:PX\to PY$ the pushforward of measures (for category theorists, the action of the functor $P$ on the morphisms). We have \begin{align*} d( f_*p, f_*q ) \;&=\; \sup_{B\subseteq Y} |f_*p(B) - f_*q(B)| \\\ \;&=\; \sup_{B\subseteq Y} |p(f^{-1}(B)) - q(f^{-1}(B))| \\\ \;&\le\; \sup_{A\subseteq X} |p(A) - q(A)| \\\ \;&=\; d( p, q ) , \end{align*} which means that $f_*:PX\to PY$ is short for the metric just defined. This will be of use later.

We can equip now the sets $\mathsf{Stoch}(X,Y)$ with the "product" or "$L^\infty$" metric construction induced by the one on $PY$, as follows. We use the following notation, a stochastic map $k:X\to PY$ evaluated at a point $x\in X$ gives the measure $k_x\in PY$. Now for stochastic maps $k,h:X\to PY$, we set $$ d(k,h) \;=\; \sup_{x\in X} d\big( k_x, h_y \big) . $$ This number is bounded by $1$. (Thanks to Martin Hairer for pointing this out, see the comments.)

We now have to prove that the (Kleisli) composition of $\mathsf{Stoch}$ is short. Given $h:X \to PY$ and $l: Y \to PZ$, their Kleisli composition, which we denote by $lh$, is given by the Chapman-Kolmogorov formula. Explicitly, for every measurable $C \subseteq Z$, we have $$ lh_x(C) \;=\; \int_{PZ} q(C) \,d(l_*h_x)(q) \;=\; \int_{Y} l_y(C) \,dh_x(y) . $$

Now, to see that postcomposition is short, let $h,k:X \to PY$ and $l: Y \to PZ$. We have \begin{align*} d( lh, lk ) \;&=\; \sup_{x\in X} \sup_{C\subseteq Z} | lh_x(C) - lk_x(C) | \\\ \;&=\; \sup_{x\in X} \sup_{C\subseteq Z} \left| \int_{PZ} q(C) \,d(l_*h_x)(q) - \int_{PZ} q(C) \,d(l_*k_x)(q) \right| \\\ \;&\le\; \sup_{x\in X} d\big( l_*h_x , l_*k_x \big) \\\ \;&\le\; \sup_{x\in X} d( h_x , k_x ) \\\ \;&=\; d( h, k ) . \end{align*} (We used the fact that the evaluation map $PX\to \Bbb{R}$ given by $p\mapsto p(A)$ for a measurable set $A\subseteq X$ is measurable for the $\sigma$-algebra on $PX$ in the construction of the Giry monad.)

To see that precomposition is short, let also $g: W \to PX$. Then \begin{align*} d( hg, kg ) \;&=\; \sup_{w\in W} \sup_{B\subseteq Y} | hg_w(B) - kg_w(B) | \\\ \;&=\; \sup_{w\in W} \sup_{B\subseteq Y} \left| \int_{X} h_x(B) \,dg_w(x) - \int_{X} k_x(B) \,dg_w(x) \right| \\\ \;&\le\; \sup_{w\in W} \int_{X} \sup_{B\subseteq Y} | h_x(B) - k_x(B) | \,d(g_w)(x) \\\ \;&=\; \sup_{w\in W} \int_{X} d( h_x, k_x ) \,d(g_w)(x) \\\ \;&\le\; d( h_x, k_x ) . \end{align*}

Consider now the set $\mathsf{Stoch}(X,Y)\times\mathsf{Stoch}(Y,Z)$. We can equip it either with the metric $$ d \big( (h_1,l_1), (h_2,l_2) \big) \;=\; \max\{ d(h_1,h_2), d(l_1,l_2) \}, $$ which corresponds to the metric of the cartesian (categorical) product of $\mathsf{Met}$, or with the metric $$ d \big( (h_1,l_1), (h_2,l_2) \big) \;=\; d(h_1,h_2) + d(l_1,l_2) , $$ which is the metric of the closed monoidal product of $\mathsf{Met}$ as an (i.e. enhibiting a hom-tensor adjunction).

For either choice, the map $\circ: \mathsf{Stoch}(X,Y)\times\mathsf{Stoch}(Y,Z) \to \mathsf{Stoch}(X,Z)$ given by composition is short. This gives the desired enrichment.

By the way, if we want talk about diagrams "commuting up to $\varepsilon$", then by definition of the metric, $\varepsilon$ has to be a uniform bound. For example, for the diagram $\require{AMScd}$ \begin{CD} A @>f>> B\\ @V m V V @VV n V\\ C @>>g> D \end{CD} to commute up to $\varepsilon$, in the sense that $d(n\circ f,g\circ m)\lt\varepsilon$, we need that $$ \sup_{a\in A} d\big(n(f(a)),g(m(a))\big) \;\lt\;\varepsilon, $$ where the distance above is the one of $D$. For that to happen, $\varepsilon$ needs to be independent of $a$, which is quite a strong condition in practice (if $A$ is not compact).

  • $\begingroup$ There are no infinite distances here, $d$ is bounded by $1$. (Your dual representation of TV is incorrect, you want $f \colon X \to [0,1]$.) Note also that the 'non-boring' case $d \neq 1$ is a fancy way of talking about Doeblin's condition which is 'rarely' verified 'in practice'. (Of course, maybe the OP has in mind some specific situation where it is relevant.) $\endgroup$ – Martin Hairer Nov 23 at 14:00
  • $\begingroup$ @MartinHairer Thank you! Let me add the corrections. $\endgroup$ – Paolo Perrone Nov 23 at 19:57

A boring way is to set $d(f,g)=1$ if $f$ and $g$ are different.

A slightly less boring way is to take $d(f,g)$ to be the supremum over $x$ of the probability that two independent variables with laws $f(x)$ and $g(x)$ differ. Different functions may then have a small distance if their image consists of distributions with atoms.


If you're willing to work with generalized metric spaces, then the answer is yes. $\mathsf{Stoch}$ is enriched over the category of convex spaces, which in turn is enriched over $V$-cat as there exists a closed functor from convex spaces to $V$-cat, where $V=([0,\infty], \ge)$ is the SMCC whose objects can be viewed as generalized metric spaces, and arrows viewed as short maps. This all follows from Meng's thesis, proposition 5. (Available at nLab)

You can actually say a little more by noting that $\mathsf{Stoch}$ is enriched over the category of super convex spaces, which differs from convex spaces in that one considers countable sums of one, rather than finite sums, and requires the morphisms to preserve the countable sums. (The proof of enrichment over super convex spaces is essentially identical to that found in Meng.) The benefit of working with (coseparated) super convex spaces is that it is a $*$-autonomous category.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.