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.

- We restrict to finite multisets
- 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.

finiteMultisets here? $\endgroup$ – Alex Kruckman Sep 16 '18 at 16:43