nLab monads of probability, measures, and valuations

Idea

In many categorical approaches to probability theory, one considers a category of spaces, such as measurable spaces or topological spaces, and equips this category with a monad whose functor part assigns to each space $X$ a space $P X$ of measures, probability measures, or valuations on $X$, or a variation thereof.

For probability theory, this can be interpreted as adding to the points of a space $X$ new “random points”, modelled as probability measures or valuations. The old points, which we can think of as deterministic, are embedded in $P X$ via the unit of the monad $X\to P X$. Just as well, the Kleisli morphisms of $P$ can be seen as stochastic maps. (Monads can be seen as ways of extending our spaces and functions to account for new phenomena, see for example extension system and monad in computer science.) Note that these probability measures are technically different from random elements: they rather correspond to the laws of the random elements.

Algebras of probability and measure monads can be interpreted as generalized convex spaces or conical spaces of a certain kind. For probability theory, in particular, the algebras of a probability monad can be seen as spaces equipped with a notion of expectation value of a random variable.

The details vary depending on the monad and on the category under consideration.

Many choices of categories and of monads are possible, depending on which aspects of measure theory or probability one wants to study. See the table below for more details.

Note that “probability monad” and “measure monad” are not used here as technical terms with a definition. Here we just explain what most monads of this kind look like. (There are ongoing works which may give a general, precise definition of probability monad.) The term “probability monad” was coined by Giry (see here), to refer to what we today call the Giry monad.

Functor, unit and multiplication

The functor: random outcomes

The basic idea, that holds for all monads of this sort, is that of forming spaces of random elements, or rather their laws.

Consider a category $C$, whose objects we can think of as “spaces of outcomes” with possibly extra structure, such as measurable spaces, or topological spaces, or even just sets. A probability monad assigns to each space $X$ a space $P X$ which we can think of as a space of “laws of random outcomes on $X$” or other measure-like entities. For example,

• The distribution monad assigns to each set the space of finite distributions on it.
• The Giry monad assigns to each measurable space the space of probability measures over it.
• The extended probabilistic powerdomain assigns to each topological space the space of continuous valuations on it.
• The Kantorovich monad assigns to each metric space the Wasserstein space over it.

(See also the table below.)

A possible interpretation of probability monads, which uses the interpretation of monads as encoding generalized theories, is that $P X$ is a space of “formal generalized convex combinations” (in the sense of convex space) of points of $X$. For instance, for the distribution monad, given the set $\{heads,tails\}$ of possible outcomes of a coin flip, the set $P X$ contains for example the distribution that assigns probability $1/2$ to both outcomes. This can be thought of as the formal convex combination

$$\frac{1}{2}\, heads + \frac{1}{2}\,tails.$$

On the morphisms, the functor gives for example the pushforward of measures.

The unit: deterministic random variables

The unit of the monad gives, for each space of outcomes, a map $X\to P X$, which we can think of as picking out “those outcomes which are not really random”, or “Dirac delta” (see Dirac measure and Dirac valuation).

These can be seen as the laws of a deterministic random variable.

The multiplication: mixing probability measures.

The multiplication of the monad is a map $P P X\to P X$ for all objects $X$. This can be thought of as of mixing or averaging probability measures.

The following example is taken from Perrone ‘19, Example 5.1.2. Suppose that you have two coins in your pocket. Suppose that one coin is fair, with “heads” on one face and “tails” on the other face; suppose the second coin has “heads” on both sides. Suppose now that you draw a coin randomly, and flip it. We can sketch the probabilities in the following way: Let $X$ be the set $\{heads,tails\}$. A coin gives a law according to which we will obtain “heads” or “tails” so it determines an element of $P X$. Since the choice of coin is also random (we also have a law on the coins), the law on the coins determines an element of $P P X$. By averaging, the resulting overall probabilities are

In other words, the “average” or “mixture” can be thought of as an assignment $E:P P X\to P X$, from laws of “random random variables” to laws of ordinary random variables.

Algebras: expectation values

According to the interpretation of probability monads in terms of “formal generalized convex combinations”, the algebras of a probability monad are then spaces equipped with a way of evaluating these expressions to a result, which we can see as a generalized “mixture”, “average”, or “expectation value”. (Expectation values play a very important role in probability: probability monads can encode them via their algebras.)

In other words, algebras of probability monads can be thought of as generalizations of convex sets, depending on the actual category and monad in question. For example,

• The algebras of the distribution monad are convex spaces.
• The algebras of the Radon monad are compact convex subsets of locally convex topological vector spaces.
• The algebras of the Kantorovich monad are closed convex subsets of Banach spaces.

(See also the table below.)

If the measure are not required to be normalized, instead of (generalized) convex combinations one should think of linear combinations with non-negative coefficients, and so as algebras one gets a generalization of conical spaces instead.

Kleisli morphisms: random maps

The basic interpretation of a Kleisli morphism, i.e. a map $X\to P Y$, is that of a map with a random outcome. For example,

• For the distribution monad, Kleisli morphisms are stochastic maps (or stochastic matrices).
• For the Giry monad, Kleisli morphisms are Markov kernels.
• …and so on.

The Kleisli composition recovers exactly the Chapman-Kolmogorov formula? for the composition of stochastic maps. In the language of conditional probability, this reads as

$$p(z|x) = \sum_y p(z|y) \, p (y|x)$$

for the discrete case, and as

$$p(A|x) = \int_Y p(A|y) \, d p(y|x)$$

for the continuous case.

(See Giry’s original article for the details, as well as the introductions given in Perrone ‘18, Section 1.1 and Perrone ‘19, Example 5.1.13).

Kleisli categories of probability monads are often instances of Markov categories.

Monoidal structure: products and marginals

Probability monads are usually defined on monoidal categories, in particular on cartesian monoidal categories. On product spaces $X\times Y$, the object $P(X\times Y)$ has the interpretation of containing joint distributions. Given a joint distribution, one can form the marginals by pushing forward along the product projections $X\times Y\to X$ and $X\times Y\to Y$. This is in general a destructive operation, since stochastic dependence may be discarded.

Given marginal distributions, one can form a canonical joint distribution by forming the product distribution. This is encoded by a monoidal structure on the probability monad (or equivalently, a commutative strength), a map which satisfies particular compatibility conditions. The Giry monad is monoidal on the category Meas with the cartesian product. Similar statements are true for most other probability and measure monads.

When the monad is affine, one has that a product probability is necessarily the product of its marginals. This is the case for monads of probability measures, but not for monads of unnormalized measures.

More on this at joint and marginal probability.

Duality

(…work in progress…)

Detailed list

Monad ($P$)	Category	Elements/points of $P X$	Extra structure of $P X$	$P$-Algebras	References
distribution monad (a.k.a. finitary Giry monad, convex combination monad)	Set	convex combinations or finitely-supported probability measures	(just a set)	convex spaces	Fritz '09, Jacobs '18
Giry monad	Meas	probability measures	initial σ-algebra of evaluation maps	Full characterization unknown. See also here.	Lawvere '62, Giry '80
Giry monad	Pol	Borel probability measures	initial topology of integration maps	Full characterization unknown. See also here.	Giry '80
Probability monad on QBS?	quasi-Borel spaces	Equivalence classes of random variables	quasi-Borel structure inherited by the cartesian closed structure	Full characterization unknown.	HKSY '17
Radon monad	Comp	Radon probability measures (or continuous valuations)		compact convex subsets of locally convex topological vector spaces	Swirszcz '74, Keimel '08
ordered Radon monad	CompOrd	Radon probability measures (or continuous valuations)	weak topology w.r.t. continuous functions, stochastic order	compact convex subsets of ordered? locally convex topological vector spaces	Swirszcz '74, Keimel '08
measure monad on Top	Top	τ-additive measures	A-topology, stochastic order	Full characterization unknown. See also here.	F-P-R '19
probabilistic powerdomain?	dcpo, continuous domains?	continuous valuations	stochastic order	abstract probabilistic domains? (continuous case)	J-P '89
extended probabilistic powerdomain	Top, stably compact spaces	continuous valuations	initial topology of evaluation maps, stochastic order	Full characterization unknown. Dedicated section here	Heckmann '96, A-J-K '04, GL-J '19, F-P-R '19
valuation monad on locales?	Loc	continuous valuations	initial topology of evaluation maps	…	Vickers '11
Kantorovich monad	complete metric spaces	Radon probability measures of finite first moment	Kantorovich-Wasserstein metric	closed convex subsets of Banach spaces	van Breugel '05, F-P '19
ordered Kantorovich monad	complete L-ordered? metric spaces	Radon probability measures of finite first moment	Kantorovich-Wasserstein metric, stochastic order	closed convex subsets of ordered Banach spaces?	F-P '20
Baire monad	Weakly Hausdorff quotients of countably-based topological spaces	Baire measures	topology induced by cartesian closedness	Full characterization unknown	K-P '24
Riesz monad	compactly generated weakly Hausdorff topological spaces	$k$-regular probability measures	topology induced by cartesian closedness	Full characterization unknown	K-P '24

(…to be expanded…)

See also

• monad, algebra over a monad, Kleisli category
• commutative monad, affine monad
• monad (in computer science)
• Giry monad, Markov kernel, Stoch
• categorical probability, Markov category
• joint and marginal distributions
• probability theory, measure theory
• valuation (measure theory)
• expectation value

References

• W. Lawvere, The category of probabilistic mappings, ms. 12 pages, 1962

  (Lawvere Probability 1962)

• Michèle Giry, A categorical approach to probability theory, Categorical aspects of topology and analysis (Ottawa, Ont., 1980), pp. 68–85, Lecture Notes in Math. 915 Springer 1982.

• T. Swirszcz, Monadic functors and convexity, Bulletin de l’Academie Polonaise des Sciences 22, 1974 (pdf)

• Klaus Keimel, The monad of probability measures over compact ordered spaces and its Eilenberg-Moore algebras, Topology and its Applications, 2008 (doi:10.1016/j.topol.2008.07.002)

• Reinhold Heckmann, Spaces of valuations, Papers on General Topology and Ap-plications, 1996 (doi:10.1111/j.1749-6632.1996.tb49168.x,pdf)

• Mauricio Alvarez-Manilla, Achim Jung, Klaus Keimel, The probabilistic powerdomain for stably compact spaces, Theoretical Computer Science 328, 2004. Link here.

• C. Jones and Gordon. D. Plotkin?, A probabilistic powerdomain of evaluations, LICS 4, 1989. (doi:10.1109/LICS.1989.39173)

• Jean Goubault-Larrecq and Xiaodong Jia, Algebras of the extended probabilistic powerdomain monad, ENTCS 345, 2019

  (doi:10.1016/j.entcs.2019.07.015)

• Tobias Fritz, Paolo Perrone and Sharwin Rezagholi, Probability, valuations, hyperspace: Three monads on Top and the support as a morphism, Mathematical Constructions in Computer Science 31(8), 2021. arXiv.

• Steve Vickers, A monad of valuation locales, 2011. Link here.

• Franck van Breugel, The metric monad for probabilistic nondeterminism, unpublished, 2005. (pdf)

• Tobias Fritz and Paolo Perrone, A probability monad as the colimit of spaces of finite samples, Theory and Applications of Categories 34, 2019. (pdf)

• Tobias Fritz and Paolo Perrone, Stochastic order on metric spaces and the ordered Kantorovich monad, Advances in Mathematics 366, 2020. (arXiv:1808.09898)

• Bart Jacobs, From probability monads to commutative effectuses, Journal of Logical and Algebraic Methods in Programming 94, 2018.

  (doi:10.1016/j.jlamp.2016.11.006)

• Tobias Fritz, Convex spaces I: definitions and examples, 2009. (arXiv:0903.5522)

• Chris Heunen, Ohad Kammar, Sam Staton and Hongseok Yang, A convenient category for higher-order probability theory, Proceedings of LICS 2017. (arXiv)

• Sean Moss?, Paolo Perrone, Probability monads with submonads of deterministic states, LICS 2022. (arXiv:2204.07003)

• Tobias Fritz, Tomáš Gonda, Paolo Perrone, Eigil Fjeldgren Rischel, Representable Markov categories and comparison of statistical experiments in categorical probability, Theoretical Computer Science 961, 2023. (arXiv:2010.07416)

• Peter Kristel, Benedikt Peterseim, A topologically enriched probability monad on the cartesian closed category of CGWH spaces. (arXiv)

An account in terms of codensity monads in:

• Ruben Van Belle, Probability monads as codensity monads. Theory and Applications of Categories 38 (2022), 811–842, (tac)

An introduction to some of the concepts can be also found in:

• Paolo Perrone, Notes on Category Theory with examples from basic mathematics, Chapter 5. (arXiv)

• Paolo Perrone, Categorical probability and stochastic dominance in metric spaces, PhD thesis, Chapter 1. (pdf)

• Tobias Fritz and Paolo Perrone, Monads, partial evaluations, and rewriting, MFPS 36, 2020 - Section 6. (arXiv)

and in the following video lectures:

• Arthur Parzygnat, Categorical probability, video playlist. (YouTube)

• Paolo Perrone, What is a probability monad?, tutorial. (YouTube)

category: probability