From Multisets over Distributions to Distributions over Multisets

A well-known challenge in the semantics of programming languages is how to combine non-determinism and probability. At a technical level, the problem arises from the fact that there is a no distributive law between the powerset monad and the distribution monad -as noticed some twenty years ago by Plotkin. More recently, it has become clear that there is a distributive law of the multiset monad over the distribution monad. This article elaborates the details of this distributivity and shows that there is a rich underlying theory relating multisets and probability distributions. It is shown that the new distributive law, called parallel multinomial law, can be defined in (at least) four equivalent ways. It involves putting multinomial distributions in parallel and commutes with hypergeometric distributions. Further, it is shown that this distributive law commutes with a new form of zipping for multisets. Abstractly, this can be described in terms of monoidal structure for a fixed-size multiset functor, when lifted to the Kleisli category of the distribution monad. Concretely, an application of the theory to sampling semantics is included.

in [10], [11], with full credits, where variations have been investigated (see also [12]). The lack of a distributive law between P and D means that there is no semantically clean way to combine non-deterministic and probabilistic computation.

In contrast, multisets do distribute over probability distributions. This seems to have been folklore knowledge for some time. It is therefore hard to give proper credit to this observation. In [13, p.82] it is described how the set of distributions D(M ) on a commutative monoid M , can itself be turned into a commutative monoid. This is a somewhat isolated observation in [13], but by pushing this approach through one finds that it means that the distribution monad D on the category of sets lifts to the category of commutative monoids. Since the latter category is the category of Eilenberg-Moore algebras of the multiset monad M, some abstract categorical result tells that this is equivalent to the existence of a distributive law of monads MD ⇒ DM. Hence one can say that this law is implicit in [13], but without an explicit description. The existence of this law is also discussed in [14], but also without an explicit definition. A further source is [15], where the existence of this law is taken for granted, since the resulting composite DM is used as a monad. We simplify things, since [15] uses continuous instead of discrete distributions, but that is not essential. Also there, no explicit description of the distributive law is given.

This absence of an explicit description of the distributive law MD ⇒ DM is understandable, since it is quite complex. The main contribution of this paper is that it describes the distributive law in full detail -actually in four different ways -and that it develops a rich theory surrounding this law.

The distributive law MD ⇒ DM turns a multiset over distributions into a distribution over multisets. At the heart of this theory that we develop is the interaction of multisets and distributions. Recall that a multiset is like a set, except that elements may occur multiple times. A prime example of a multiset is an urn, containing multiple coloured balls. If the urn contains three red, five blue and two green balls, then we shall write it as a multiset 3|R + 5|B + 2|G over the set R, B, G of colours. This multiset clearly has size 10. A basic property of the distributive law is that it preserves size: it turns a K-sized multiset of distributions into a distribution over multisets of size K ∈ N.

When we draw a handful of balls from an urn, the draw itself may also be represented as a multiset. The classical multino-