Map from the Multiset Monad to the Giry Monad: From Data to Probabilities

Question

The Mulitiset monad, aka the free commutative monoid monad or "Bag" monad, takes a set to the set of all Multisets for that set. A Multiset is like a set, but can have duplicates. It is used in computer science as the Bag monad, where the Bag is a data structure that can take in symbols or readings from a set and pop them out in random order (ie there is no ordering for the data). There is a monad that captures this, $(M, \mu, \eta)$ where the product $\mu: M \cdot M \rightarrow M$ works by taking a Multiset of Multisets, dissolving the inner container walls, and making one big Multiset.

The Giry Monad, $(G, \mu_G, \eta_G)$ is meant to capture probability measures. The functor, $G$, takes a set to the set of probability measures on that set. The product axiom is described in a comment here and goes as follows:

A probability measure on an affine space has an average value (also called expectation or integral), which is a point in that affine space. Apply this to the affine space of probability measures on X. In other words, a measure on the space of measures determines a (weighted) average of those measures.

Every Multiset has an associated probability measure that gives the probability of finding one of the set elements in that Multiset. This must mean that there is a transformation from the Multiset monad to the Giry monad.

Could someone write down, in detail, what this transformation is and give some interpretations of it too.

Some restrictions have been suggested.

1. We restrict to finite multisets
2. Because $M$ is on Set and $G$ is usually on a category of nice topological spaces, we will restrict $G$ to Set by viewing a set as a discrete topological space.

I will accept any answer with these restrictions. If you have a general answer, please also post that.

Answer 1

The intuition described in the question can be made precise as a natural map from the finite-multiset monad to a certain monad of (non-normalised) measures. However, this map doesn’t factor through the discrete Giry monad; in fact, there is no monad morphism from either the finite-multiset monad or the non-empty-finite-multiset monad to the discrete Giry monad.

Specifically, define monads on $\newcommand{\Set}{\mathbf{Set}}\Set$ by:

• $MX$ is the set of finite multisets on $X$, with monad structure as defined in the question;
• $HX$ is the set of finitely supported measures on $X$, with monad structure defined as for the Giry monad;
• $GX \subseteq HX$ is the set of finitely supported probability measures on $X$, with the induced monad structure (i.e. $G$ is a version of the Giry monad).

(Note these are not the original Giry monad, since these are on sets not spaces, and hence require the restriction to finitely or countably supported measures in order to define the monad multiplication.)

Then the natural transformation $\alpha : M \to H$ sending a finite multiset $m$ from $X$ to the measure $\mu(x) = |x \in m|$ is a monad morphism. Indeed, it is a monomorphism, and can be seen as including $M$ as the submonad of integer-valued finitely supported measures within $H$. Similarly the inclusion natural transformation $\iota : G \to H$ is a monad morphism by definition.

However, there is no natural transformation $M \to G$ (so, a fortiori, no transformation $H \to G$): for any set $X$ with two distinct elements $x, y$, the empty multiset in $X$ is in the image of both $Mi_x$ and $Mi_y : M1 \to MX$ (where $i_x : 1 \to X$ picks out $x$, and $i_y$ similarly), so its image in $GX$ should be in the image of both $Gi_x$, $Gi_y$; but these maps have disjoint images (they pick out the point measures concentrated on $x$ and $y$ respectively).

Restricting to the monads $M'$, $H'$ of non-empty multisets / nonzero measures, there is at least a natural transformation $\nu : H' \to G$, sending a measure to its normalised probability measure (and hence a composite transformation $M' \to G$). However, this is \emph{not} a monad map, nor is the composite $\nu \alpha : M \to G$. Concretely, $\nu \alpha$ doesn’t preserve monad multiplication (and so $\nu$ can’t): given a set $X$ with distinct elements $x,y$, $\{\{x,x\},\{y\}\} \in M'M'X$ goes to the half-and-half measure if you normalise the components then multiply in $G$, but to the two-thirds/one-third measure if you multiply in $M$ and then normalise it.

In fact, there is no monad morphism $M' \to G$. Suppose given any natural transformation $\beta : M' \to G$. A symmetry/naturality argument shows that any multiset from $X$ with all nonzero multiplicities equal must be sent by $\beta$ to the uniform distribution on the corresponding subset of $X$. But any multiset (like $\{x,x,y\}$ above) arises by multiplication from a multiset with all nonzero multiplicities 1, whose elements each involve only one element. So if $\beta$ preserved multiplication, it would have to send any multiset $m$ to the uniform distribution on the set of elements occurring in $m$. This determines $\beta$ fully; but then this can’t preserve multiplication, since the uniform distributions don’t form a submonad of $G$.