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

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.

• "Every Multiset has an associated probability measure that gives the probability of finding one of the set elements in that Multiset." Don't you want to restrict to finite Multisets here? – Alex Kruckman Sep 16 '18 at 16:43
• Also, Multiset is a monad on Set, while the Giry monad is usually viewed as a monad on some category of sufficiently nice topological spaces, so you'll have to explain what you mean by a transformation between the two. One option is restrict the Giry monad to Set by viewing a set as a discrete topological space. Then $G(X)$ will be the set of probability measures on the full powerset of $X$. – Alex Kruckman Sep 16 '18 at 16:54
• If you restrict to finite Multisets and discrete spaces, isn't the transformation clear? Its component on the set $X$ is a map $\varphi_X\colon M(X)\to P(X)$, where $M(X)$ is the set of finite multisets with all elements in $X$, and $P(X)$ is the set of probability measures on $X$. Let $A\in M(X)$ be a finite multiset. Let $|A|$ be the cardinality of $A$, and for $x\in X$, let $A(x)$ be the number of occurrences of $x$ in $A$. Then $\varphi_X(A)$ is the probability measure $\mu$ on $X$ which gives measure $A(x)/|A|$ to the element $x$. Explicitly, $\mu(Y) = \sum_{x\in Y} A(x)/|A|$. – Alex Kruckman Sep 16 '18 at 16:54
• @AlexKruckman: That’s the obvious natural map, but doesn’t preserve monad multiplication. Consider $\{\{a,a\},\{b\}\} \in MM\{a,b\}$. If we multipliy it in $M$, then turn it into a probability measure, we get $\mu(\{a\}) = \frac{2}{3}$, $\mu(\{b\}) = \frac{1}{3}$. But if we send it to $G$ and multiply it there, we get the half-and-half measure; the multiplicity of $a$ gets normalised away. If we use a measure monad instead of a probability monad, I think this would work (with no normalisation by cardinality in the map). But for the Giry monad, I suspect there may be no non-trivial map. – Peter LeFanu Lumsdaine Sep 17 '18 at 7:56
• @PeterLeFanuLumsdaine Nice example, I was too quick. I'll leave my wrong comment there, since our two comments together might be helpful to others. – Alex Kruckman Sep 17 '18 at 14:06

## 1 Answer

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$.