Markov Category

A Markov category is a symmetric monoidal category in which every object carries a commutative comonoid compatibly with . This comonoid consists of a copy and a discard , where is the unique map to the monoidal unit . A morphism is a channel, or Markov kernel, and a state is a morphism . Composition read in diagram order models ” then ”, and every channel is causal, .

The prototype is , whose objects are measurable spaces, morphisms are Markov kernels , states are probability measures, and is the product. Its comonoid structure, beyond that of a plain category, supplies duplication and deletion of information. Over a semifield other than the same axioms yield possibilistic and tropical variants, whereas making conditioning total and exact gives exact-conditioning.

Remark. String diagrams

Morphisms compose as string diagrams read top-to-bottom: a channel is a box , a wire is an object, is a branching node, a terminating node, and the symmetry a wire crossing. A type mismatch is a diagram that will not draw.

Proposition. Deterministic morphisms

A channel is deterministic iff it is a comonoid homomorphism, meaning and . The deterministic morphisms form a subcategory; in they are the measurable functions.

Semifield-parametric variants

The whole apparatus, from composition through marginalization to disintegration, is parametric in an underlying semifield, so ordinary probability and tropical optimization are two instances of one diagrammatic theory (Cakiqi and Little). Every structural operation is a sum-of-products over the semifield, whether composing channels, marginalizing a wire, or disintegrating a joint state, so a semifield homomorphism transports weights along the same string diagrams and induces a functor between the Markov categories built over and over . Changing the semifield alters only the arithmetic, not the diagram.

Sending the probability semifield to the min-plus (tropical) semifield replaces marginal sums by minima and products by sums, and the differentiable softmin-plus relaxation interpolates between the two regimes for gradient-based inference.

Example. Tropical disintegration

Under the min-plus semifield the disintegration of a joint cost state recovers a Viterbi/shortest-path decomposition, with the marginal giving the minimal cost and the kernel giving the argmin continuation. The same diagram read over yields the ordinary marginal and posterior.

Property. Causal adjustment transports functorially

Back-door and front-door adjustment are expressed by a point-state cut functor that severs an incoming wire and reconnects a fixed interventional state. Because the functor is defined diagrammatically, it commutes with the semifield change, so an identification proof written for probability holds verbatim over min-plus.

References

• Tobias Fritz, “A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics”, Advances in Mathematics 370 (2020), arXiv:1908.07021
• Kenta Cho and Bart Jacobs, “Disintegration and Bayesian inversion via string diagrams”, Mathematical Structures in Computer Science 29 (2019), arXiv:1709.00322