  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.
