Category of Markov kernels

Last updated July 27, 2024

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.

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]

Citations

Related Research Articles

In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects are associated to topological spaces, and maps between these algebraic objects are associated to continuous maps between spaces. Nowadays, functors are used throughout modern mathematics to relate various categories. Thus, functors are important in all areas within mathematics to which category theory is applied.

In mathematics, especially in category theory and homotopy theory, a groupoid generalises the notion of group in several equivalent ways. A groupoid can be seen as a:

In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently from the method chosen for constructing them. For example, the definitions of the integers from the natural numbers, of the rational numbers from the integers, of the real numbers from the rational numbers, and of polynomial rings from the field of their coefficients can all be done in terms of universal properties. In particular, the concept of universal property allows a simple proof that all constructions of real numbers are equivalent: it suffices to prove that they satisfy the same universal property.

In mathematics, the Yoneda lemma is a fundamental result in category theory. It is an abstract result on functors of the type morphisms into a fixed object. It is a vast generalisation of Cayley's theorem from group theory. It allows the embedding of any locally small category into a category of functors defined on that category. It also clarifies how the embedded category, of representable functors and their natural transformations, relates to the other objects in the larger functor category. It is an important tool that underlies several modern developments in algebraic geometry and representation theory. It is named after Nobuo Yoneda.

In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions such as products, pullbacks and inverse limits. The dual notion of a colimit generalizes constructions such as disjoint unions, direct sums, coproducts, pushouts and direct limits.

In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are known as adjoint functors, one being the left adjoint and the other the right adjoint. Pairs of adjoint functors are ubiquitous in mathematics and often arise from constructions of "optimal solutions" to certain problems, such as the construction of a free group on a set in algebra, or the construction of the Stone–Čech compactification of a topological space in topology.

In mathematics, specifically in category theory, a pre-abelian category is an additive category that has all kernels and cokernels.

In mathematics, a direct limit is a way to construct a object from many objects that are put together in a specific way. These objects may be groups, rings, vector spaces or in general objects from any category. The way they are put together is specified by a system of homomorphisms between those smaller objects. The direct limit of the objects $, where ranges over some directed set, is denoted by . This notation suppresses the system of homomorphisms; however, the limit depends on the system of homomorphisms.$

In mathematics, an algebraic stack is a vast generalization of algebraic spaces, or schemes, which are foundational for studying moduli theory. Many moduli spaces are constructed using techniques specific to algebraic stacks, such as Artin's representability theorem, which is used to construct the moduli space of pointed algebraic curves $and the moduli stack of elliptic curves. Originally, they were introduced by Alexander Grothendieck to keep track of automorphisms on moduli spaces, a technique which allows for treating these moduli spaces as if their underlying schemes or algebraic spaces are smooth. After Grothendieck developed the general theory of descent, and Giraud the general theory of stacks, the notion of algebraic stacks was defined by Michael Artin.$

In mathematics, a quotient category is a category obtained from another category by identifying sets of morphisms. Formally, it is a quotient object in the category of categories, analogous to a quotient group or quotient space, but in the categorical setting.

In category theory, a branch of mathematics, a presheaf on a category $is a functor . If is the poset of open sets in a topological space, interpreted as a category, then one recovers the usual notion of presheaf on a topological space.$

In mathematics, specifically in algebraic topology and algebraic geometry, an inverse image functor is a contravariant construction of sheaves; here “contravariant” in the sense given a map $, the inverse image functor is a functor from the category of sheaves on Y to the category of sheaves on X . The direct image functor is the primary operation on sheaves, with the simplest definition. The inverse image exhibits some relatively subtle features.$

In mathematics, Verdier duality is a cohomological duality in algebraic topology that generalizes Poincaré duality for manifolds. Verdier duality was introduced in 1965 by Jean-Louis Verdier as an analog for locally compact topological spaces of Alexander Grothendieck's theory of Poincaré duality in étale cohomology for schemes in algebraic geometry. It is thus one instance of Grothendieck's six operations formalism.

In probability theory, a Markov kernel is a map that in the general theory of Markov processes plays the role that the transition matrix does in the theory of Markov processes with a finite state space.

A differentiable stack is the analogue in differential geometry of an algebraic stack in algebraic geometry. It can be described either as a stack over differentiable manifolds which admits an atlas, or as a Lie groupoid up to Morita equivalence.

In mathematics, the quotient of an abelian category $by a Serre subcategory is the abelian category which, intuitively, is obtained from by ignoring all objects from . There is a canonical exact functor whose kernel is, and is in a certain sense the most general abelian category with this property.$

In mathematics, compact objects, also referred to as finitely presented objects, or objects of finite presentation, are objects in a category satisfying a certain finiteness condition.

In probability theory and ergodic theory, a Markov operator is an operator on a certain function space that conserves the mass. If the underlying measurable space is topologically sufficiently rich enough, then the Markov operator admits a kernel representation. Markov operators can be linear or non-linear. Closely related to Markov operators is the Markov semigroup.

In mathematics, the category of measurable spaces, often denoted Meas, is the category whose objects are measurable spaces and whose morphisms are measurable maps. This is a category because the composition of two measurable maps is again measurable, and the identity function is measurable.

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. It is one of the main examples of a probability monad.

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.