A Markov kernel (also called transition kernel, stochastic kernel, or probability kernel) is a mathematical formalization of a “function with random outcomes”, or “random transition”. (Sometimes the term transition kernel denotes a more general, non-normalized mapping.)
It can be thought of as a generalization of a stochastic map outside the finite discrete case. (Sometimes the term “stochastic map” is itself used to denote a Markov kernel.)
Markov kernels, in the form of regular conditional distributions (see below) are also the standard setting for talking about conditional probability outside of the discrete case (and without incurring in paradoxes).
Markov kernels and their categories are among the basic building blocks of categorical probability.
Let and be measurable spaces, i.e. sets equipped each with a sigma-algebra. A Markov kernel is an assignment which is
The quantity can be thought of as the probability of transitioning to if we are in , or of the conditional probability of the event given .
A Markov kernel can be equivalently expressed as a measurable map where denotes the Giry monad on Meas, with the Giry sigma-algebra. In other words, a Markov kernel is exactly a Kleisli morphism for the Giry monad. Particular Markov kernels are also Kleisli morphisms for other probability monads.
Consider two and a measure on . The kernels and are said to be -almost surely equal or -almost everywhere equal if for every , the quantities and only differ on a set of measure zero. Note that in general this set depends on the choice of , but in some cases, such as when is standard Borel, it can be taken independently of .
Let and be probability spaces, i.e. measurable spaces equipped each with a probability measure. A measure-preserving kernel is a kernel between the underlying measurable spaces such that for every ,
The identity function on a measurable set defines a kernel as follows,
for every and . This gives the identity morphisms in the categories of kernels below.
More generally, let be a measurable function. We can define the kernel as follows,
for every and . Intuitively, this kernel represents the deterministic transition, from to with probability one. This construction induces a functor from the category Meas to the categories of kernels below. (Compare with the analogous construction for stochastic maps.)
Every kernel in the form is a zero-one kernel, but the converse is not true in general.
Note that if is a measure-preserving function, then is a measure-preserving kernel in the sense defined above.
Given a measure-preserving Markov kernel , a Bayesian inverse of is a Markov kernel such that for all and ,
The last formula can be seen as an instance of Bayes' formula, as it generalize the usual discrete formula
We have that
Every kernel between standard Borel spaces admits a Bayesian inverse;
If a kernel admits a Bayesian inverse , then any kernel is a Bayesian inverse of if and only if it is -almost surely equal to .
Bayesian inverses, when they exist, depend crucially on the measure .
Bayesian inversion makes the category Krn (see below) a dagger category.
A Markov kernel can be seen as a probability measure which depends measurably on a parameter. Therefore, together with the idea of conditional expectation, it’s a very useful tool to talk about conditional probability without incurring into paradoxes. Let’s see how.
Let be a probability space, and consider a sub-sigma-algebra . Recall that
the conditional expectation of an integrable function given is a function which is -measurable (“coarser” than ), and such that for every ,
(Such a function always exists by the Radon-Nikodym theorem.)
the conditional probability of an event (measurable subset) is the conditional expectation of its indicator function:
Note that is a function,
which is -measurable for every . Therefore, in order for the assignment to be a Markov kernel (see the definition above), we moreover need that for every the assignment
be a probability measure on . This is not always the case. When this happens, we call the resulting kernel a regular conditional distribution given . We can view a regular conditional distribution as a probability measure on which is parametrized in a measurable way by .
The disintegration theorem says that when is standard Borel, regular conditional distributions in the form above always exist.
Using the disintegration theorem we can obtain conditional probability distributions in a way that generalizes the discrete formula
to the non-discrete setting.
Given standard Borel spaces and , their product is again standard Borel. The projection map induces a sub-sigma-algebra on (which makes it isomorphic to in both Stoch and Krn, see Section 2.1 of this paper).
Given a joint distribution on , we can then form the regular conditional (or equivalently, up to isomorphism, ). Further composing with the projection (or equivalently restricting the kernel to the sub-sigma-algebra ) we then get a kernel sometimes denoted simply or .
This kernel satisfies the property that for every and ,
and is therefore a generalization of conditional probability to the non-discrete setting: compare it to the formula
Stoch is the category of measurable spaces and Markov kernels between them.
One can also form the category of probability spaces and equivalence classes of Markov kernels between them (under almost sure equality).
One can restrict the category above to standard Borel probability spaces, obtaining a dagger category sometimes denoted by Krn, which is equivalent to the category of couplings.
See also:
Discussion via category theory:
F. W. Lawvere, The Category of Probabilistic Mappings, 1962, PDF.
Fredrik Dahlqvist, Vincent Danos, Ilias Garnier, and Alexandra Silva, Borel kernels and their approximation, categorically. In MFPS 34: Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics, volume 341, 91–119, 2018. arXiv.
Tobias Fritz, A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics. Adv. Math., 370:107239, 2020. arXiv:1908.07021.
Noé Ensarguet, Paolo Perrone, Categorical probability spaces, ergodic decompositions, and transitions to equilibrium. arXiv.
Last revised on July 12, 2024 at 15:46:14. See the history of this page for a list of all contributions to it.