nLab convex powerset of distributions monad




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


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

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

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

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

[r 1r k]={a 1r 1++a kr k|(a 1,,a k)[0,1] k& j=1 ka j=1}[\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)C(n) be the set of finitely generated convex subsets of Δ(n)\Delta(n).

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

  • It also has the structure of a convex space, with [r 1r k]+ p[s 1s l][\vec r_1\dots \vec r_k]+_p [\vec s_1\dots \vec s_l] defined to be

[pr 1+(1p)s 1, , pr k+(1p)s 1, , , , pr 1+(1p)s l, , pr k+(1p)s l]. \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)C(n):

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

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

f *([r 1r k])=(r 1,1f(1)++r 1,mf(m))(r k,1f(1)++r k,mf(m)). 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)).


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

x+ r(yz)=(x+ ry)(x+ rz) x +_r (y \oplus z) = (x +_r y) \oplus (x +_r z)

for all r(0,1)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, xy=xy(x+ 0.5y)x\oplus y = x \oplus y \oplus (x+_0.5 y), for:

xy=(xy)+ 0.5(xy)=(x+ 0.5x)(x+ 0.5y)(y+ 0.5x)(y+ 0.5y)=xy(x+ 0.5y).) 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.5z)(y+ 0.5x)(xy)+ 0.5(zx) (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.5z)(y+ 0.5z)x(y+ 0.5x)(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)][(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).


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.