nLab Stoch

Idea

The category whose objects are measurable spaces and whose morphisms are stochastic kernels (or Markov kernels) is often denotes Stoch, or similar.

It is the motivating example of a Markov category, and together with its subcategory BorelStoch, one of the most important categories of categorical probability.

Definition

Stoch is the category whose

• Objects are measurable spaces, i.e. pairs $(X,\mathcal{A})$ where $X$ is a set and $\mathcal{A}$ is a sigma-algebra on $X$;
• Morphisms$(X,\mathcal{A})\to(Y,\mathcal{B})$ are Markov kernels of entries $k(B|x)$, for $x\in X$ and $B\in\mathcal{B}$;
• The identities $(X,\mathcal{A})\to(X,\mathcal{A})$ are given by the Dirac delta kernels
  $$\delta(A|x) = 1_A(x) = \begin{cases} 1 & x\in A ; \\ 0 & x\notin A ; \end{cases}$$
• The composition of kernels $k:(X,\mathcal{A})\to(Y,\mathcal{B})$ and $h:(Y,\mathcal{B})\to(Z,\mathcal{C})$ is given by the Lebesgue integral
  $$(h\circ k) (C|x) = \int_Y h(C|y)\,k(dy|x)$$

  for all $x\in X$ and $C\in\mathcal{C}$. This is sometimes called Chapman-Kolmogorov formula. (Compare with the composition formula for stochastic matrices.)

Properties

As a Kleisli category

Stoch can be equivalently described as the Kleisli category of the Giry monad on Meas.

It can also be described as the Kleisli category of the Giry monad restricted to the category $SoberMeas$ of sober measurable spaces. Indeed,

• For every measurable space $X$, the space $P X$ is always sober, and so the Giry monad restricts to SoberMeas;

• By this proposition, every measurable space is isomorphic to its sobrification in the category of zero-one kernels (and hence, in Stoch as well).

In other words, this triangle commutes up to natural isomorphism, where $S$ denotes the sobrification, and $L_P$ denotes the left adjoint of the Kleisli adjunction given by the Giry monad on Meas, as well as its restriction to sober measurable spaces.

As a Markov category

As a Markov category, Stoch is causal and hence positive. It does not have all conditionals, but its subcategory BorelStoch does.

Its deterministic morphisms are exactly the zero-one kernels, forming the subcategory $Stoch_det$. Note that, outside of the sober case, these are more general than measurable functions.

Representability

Stoch is a representable Markov category:

• First of all, as we saw above, the Giry monad restricts to SoberMeas.

• Also, $Stoch_det$ is equivalent to $SoberMeas$.

Consider now the following diagram, where

• $P$ denotes the Giry monad on $SoberMeas$;
• $L_P$ and $R_P$ are the left and right adjoints of the Kleisli adjunction, making the triangle on the right commute;
• The equivalence $Stoch_det\to SoberMeas$, on objects, maps a measurable space $X$ to its sobrification $S X$. Since $X$ is naturally isomorphic to $S X$ in $Stoch$ (see above), the upper triangle commutes up to natural isomorphism;
• The equivalence $SoberMeas\to Stoch_det$ is the identity on objects, and on morphisms it canonically induces a kernel from a function;
• The functor $R':Stoch\to Stoch_det$ is exactly the one making the lower triangle commute. Explicitly it maps an object $X$ to the space $P X$, and a kernel $X\to Y$ to the kernel induced by the Kleisli extension $P X \to P Y$.

By the considerations above, $R'$ is right adjoint to the inclusion functor $Stoch_det\hookrightarrow Stoch$, making $Stoch$ a representable Markov category.

Explicitly, the sampling map $samp:P X\to X$ is the usual measure-theoretic one:

$$samp(A|p) \;=\; p(A) .$$

The resulting monad on $SubStoch$, chasing the diagram above, can be seen as induced the Giry monad on $SoberMeas$ through the equivalence $SoberMeas \simeq Stoch_det$.

One should always keep in mind that the probability monad making Stoch representable is on $Stoch_det$, or equivalently on SoberMeas, but not on Meas, even though $Stoch$ is also the Kleisli category of the Giry monad on Meas. (The reason is that measurable functions are not the deterministic morphisms of $Stoch$, zero-one kernels are.)

Particular limits and colimits

• The invariant sigma-algebra for every action via zero-one kernels (for example, via deterministic functions) is a colimit.

• For every action for which the ergodic decomposition theorem applies, the space of ergodic measures is a limit.

• A notable special case of the condition above is de Finetti's theorem, which says that the space of probability measures $P X$ (Giry monad) is a limit for the action of finite permutations.

• Being a Kleisli category, and since left adjoints preserve colimits, every colimit of measurable spaces is also a colimit in Stoch.

Notable subcategories

BorelStoch

BorelStoch is the full subcategory of Stoch whose objects are standard Borel measurable spaces. This is particularly important as a Markov category because it has conditionals and countable Kolmogorov products. It is the Kleisli category of the Giry monad restricted to standard Borel spaces.

As proven here, in BorelStoch all idempotents split, making it a Cauchy-complete category.

FinStoch

FinStoch is the full subcategory of Stoch whose objects are discrete finite sets. Equivalently, it is the category of finite stochastic matrices.

It is closely related to the Kleisli category of the distribution monad.

Related concepts

• Markov category
• Markov kernel
• category of couplings
• probability monad
• Giry monad
• Kleisli category
• categorical probability

References

• Bill Lawvere, The category of probabilistic mappings, ms. 12 pages, 1962

  (Lawvere Probability 1962)

• N. N. Chentsov, The categories of mathematical statistics, Dokl. Akad. SSSR 164, 1965.

• Prakash Panangaden, The category of Markov kernels, ENTCS, 1999. (full text)

• Kenta Cho, Bart Jacobs, Disintegration and Bayesian Inversion via String Diagrams, Mathematical Structures of Computer Science 29, 2019. (arXiv:1709.00322)

• Tobias Fritz, A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics, Advances of Mathematics 370, 2020. (arXiv:1908.07021)

• Tobias Fritz, Tomáš Gonda, Antonio Lorenzin, Paolo Perrone, Dario Stein, Absolute continuity, supports and idempotent splitting in categorical probability, (arXiv:2308.00651)

category: category, probability