internalization and categorical algebra
algebra object (associative, Lie, …)
internal category ($\to$ more)
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 $n$, the set of probability distributions $\Delta(n)\subseteq [0,1]^n$,
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):
(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
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:
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
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:
The theory is not commutative, and so the monad is not a commutative monad. Indeed
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).
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:
The theory is further spelt out, amongst other things, in:
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
and analyzed as “convex powercones” by
Michael W. Mislove, Nondeterminism and probabilistic choice: Obeying the laws, in: Proc. CONCUR
2000, Lecture Notes in Computer Science 1877, Springer (2000) 350–364 [doi:10.1007/3-540-44618-4_26].
Regina Tix, Klaus Keimel, Gordon D. Plotkin: Semantic domains for combining probability and non-determinism, Electronic Notes in Theoretical Computer Science, 222 (2009) 3–99 [doi:10.1016/j.entcs.2009.01.002]
Jean Goubault-Larrecq: Prevision domains and convex powercones, in: Proc. FOSSACS 2008, Lecture Notes in Computer Science 4962, Springer (2008) 318–333 [doi:10.1007/978-3-540-78499-9_23]
Last revised on January 20, 2024 at 11:22:56. See the history of this page for a list of all contributions to it.