Category of Markov kernels

In mathematics, the category of Markov kernels, often denoted Stoch, is the category whose objects are measurable spaces and whose morphisms are Markov kernels. ^[1]^[2]^[3]^[4] It is analogous to the category of sets and functions, but where the arrows can be interpreted as being stochastic.

Several variants of this category are used in the literature. For example, one can use subprobability kernels^[5] instead of probability kernels, or more general s-finite kernels.^[6] Also, one can take as morphisms equivalence classes of Markov kernels under almost sure equality,^[7] see below.

Definition

Recall that a Markov kernel between measurable spaces $(X,{\mathcal {F}})$ and $(Y,{\mathcal {G}})$ is an assignment $k:X\times {\mathcal {G}}\to \mathbb {R}$ which is measurable as a function on $X$ and which is a probability measure on ${\mathcal {G}}$ .^[4] We denote its values by $k(B|x)$ for $x\in X$ and $B\in {\mathcal {G}}$ , which suggests an interpretation as conditional probability.

The category Stoch has:^[4]

As objects, measurable spaces;
As morphisms, Markov kernels between them;
For each measurable space $(X,{\mathcal {F}})$ , the identity morphism is given by the kernel

\delta (A|x)=1_{A}(x)={\begin{cases}1&x\in A;\\0&x\notin A\end{cases}}

for all

x\in X

and

A\in {\mathcal {F}}

;

Given kernels $k:(X,{\mathcal {F}})\to (Y,{\mathcal {G}})$ and $h:(Y,{\mathcal {G}})\to (Z,{\mathcal {H}})$ , the composite morphism $h\circ k:(X,{\mathcal {F}})\to (Z,{\mathcal {H}})$ is given by

(h\circ k)(C|x)=\int _{Y}h(C|y)\,k(dy|x)

for all

x\in X

and

C\in {\mathcal {H}}

.

This composition formula is sometimes called the Chapman-Kolmogorov equation.^[4]

This composition is unital, and associative by the monotone convergence theorem, so that one indeed has a category.

Basic properties

Probability measures

The terminal object of Stoch is the one-point space $1$ .^[4] Morphisms in the form $1\to X$ can be equivalently seen as probability measures on $X$ , since they correspond to functions $1\to PX$ , i.e. elements of $PX$ .

Given kernels $p:1\to X$ and $k:X\to Y$ , the composite kernel $k\circ p:1\to Y$ gives the probability measure on $Y$ with values

(k\circ p)(B)=\int _{X}k(B|x)\,p(dx),

for every measurable subset $B$ of $Y$ .^[7]

Given probability spaces $(X,{\mathcal {F}},p)$ and $(Y,{\mathcal {G}},q)$ , a measure-preserving Markov kernel $(X,{\mathcal {F}},p)\to (Y,{\mathcal {G}},q)$ is a Markov kernel $k:(X,{\mathcal {F}})\to (Y,{\mathcal {G}})$ such that for every measurable subset $B\in {\mathcal {G}}$ ,^[7]

q(B)=\int _{X}k(B|x)\,p(dx).

Probability spaces and measure-preserving Markov kernels form a category, which can be seen as the slice category $(\mathrm {Hom} _{\mathrm {Stoch} }(1,-),\mathrm {Stoch} )$ .

Measurable functions

Every measurable function $f:(X,{\mathcal {F}})\to (Y,{\mathcal {G}})$ defines canonically a Markov kernel $\delta _{f}:(X,{\mathcal {F}})\to (Y,{\mathcal {G}})$ as follows,

\delta _{f}(B|x)=1_{B}(f(x))={\begin{cases}1&f(x)\in B;\\0&f(x)\notin B\end{cases}}

for every $x\in X$ and every $B\in {\mathcal {G}}$ . This construction preserves identities and compositions, and is therefore a functor from Meas to Stoch.

Isomorphisms

By functoriality, every isomorphism of measurable spaces (in the category Meas) induces an isomorphism in Stoch. However, in Stoch there are more isomorphisms, and in particular, measurable spaces can be isomorphic in Stoch even when the underlying sets are not in bijection.

Relationship with other categories

Stoch is the Kleisli category of the Giry monad.^[3]^[4] This in particular implies that there is an adjunction

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

between Stoch and the category of measurable spaces.

The left adjoint $L:\mathrm {Meas} \to \mathrm {Stoch}$ of the adjunction above is the identity on objects, and on morphisms it gives the canonical Markov kernel induced by a measurable function described above.

As mentioned above, one can construct a category of probability spaces and measure-preserving Markov kernels as the slice category $(\mathrm {Hom} _{\mathrm {Stoch} }(1,-),\mathrm {Stoch} )$ .

Similarly, the category of probability spaces can be seen as the comma category $(\mathrm {Hom} _{\mathrm {Stoch} }(1,-),L)$ .

Particular limits and colimits

Since the functor $L:\mathrm {Meas} \to \mathrm {Stoch}$ is left adjoint, it preserves colimits.^[8] Because of this, all colimits in the category of measurable spaces are also colimits in Stoch. For example,

The initial object is the empty set, with its trivial measurable structure;
The coproduct is given by the disjoint union of measurable spaces, with its canonical sigma-algebra.
The sequential colimit of a decreasing filtration is given by the intersection of sigma-algebras.

In general, the functor $L$ does not preserve limits. This in particular implies that the product of measurable spaces is not a product in Stoch in general. Since the Giry monad is monoidal, however, the product of measurable spaces still makes Stoch a monoidal category.^[4]

Almost sure version

Sometimes it is useful to consider Markov kernels only up to almost sure equality, for example when talking about disintegrations or about regular conditional probability.

Given probability spaces $(X,{\mathcal {F}},p)$ and $(Y,{\mathcal {G}},q)$ , we say that two measure-preserving kernels $k,h:(X,{\mathcal {F}},p)\to (Y,{\mathcal {G}},q)$ are almost surely equal if and only if for every measurable subset $B\in {\mathcal {G}}$ ,

k(B|x)=h(B|x)

for $p$ -almost all $x\in X$ .^[7] This defines an equivalence relation on the set of measure-preserving Markov kernels $k,h:(X,{\mathcal {F}},p)\to (Y,{\mathcal {G}},q)$ .

Probability spaces and equivalence classes of Markov kernels under the relation defined above form a category. When restricted to standard Borel probability spaces, the category is often denoted by Krn.^[7]

Citations

^ Lawvere (1962)
^ Chentsov (1965)
^ ^a ^b Giry (1982), p. 69
^ ^a ^b ^c ^d ^e ^f ^g Fritz (2020), pp. 19–21
^ Panangaden (1999), p. 4
^ Kallenberg (2017)
^ ^a ^b ^c ^d ^e Dahlqvist (2018), p. 3
^ Riehl (2016), p. 140

References

Lawvere, F. W. (1962). "The Category of Probabilistic Mappings" (PDF).
Chentsov, N. N. (1965). "The categories of mathematical statistics". Dokl. Akad. SSSR. 164.
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.
Panangaden, Prakash (1999). "The category of Markov kernels". Electronic Notes in Theoretical Computer Science. 22: 171–187. doi:10.1016/S1571-0661(05)80602-4.
Riehl, Emily (2016). Category Theory in Context. Dover. ISBN 9780486809038.
Kallenberg, Olav (2017). Random Measures, Theory and Applications. Probability Theory and Stochastic Modelling. Vol. 77. Springer. doi:10.1007/978-3-319-41598-7. ISBN 978-3-319-41596-3.
Dahlqvist, Fredrik; Danos, Vincent; Garnier, Ilias; Silva, Alexandra (2018). "Borel Kernels and their Approximation, Categorically". MFPS 2018: Proceedings of Mathematical Foundations of Programming Semantics. arXiv:1803.02651.
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.