Giry Monad

definition theorem example

The Giry monad $\mathcal{G}$ on the category $\mathbf{Meas}$ of measurable spaces sends $X$ to the space $\mathcal{G}X$ of probability measures on $X$, with the $\sigma$-algebra generated by the evaluation maps $\mu \mapsto \mu (A)$. Its unit and multiplication are

$${\eta }_X(x)={\delta }_x(\text{Dirac}),{\mu }_X(\Pi )(A)={\int }_{\mathcal{G}X}\nu (A)\Pi (d\nu )(\text{averaging a random measure}),$$

and the Kleisli composite of $f:X\to \mathcal{G}Y$ and $g:Y\to \mathcal{G}Z$ is the Chapman–Kolmogorov integral $(g\bullet f)(C\mid x)={\int }_{Y}g(C\mid y)f(dy\mid x)$. The Kleisli Category $\mathrm{Kl}(\mathcal{G})$ is $\mathbf{Stoch}$, the category of measurable spaces and Markov kernels — the prototypical Markov Category.

Sources: Giry, A categorical approach to probability theory, LNM 915 (1982); Lawvere (1962), The category of probabilistic mappings; Fritz arXiv:1908.07021 (notes) §4 (Lemma 4.1: $\mathcal{G}$ is an affine symmetric monoidal monad; hence $\mathbf{Stoch}=\mathrm{Kl}(\mathcal{G})$ is Markov by Corollary 3.2); Cho & Jacobs arXiv:1709.00322 (notes) Example 2.5.

Why a monad, and why an affine commutative one

• Monad: a random variable whose law is itself random can be flattened by averaging; this is $\mu$. Kleisli arrows $X\to \mathcal{G}Y$ are exactly “stochastic functions”.
• Commutative / symmetric monoidal: the product measure $\mathcal{G}X\times \mathcal{G}Y\to \mathcal{G}(X\times Y)$ makes $\mathrm{Kl}(\mathcal{G})$ symmetric monoidal (Fubini is what makes the two ways of forming it agree). This is what lets independent kernels run in parallel.
• Affine: $\mathcal{G}1\cong 1$ — there is exactly one probability measure on a point. This is naturality of deletion, i.e. normalisation. Dropping normalisation (s-finite or sub-probability kernels) keeps a monad but loses affineness, and the Kleisli category becomes a Copy-Discard Category rather than a Markov category.

Relatives

monad	on	Kleisli category	Markov?
Giry $\mathcal{G}$	$\mathbf{Meas}$	$\mathbf{Stoch}$	yes
finitely supported $\mathcal{D}$ (Distribution Monad)	$\mathbf{Set}$	discrete Markov kernels	yes
Radon monad	compact Hausdorff spaces	continuous kernels	yes (Fritz §5)
sub-probability / s-finite measures	$\mathbf{Meas}$	$\mathbf{sfKrn}$	no — only copy-discard
non-empty power set	$\mathbf{Set}$	possibilistic kernels	yes (Fritz Ex. 2.6)
probability monad of Gaussians	—	$\mathbf{Gauss}$	yes; faithful into $\mathbf{Stoch}$ (Fritz Proposition 6.1)

Probabilistic programming languages denote programs as Kleisli morphisms of such monads; sample, observe and return are Kleisli composition, conditioning and $\eta$.

JuliaLeanHaskell

Docs: Theories (Catlab): copy/delete — ThMonoidalCategoryWithDiagonals

# The finite Giry/distribution monad with Dicts: η = Dirac, μ = averaging, Kleisli = Chapman–Kolmogorov.
η(x) = Dict(x => 1.0)
function μ(Π)                               # Π : distribution over distributions, as (ν => w) pairs
    out = Dict{Any,Float64}()
    for (ν, w) in Π, (x, p) in ν
        out[x] = get(out, x, 0.0) + w * p
    end
    out
end
bind(ν, f) = μ([f(x) => p for (x, p) in ν])            # Kleisli extension
weather = Dict(:rain => 0.3, :dry => 0.7)
grass(w) = w == :rain ? Dict(:wet => 0.9, :dry => 0.1) : Dict(:wet => 0.2, :dry => 0.8)
wet = bind(weather, grass)
round(wet[:wet]; digits = 2)                             # 0.3·0.9 + 0.7·0.2 = 0.41
bind(weather, η) == weather                              # right unit law: true
sum(values(wet)) ≈ 1                                     # affine: normalisation is preserved

import Mathlib
open MeasureTheory
-- Mathlib's Giry monad lives on `Measure`; probability measures are the affine part.
#check @Measure.dirac              -- η
#check @Measure.bind               -- Kleisli extension μ ∘ G f
#check @Measure.join               -- μ : Measure (Measure α) → Measure α
#check @Measure.bind_dirac         -- a unit law
#check ProbabilityMeasure

-- The finitely supported probability monad, i.e. the discrete Giry monad
newtype Dist a = Dist { runDist :: [(a, Double)] }
instance Functor Dist where fmap f (Dist xs) = Dist [ (f x, p) | (x, p) <- xs ]
instance Applicative Dist where
  pure x = Dist [(x, 1)]                                       -- η: the Dirac distribution
  Dist fs <*> Dist xs = Dist [ (f x, p * q) | (f, p) <- fs, (x, q) <- xs ]
instance Monad Dist where
  Dist xs >>= k = Dist [ (y, p * q) | (x, p) <- xs, (y, q) <- runDist (k x) ]   -- μ: averaging
 
data W = Rain | Dry deriving (Eq, Show)
data G = Wet | Parched deriving (Eq, Show)
weather :: Dist W
weather = Dist [(Rain, 0.3), (Dry, 0.7)]
grass :: W -> Dist G
grass Rain = Dist [(Wet, 0.9), (Parched, 0.1)]
grass Dry  = Dist [(Wet, 0.2), (Parched, 0.8)]
pWet :: Double
pWet = sum [ p | (Wet, p) <- runDist (weather >>= grass) ]     -- 0.41