Giry monad

In mathematics, the Giry monad is a construction that assigns to a measurable space a space of probability measures over it, equipped with a canonical sigma-algebra. ^{[1] [2] [3] [4] [5]} It is one of the main examples of a probability monad.

It is implicitly used in probability theory whenever one considers probability measures which depend measurably on a parameter (giving rise to Markov kernels), or when one has probability measures over probability measures (such as in de Finetti's theorem).

Like many iterable constructions, it has the category-theoretic structure of a monad, on the category of measurable spaces.

Construction

The Giry monad, like every monad, consists of three structures: ^{[6] [7] [8]}

• A functorial assignment, which in this case assigns to a measurable space ${\displaystyle X}$ a space of probability measures ${\displaystyle PX}$ over it;
• A natural map ${\displaystyle \delta :X\to PX}$ called the unit, which in this case assigns to each element of a space the Dirac measure over it;
• A natural map ${\displaystyle {\mathcal {E}}:PPX\to PX}$ called the multiplication, which in this case assigns to each probability measure over probability measures its expected value.

The space of probability measures

Let ${\displaystyle (X,{\mathcal {F}})}$ be a measurable space. Denote by ${\displaystyle PX}$ the set of probability measures over ${\displaystyle (X,{\mathcal {F}})}$. We equip the set ${\displaystyle PX}$ with a sigma-algebra as follows. First of all, for every measurable set ${\displaystyle A\in {\mathcal {F}}}$, define the map ${\displaystyle \varepsilon _{A}:PX\to \mathbb {R} }$ by ${\displaystyle p\longmapsto p(A)}$. We then define the sigma algebra ${\displaystyle {\mathcal {PF}}}$ on ${\displaystyle PX}$ to be the smallest sigma-algebra which makes the maps ${\displaystyle \varepsilon _{A}}$ measurable, for all ${\displaystyle A\in {\mathcal {F}}}$ (where ${\displaystyle \mathbb {R} }$ is assumed equipped with the Borel sigma-algebra). ^[6]

Equivalently, ${\displaystyle {\mathcal {PF}}}$ can be defined as the smallest sigma-algebra on ${\displaystyle PX}$ which makes the maps

${\displaystyle p\longmapsto \int _{X}f\,dp}$

measurable for all bounded measurable ${\displaystyle f:X\to \mathbb {R} }$. ^[9]

The assignment ${\displaystyle (X,{\mathcal {F}})\mapsto (PX,{\mathcal {PF}})}$ is part of an endofunctor on the category of measurable spaces, usually denoted again by ${\displaystyle P}$. Its action on morphisms, i.e. on measurable maps, is via the pushforward of measures. Namely, given a measurable map ${\displaystyle f:(X,{\mathcal {F}})\to (Y,{\mathcal {G}})}$, one assigns to ${\displaystyle f}$ the map ${\displaystyle f_{*}:(PX,{\mathcal {PF}})\to (PY,{\mathcal {PG}})}$ defined by

${\displaystyle f_{*}p\,(B)=p(f^{-1}(B))}$

for all ${\displaystyle p\in PX}$ and all measurable sets ${\displaystyle B\in {\mathcal {G}}}$. ^[6]

The Dirac delta map

Given a measurable space ${\displaystyle (X,{\mathcal {F}})}$, the map ${\displaystyle \delta$ :(X,{\mathcal {F}})\to (PX,{\mathcal {PF}})} maps an element ${\displaystyle x\in X}$ to the Dirac measure ${\displaystyle \delta _{x}\in PX}$, defined on measurable subsets ${\displaystyle A\in {\mathcal {F}}}$ by ^[6]

${\displaystyle \delta _{x}(A)=1_{A}(x)={\begin{cases}1&{\text{if }}x\in A,\\0&{\text{if }}x\notin A.\end{cases}}}$

The expectation map

Let ${\displaystyle \mu \in PPX}$, i.e. a probability measure over the probability measures over ${\displaystyle (X,{\mathcal {F}})}$. We define the probability measure ${\displaystyle {\mathcal {E}}\mu \in PX}$ by

${\displaystyle {\mathcal {E}}\mu (A)=\int _{PX}p(A)\,\mu (dp)}$

for all measurable ${\displaystyle A\in {\mathcal {F}}}$. This gives a measurable, natural map ${\displaystyle {\mathcal {E}}:(PPX,{\mathcal {PPF}})\to (PX,{\mathcal {PF}})}$. ^[6]

Example: mixture distributions

A mixture distribution, or more generally a compound distribution, can be seen as an application of the map ${\displaystyle {\mathcal {E}}}$. Let's see this for the case of a finite mixture. Let ${\displaystyle p_{1},\dots ,p_{n}}$ be probability measures on ${\displaystyle (X,{\mathcal {F}})}$, and consider the probability measure ${\displaystyle q}$ given by the mixture

${\displaystyle q(A)=\sum _{i=1}^{n}w_{i}\,p_{i}(A)}$

for all measurable ${\displaystyle A\in {\mathcal {F}}}$, for some weights ${\displaystyle w_{i}\geq 0}$ satisfying ${\displaystyle w_{1}+\dots +w_{n}=1}$. We can view the mixture ${\displaystyle q}$ as the average ${\displaystyle q={\mathcal {E}}\mu }$, where the measure on measures ${\displaystyle \mu \in PPX}$, which in this case is discrete, is given by

${\displaystyle \mu =\sum _{i=1}^{n}w_{i}\,\delta _{p_{i}}.}$

More generally, the map ${\displaystyle {\mathcal {E}}:PPX\to PX}$ can be seen as the most general, non-parametric way to form arbitrary mixture or compound distributions.

The triple ${\displaystyle (P,\delta ,{\mathcal {E}})}$ is called the Giry monad. ^{[1] [2] [3] [4] [5]}

Relationship with Markov kernels

One of the properties of the sigma-algebra ${\displaystyle {\mathcal {PF}}}$ is that given measurable spaces ${\displaystyle (X,{\mathcal {F}})}$ and ${\displaystyle (Y,{\mathcal {G}})}$, we have a bijective correspondence between measurable functions ${\displaystyle (X,{\mathcal {F}})\to (PY,{\mathcal {PG}})}$ and Markov kernels ${\displaystyle (X,{\mathcal {F}})\to (Y,{\mathcal {G}})}$. This allows to view a Markov kernel, equivalently, as a measurably parametrized probability measure. ^[10]

In more detail, given a measurable function ${\displaystyle f:(X,{\mathcal {F}})\to (PY,{\mathcal {PG}})}$, one can obtain the Markov kernel ${\displaystyle f^{\flat }:(X,{\mathcal {F}})\to (Y,{\mathcal {G}})}$ as follows,

${\displaystyle f^{\flat }(B|x)=f(x)(B)}$

for every ${\displaystyle x\in X}$ and every measurable ${\displaystyle B\in {\mathcal {G}}}$ (note that ${\displaystyle f(x)\in PY}$ is a probability measure). Conversely, given a Markov kernel ${\displaystyle k:(X,{\mathcal {F}})\to (Y,{\mathcal {G}})}$, one can form the measurable function ${\displaystyle k^{\sharp }:(X,{\mathcal {F}})\to (PY,{\mathcal {PG}})}$ mapping ${\displaystyle x\in X}$ to the probability measure ${\displaystyle k^{\sharp }(x)\in PY}$ defined by

${\displaystyle k^{\sharp }(x)(B)=k(B|x)}$

for every measurable ${\displaystyle B\in {\mathcal {G}}}$. The two assignments are mutually inverse.

From the point of view of category theory, we can interpret this correspondence as an adjunction

${\displaystyle \mathrm {Hom} _{\mathrm {Meas} }(X,PY)\cong \mathrm {Hom} _{\mathrm {Stoch} }(X,Y)}$

between the category of measurable spaces and the category of Markov kernels. In particular, the category of Markov kernels can be seen as the Kleisli category of the Giry monad. ^{[3] [4] [5]}

Product distributions

Given measurable spaces ${\displaystyle (X,{\mathcal {F}})}$ and ${\displaystyle (Y,{\mathcal {G}})}$, one can form the measurable space ${\displaystyle (PX,{\mathcal {PX}})\times (PY,{\mathcal {PY}})=(X\times Y,{\mathcal {F}}\times {\mathcal {G}})}$ with the product sigma-algebra, which is the product in the category of measurable spaces. Given probability measures ${\displaystyle p\in PX}$ and ${\displaystyle q\in PY}$, one can form the product measure ${\displaystyle p\otimes q}$ on ${\displaystyle (X\times Y,{\mathcal {F}}\times {\mathcal {G}})}$. This gives a natural, measurable map

${\displaystyle (PX,{\mathcal {PF}})\times (PY,{\mathcal {PG}})\to {\big (}P(X\times Y),{\mathcal {P(F\times G)}}{\big )}}$

usually denoted by ${\displaystyle \nabla }$ or by ${\displaystyle \otimes }$. ^[4]

The map ${\displaystyle \nabla :PX\times PY\to P(X\times Y)}$ is in general not an isomorphism, since there are probability measures on ${\displaystyle X\times Y}$ which are not product distributions, for example in case of correlation. However, the maps ${\displaystyle \nabla :PX\times PY\to P(X\times Y)}$ and the isomorphism ${\displaystyle 1\cong P1}$ make the Giry monad a monoidal monad, and so in particular a commutative strong monad. ^[4]

Further properties

• If a measurable space ${\displaystyle (X,{\mathcal {F}})}$ is standard Borel, so is ${\displaystyle (PX,{\mathcal {PF}})}$. Therefore the Giry monad restricts to the full subcategory of standard Borel spaces. ^{[1] [4]}

• The algebras for the Giry monad include compact convex subsets of Euclidean spaces, as well as the extended positive real line ${\displaystyle [0,\infty ]}$, with the algebra structure map given by taking expected values. ^[11] For example, for ${\displaystyle [0,\infty ]}$, the structure map ${\displaystyle e:P[0,\infty ]\to [0,\infty ]}$ is given by

${\displaystyle p\longmapsto \int _{[0,\infty )}x\,p(dx)}$

whenever ${\displaystyle p}$ is supported on ${\displaystyle [0,\infty )}$ and has finite expected value, and ${\displaystyle e(p)=\infty }$ otherwise.

See also

• Mixture distribution
• Compound distribution
• de Finetti theorem
• Measurable space
• Markov kernel
• Monad (category theory)
• Monad (functional programming)
• Category of measurable spaces
• Category of Markov kernels
• Categorical probability

Citations

1. Giry (1982)
2. Avery (2016) , pp. 1231–1234
3. Jacobs (2018) , pp. 205–106
4. Fritz (2020) , pp. 19–23
5. Moss & Perrone (2022) , pp. 3–4
6. Giry (1982) , p. 69
7. Riehl (2016)
8. Perrone (2024)
9. Perrone (2024) , p. 238
10. Giry (1982) , p. 71
11. Doberkat (2006) , pp. 1772–1776

References

• Giry, Michèle (1982). "A categorical approach to probability theory". Categorical Aspects of Topology and Analysis. Lecture Notes in Mathematics. Vol. 915. Springer. pp. 68–85. doi:10.1007/BFb0092872. ISBN   978-3-540-11211-2.

• Doberkat, Ernst-Erich (2006). "Eilenberg-Moore algebras for stochastic relations". Information and Computation. 204 (12): 1756–1781. doi:10.1016/j.ic.2006.09.001.

• Avery, Tom (2016). "Codensity and the Giry monad". Journal of Pure and Applied Algebra. 220 (3): 1229–1251. arXiv: 1410.4432 . doi:10.1016/j.jpaa.2015.08.017. S2CID   119695729.

• Jacobs, Bart (2018). "From probability monads to commutative effectuses". Journal of Logical and Algebraic Methods in Programming. 94: 200–237. doi:10.1016/j.jlamp.2016.11.006.

• Fritz, Tobias (2020). "A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics". Advances in Mathematics. 370. arXiv: 1908.07021 . doi:10.1016/j.aim.2020.107239. S2CID   201103837.

• Moss, Sean; Perrone, Paolo (2022). "Probability monads with submonads of deterministic states". LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. arXiv: 2204.07003 . doi:10.1145/3531130.3533355.

• Riehl, Emily (2016). "Chapter 5. Monads and their Algebras". Category Theory in Context. Dover. ISBN   978-0486809038.

• Perrone, Paolo (2024). "Chapter 5. Monads and Comonads". Starting Category Theory. World Scientific. doi:10.1142/9789811286018_0005. ISBN   978-981-12-8600-1.

Further reading

• Monads of probability, measures, and valuations, in nLab.
• https://ncatlab.org/nlab/show/Giry+monad

External links

• What is a probability monad?, video tutorial.