# nLab convex powerset of distributions monad

Contents

### Context

#### Measure and probability theory

measure theory

probability theory

## Applications

#### Categorical algebra

internalization and categorical algebra

universal algebra

categorical semantics

# Contents

## Idea

The convex powerset of distributions monad is a monad (or family of monads) that encompasses both non-determinism (via power sets) and probability (via probability distributions).

## Definition

The finitary version of the monad is defined as follows. First recall that for any finite set $n$, the set of probability distributions $\Delta(n)\subseteq [0,1]^n$,

$\Delta(n)=\{(r_1,\dots,r_n)\in[0,1]^n | \textstyle \sum_{i=1}^n r_i=1\}$

is the topological $(n-1)$-simplex. A subset $S\subseteq \Delta(n)$ is convex if it is closed under convex combinations, i.e. if $\vec r\in S$ and $\vec s\in S$ then $(a\vec r+(1-a) \vec s)\in S$ for any $a\in[0,1]$.

Any finite set of points $\{\vec r_1\dots \vec r_k\}\subseteq \Delta(n)$ generate a convex set (the convex hull):

$[\vec r_1\dots \vec r_k] = \{ a_1\vec r_1 + \dots +a_k\vec r_k | (a_1,\dots, a_k)\in [0,1]^k \& \textstyle \sum_{j=1}^k a_j=1 \}$

(Recall that the convex hull is not uniquely determined by such a set of points, since some points in the generating set maybe convex combinations of others.)

Let $C(n)$ be the set of finitely generated convex subsets of $\Delta(n)$.

• $C(n)$ has the structure of a semilattice, with $S\oplus T$ the union of $S$ and $T$ closed under convex combinations.

• It also has the structure of a convex space, with $[\vec r_1\dots \vec r_k]+_p [\vec s_1\dots \vec s_l]$ defined to be

$\array{[p\vec r_1+(1-p)\vec s_1,&\dots,&p\vec r_k+(1-p)\vec s_1,\\ \dots,&\dots,&\dots,\\ p\vec r_1+(1-p)\vec s_l,&\dots,&p\vec r_k+(1-p)\vec s_l].}$

We thus build a monad structure for $C(n)$:

• The unit, $\eta_n:n\to C(n)$, picks out the singleton sets containing the basis vectors: $\eta_n(1) = \{(1,0,\dots,0)\}$, $\eta_n(2) = \{(0,1,\dots,0)\}$, and so on.

• The bind, or Kleisli extension, takes a function $f:m\to C(n)$ to a function $f^*:C(m)\to C(n)$, given by using the convex and semilattice structures:

$f^*([\vec r_1\dots \vec r_k]) = (r_{1,1}f(1)+\dots+r_{1,m}f(m)) \oplus \dots\oplus (r_{k,1}f(1)+\dots+r_{k,m}f(m)).$

## Presentation

The finitary convex powerset of distributions monad is presented by an equational theory. This has the theory of convex spaces ($+_r$) together with the theory of semilattices ($\oplus$) and the axiom

$x +_r (y \oplus z) = (x +_r y) \oplus (x +_r z)$

for all $r\in (0,1)$.

(It may be tempting to think that this is a distributive law of monads, but it is not, because two sets of distributions are equated if they have the same convex hull. For instance, $x\oplus y = x \oplus y \oplus (x+_0.5 y)$, for:

$x \oplus y = (x \oplus y) +_0.5 (x \oplus y) = (x +_0.5 x)\oplus (x +_0.5 y) \oplus (y +_0.5 x) \oplus (y +_0.5 y) = x \oplus y \oplus (x +_0.5 y) \ .)$

The theory is not commutative, and so the monad is not a commutative monad. Indeed

$(x +_0.5 z) \oplus (y +_0.5 x) \neq (x \oplus y) +_0.5 (z \oplus x)$

since the right hand side is equal to $(x +_0.5 z) \oplus (y+_0.5 z) \oplus x \oplus (y+_0.5 x)$, and we can compare the convex hulls of the two points of the left-hand side $[(0.5,0,0.5),(0.5,0.5,0)]$ and the four points of the right-hand side [(0.5,0,0.5),(0,0.5,0.5),(1,0,0),(0.5,0.5,0)], which are different convex subsets of the 2-simplex (triangle).

## References

Convex powersets of distributions have been considered by various authors over the last few decades.

A recent extension to metric spaces, including a literature survey is:

The theory in the finitely generated case is shown to be a “distributive tensor” of probability and non-determinism, and axioms and geometric nature is spelt out in Chapter 6 of:

• Kwok-Ho Cheung, Distributive Interaction of Algebraic Effects, PhD thesis, Oxford 2017 [university archive].

The theory is further spelt out, amongst other things, in:

• Filippo Bonchi, Ana Sokolova, Valeria Vignudelli: The Theory of Traces for Systems with Nondeterminism, Probability, and Termination, Logical Methods in Computer Science 18 2 (2022) [doi:10.46298/lmcs-18(2:21)2022]

The case with unbounded, infinite joins is earlier considered here:

In domain theory, convex powersets of distributions are explored and axiomatized amongst other approaches by

• Daniela Varacca: Probability, Nondeterminism and Concurrency: Two Denotational Models for Probabilistic Computation. PhD thesis, Univ. Aarhus (2003) [brics:DS/03/14]

and analyzed as “convex powercones” by

Last revised on January 20, 2024 at 11:22:56. See the history of this page for a list of all contributions to it.