A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics

Tobias Fritz

Source-linked AI summary

A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics

Tobias Fritz

arXiv:1908.07021v8Aug 19, 2019math.STcs.LOmath.CTmath.PR

TL;DR

The paper develops Markov categories as a purely abstract framework for synthetic probability and statistics, replacing reliance on low-level measure-theoretic machinery with algebraic axioms for systems of Markov kernels. It treats conditioning, conditional independence, conditional products, almost-sure reasoning, sufficient statistics, and related theorems uniformly across several kinds of probability theory, including discrete, measure-theoretic, Gaussian, and stochastic-process settings.

Problem
Probability theory and statistics traditionally rely on measure theory directly, motivating a higher-level algebraic framework for systems of Markov kernels.
Method
The paper formulates conditioning, disintegration, conditional independence, conditional products, almost surely, and sufficient statistics in the abstract language of Markov categories.
Results
The framework provides a uniform treatment of discrete, general measurable, Gaussian, and corresponding stochastic-process probability theories, and yields abstract versions of the Fisher–Neyman, Basu, and Bahadur sufficient-statistics theorems.
Takeaways & Limitations
The categorical setup offers conceptual clarity while avoiding frequent appeal to low-level measure-theoretic machinery.
Takeaways & Limitations
Randomness pushback is not used in this paper, and whether an axiom capturing all discussed aspects of causality exists remains an open question.

Abstract

from arXiv · show

We develop Markov categories as a framework for synthetic probability and statistics, following work of Golubtsov as well as Cho and Jacobs. This means that we treat the following concepts in purely abstract categorical terms: conditioning and disintegration; various versions of conditional independence and its standard properties; conditional products; almost surely; sufficient statistics; versions of theorems on sufficient statistics due to Fisher--Neyman, Basu, and Bahadur. Besides the conceptual clarity offered by our categorical setup, its main advantage is that it provides a uniform treatment of various types of probability theory, including discrete probability theory, measure-theoretic probability with general measurable spaces, Gaussian probability, stochastic processes of either of these kinds, and many others.

1. Introduction

The paper replaces low-level measure-theoretic foundations with a higher-level categorical framework for Markov kernels, aiming for conceptual clarity, generality, and modularity across probability theories. It develops abstract treatments of conditional independence, almost-sure equality, and sufficient-statistics theorems, while acknowledging that the formalism remains subject to refinement.

Motivation: Markov categories provide algebraic axioms that avoid directly using low-level measure-theoretic machinery.The paper compares this shift with moving from machine-code programming to a higher-level programming language.
Generality: The framework applies across finite, Gaussian, measurable-space, and stochastic-process probability theories, as well as some non-probabilistic examples.Results can therefore specialize automatically to different categories satisfying the axioms.
Generality: Modularity allows many results to require only fragments of the full axiom system.Such results can be instantiated in Markov categories where only the relevant fragment holds.
Scope: The authors present the formalism as conceptually useful but preliminary, with definitions and technical details expected to undergo further refinement.They nevertheless regard results based on the preliminary definitions as definite.
Results: The paper develops categorical versions of conditional independence, conditional products, almost-sure equality, and sufficient-statistics results.Its sufficient-statistics results include abstract relatives of Fisher–Neyman, Basu, and Bahadur theorems.
Results: The abstract results recover familiar statistical theorems: FinStoch induces Fisher–Neyman factorization, while complete sufficient statistics are independent of ancillary statistics.If a minimal sufficient statistic exists, a complete sufficient statistic is minimal sufficient.

2. Markov categories

Markov categories axiomatize systems of Markov kernels using symmetric monoidal structure together with copying and discarding, supporting abstract probability and statistics. Their structure interprets distributions, random variables, joint distributions, and marginalization while admitting examples such as finite stochastic matrices.

Definition and interpretation: Markov categories are symmetric monoidal categories with copy and discard structure that makes morphisms behave like Markov kernels.The axioms include sequential composition, tensor products, and distinguished morphisms for copying and discarding values.
Distributions and random variables: A distribution is a morphism ψ : I →X, while a random variable is represented by a morphism f : X →Y whose distribution is fψ : I →Y.In Stoch, distributions specialize to probability measures on measurable spaces.
Joint distributions: Morphisms ψ : I →X ⊗Y represent joint distributions, which can be marginalized by composing with idX ⊗delY.The same interpretation extends to joint distributions on more than two factors.
Examples: The framework is intended to support abstract probability theory across concrete settings, including finite stochastic matrices and general Markov kernels between measurable spaces.In FinStoch, morphisms are stochastic matrices and composition is matrix multiplication.

3. Example: Kleisli categories of monoidal monads

The paper constructs Markov categories from symmetric monoidal affine monads via Kleisli categories. This yields a canonical route to examples including measurable Markov kernels, while related statistical-operation constructions remain limited by unresolved tensor-product problems.

General construction: The Kleisli category inherits its tensor product on objects from D, and the inclusion D →Kl(T) is strict symmetric monoidal.This supports transport of comonoid structures from D to Kl(T).
General construction: For a symmetric monoidal affine monad T on a Markov category D, the Kleisli category Kl(T) is again a Markov category canonically.The construction transports the monoidal and comonoid structures while preserving terminality of the unit under the affine condition.
Other examples: The finite nonempty powerset monad yields a Kleisli category identified with finite sets and multivalued functions.Its monoidal structure maps subsets to Cartesian products.
Measurable examples: Applying the construction to the Giry monad produces the category Stoch of measurable Markov kernels and its standard-Borel subcategory BorelStoch.The Giry monad assigns probability measures to measurable spaces and acts by pushforward on measurable maps.
Limitations: Tensor products of morphisms remain unresolved in the discussed statistical-operation categories, preventing instantiation of later results there.The difficulty arises because proposed definitions on rectangles may not extend meaningfully to product σ-algebras or all bounded measurable functions.

5. Example: compact Hausdorff spaces and continuous Markov kernels

The Radon monad on compact Hausdorff spaces provides a topological example of the Kleisli construction for Markov categories. Product measures are defined through integration and the Riesz representation theorem, yielding continuous Markov kernels.

Radon monad: The Radon monad on compact Hausdorff spaces assigns Radon probability measures with a topology determined by continuity of integration maps.Its Kleisli category is opposite equivalent to unital commutative C*-algebras with positive unital linear maps.
Kleisli construction: A Kleisli morphism X →Y is represented by a continuous map X →RY, with composition given by the Chapman–Kolmogorov equation.To apply the general construction, the Radon monad must be equipped with symmetric monoidal structure.
Product measures: Product measures are obtained from RX × RY →R(X ×Y) by using the Riesz representation theorem because the Borel σ-algebra on X ⊗Y can exceed the product Borel σ-algebras.The product operation maps a pair of Radon measures to a Radon measure on the product space.
Result: The resulting maps equip R with a symmetric monoidal monad structure, so Kl(R) is a Markov category.The copy maps are represented by x ↦δ(x,x).

6. Example: Gaussian probability theory

The paper develops a Markov category for Gaussian probability theory and relates it faithfully to measurable Markov kernels. It also shows how functor categories apply the framework to stochastic processes and time-indexed statistics.

Gaussian category: Gaussian morphisms n →m are tuples (M, C, s) encoding conditional Gaussian distributions with linear transformation, positive semidefinite covariance, and mean parameters.The model takes Y ∈Rm to be determined by X ∈Rn plus independent Gaussian noise.
Gaussian category: Composition of Gaussian morphisms is (N, D, t) ◦(M, C, s) := (NM, NCN T + D, Ns + t).The covariance term follows from independent noise in the two composed kernels.
Gaussian category: The tensor product acts on two Gaussian morphisms by direct sums: (M, C, s) ⊗(N, D, t) := (M ⊕N, C ⊕D, s ⊕t).This represents acting on independent random variables simultaneously.
Relation to Stoch: There is a faithful Markov functor Gauss →Stoch sending n to Rn with its Borel σ-algebra.The functor interprets each Gaussian morphism as a measurable Markov kernel.
Stochastic processes: Functor categories built from deterministic diagrams form Markov categories and allow the definitions and results to be applied to stochastic processes and time-indexed statistics.Process components encode compatible joint distributions over times up to n, while statistics are sequences of deterministic maps Xn →Tn.

8. Example: hypergraph categories

The paper constructs Markov categories from hypergraph categories by restricting to counit-preserving morphisms, yielding broad examples and potential counterexamples.

Construction: Restricting a hypergraph category to counit-preserving morphisms produces a Markov category.The construction applies to a symmetric monoidal category of commutative comonoids as well.
Examples: FinRel restricts to FinSetMulti, recovering finite sets and multirelations as a concrete example.FinRel uses relations that copy inputs and test equality through its hypergraph structure.
Examples: For a semiring R, restricting Mat(R) to counit-preserving morphisms gives stochastic matrices with entries in R.R = R+ yields a category equivalent to FinStoch, while two fuzzy-information categories arise from alternative semirings.
Scope: The finite-set examples restrict the object class compared with versions defined on arbitrary sets.This difference is explicitly noted for the fuzzy-information-transformer examples.
Significance: The construction recovers known structures while potentially producing further Markov categories with interesting theorem instantiations.The authors also note that such categories can provide counterexamples to plausible conjectures.

10. Deterministic morphisms and a strictification theorem

The paper characterizes deterministic morphisms categorically, relates them to familiar maps in probability categories, and proves that every Markov category has a strict equivalent.

Deterministic morphisms: Deterministic morphisms preserve comultiplication and form a symmetric monoidal, cartesian monoidal subcategory.Closure under composition and inclusion of the structure maps support the cartesian structure.
Examples: In FinStoch, deterministic morphisms are exactly 0–1 stochastic matrices, corresponding to the image of FinSet.Thus the categorical notion agrees with ordinary deterministic functions in the finite setting.
Examples: In Stoch, deterministic kernels are precisely those assigning {0,1}-valued measures, but these need not be delta measures.Consequently, deterministic morphisms do not generally coincide with measurable maps.
Examples: In BorelStoch, deterministic morphisms are isomorphic to standard Borel spaces and measurable maps.Standard Borel structure ensures {0,1}-valued measures are delta measures and Borel σ-algebras separate points.
Examples: In Gaussian probability, determinism is equivalent to zero covariance, meaning that no randomness is involved.The same notion also coincides with comonoid homomorphisms in the commutative-comonoid construction.
Strictification: Every Markov category is comonoid equivalent to a strict one, validating use of strict graphical language for arbitrary Markov categories.The strictification theorem is obtained using the cartesian monoidal deterministic subcategory.

11. Further candidate axioms for Markov categories

The paper examines additional axioms that could make abstract Markov categories more closely resemble categories of measurable Markov kernels.

Candidate axioms: Additional properties of measurable-space Markov-kernel categories are treated as candidate axioms for Markov categories.The paper presents these properties as potentially useful structural enrichments, while noting that the investigation is ongoing.

Conditionals and conditioning.

The paper axiomatizes conditioning in Markov categories, extending familiar conditional-distribution and chain-rule constructions beyond discrete probability. It characterizes how these conditionals relate to regular conditional probabilities and records where they exist or fail.

Conditionals and conditioning.: A conditional distribution is a Markov kernel satisfying the joint-distribution reconstruction equation after conditioning on an input.In FinStoch, positive input probabilities use the usual ratio formula, while zero-probability inputs permit any normalized conditional.
Conditionals and conditioning.: Conditional distributions generalize the discrete chain rule to arbitrary Markov categories, including measure-theoretic settings.Formal variables encode categorical wiring rather than points or densities in Stoch and BorelStoch.
Conditionals and conditioning.: BorelStoch has conditional distributions, whereas Stoch does not in general because product regular conditional probabilities need not exist.Existence holds when the conditioned space is standard Borel, and the categorical and traditional notions are equivalent.
Conditionals and conditioning.: Radon-based Markov categories may lack conditionals because requiring conditional kernels to vary continuously is generally too strong.The obstruction is that conditionals are rarely continuous.
Conditionals and conditioning.: The generalized notion allows conditionals depending measurably on parameters and yields a categorical form of Bayes’ theorem.FinStoch and BorelStoch satisfy the relevant conditional-existence requirements; Gauss also has conditionals.
Conditionals and conditioning.: Double conditioning can produce conditioning on a tensor product, and this construction iterates to multiple variables, but the converse is not established.Conditionals are unique only in the degenerate case where any two parallel morphisms are equal.

Randomness pushback.

Randomness pushback expresses stochastic maps as deterministic maps supplied with an additional random input. The paper establishes this property in finite and Gaussian settings, while leaving its general validity for Stoch open.

Randomness pushback.: Randomness pushback requires every morphism to factor through a deterministic map with an auxiliary object carrying a fixed random distribution.The deterministic map receives both the auxiliary random input and the original input.
Randomness pushback.: The property can represent stochastic dynamical systems as random choices of deterministic dynamics and can support Bayesian-network reformulations.The paper does not use randomness pushback in its own development, though it identifies possible applications elsewhere.
Randomness pushback.: FinStoch has randomness pushback by sampling a random function and then evaluating it at the original input.The auxiliary object is the finite function set Y^X; its function values can be chosen independently with the required marginals.
Randomness pushback.: Whether Stoch has randomness pushback remains unknown, partly because measurable spaces are not cartesian closed.This prevents a direct generalization of the finite-set construction.
Randomness pushback.: Gauss has randomness pushback because Gaussian affine-noise morphisms arise by adding an independently generated Gaussian input to a deterministic addition map.A morphism represented by Y = MX + ξ uses a Gaussian noise morphism with parameters (0, C, s).

Positivity.

Positivity is an axiom motivated by probability nonnegativity and used to derive structural properties of Markov categories. It holds in the principal probabilistic examples, fails when negative probabilities are allowed, and supports later factorization results.

Positivity.: Positivity formalizes a nonnegativity-based implication for composable morphisms whose composite is deterministic.The paper introduces it as a candidate axiom and connects it to conditional independence in a special case.
Positivity.: FinStoch and Gauss are positive, and Stoch is positive by an argument using nonnegative integrals and almost-sure vanishing.Positivity also transfers along Markov embeddings, yielding Gauss from the embedding Gauss → Stoch.
Positivity.: If a Markov category has conditionals, then it is positive.Thus positivity is available in every category satisfying the stronger conditional-existence property.
Positivity.: FinStoch± is not positive because allowing negative matrix entries breaks the relevant implication, and consequently it lacks conditionals.The direct obstruction is that the conditional reconstruction right-hand side vanishes when a marginal is zero, while the joint entry need not.
Positivity.: Positivity implies that isomorphisms are deterministic and that every comonoid structure equals the distinguished one.It also implies that if gf is deterministic and f is an epimorphism, then g is deterministic.
Positivity.: The paper conjectures a 2-monadic characterization of positive Markov categories and suggests possible relevance to hypergraph categories.The proposed characterization is not worked out in detail, and a comprehensive axiom covering positivity and causality remains unresolved.

12. Conditional independence and the semigraphoid properties

The paper generalizes conditional independence to Markov categories, including settings without conditionals, and develops its standard properties and conditional products. Several distinct notions are unified through the idea that conditioning wires disconnect string diagrams.

Conditional independence is generalized from probability distributions to arbitrary Markov categories, supporting graphical-model interpretations at this level of generality.
Without conditionals, conditional independence remains meaningful but splits into distinct notions for distributions, processes, and general morphisms.
The definitions apply without conditionals and recover standard finite-set conditional independence; in Stoch, they coincide directly with Dawid and Studený’s definition.
Semigraphoid properties: The framework proves versions of symmetry, right decomposition, contraction, and weak union, known as semigraphoid properties.
Conditional products: In Markov categories with conditionals, conditional products exist, are unique given their marginals and conditional independence, and satisfy associativity.
The various definitions are unified by removing conditioning wires and requiring the remaining string diagram to disconnect into conditionally independent parts.

Franz’s notion of independent morphisms.

Franz’s independence tracks the sample space of random variables, whereas the paper’s notion depends only on their joint distribution. The two notions otherwise coincide in suitable categories of probability spaces.

For deterministic morphisms, Franz-independence is equivalent to independence of the joint distribution obtained by pairing the two random variables.
The distinction is therefore representational rather than probabilistic when the relevant categories of probability spaces are used.
Franz’s definition explicitly retains the sample space, while the paper’s independence notion is a property only of the joint distribution.

Simpson’s axioms for conditional independence.

The paper notes that Simpson proposes axioms for categorical independence but does not define conditional independence itself, and that a detailed comparison remains undone.

The paper has not yet undertaken a detailed comparison with Simpson’s approach.

13. Almost surely

The paper axiomatizes almost sure equality for morphisms in Markov categories, generalizing prior work and using it to develop probability-space categories and related constructions. It establishes concrete specializations, uniqueness properties, and compatibility results under stated hypotheses.

Definition and scope: Almost sure equality is generalized from Cho and Jacobs and extended to almost surely deterministic morphisms.The paper proposes relativizing further probabilistic concepts with respect to this equality.
Concrete interpretations: In FinStoch, f =p-a.s. g exactly when f and g agree on inputs receiving positive probability under p.In Stoch, the analogous condition requires equality of the associated kernel probabilities almost surely for every parameter value.
Concrete interpretations: The proposed Stoch notion can differ from standard pointwise almost sure equality, even identifying a map with the identity when they disagree everywhere.The paper treats this as evidence for its working hypothesis that the categorical notion is appropriate.
Basic properties: Almost sure equality is preserved by postcomposition, paired tensor products, and suitable precomposition.These properties follow from the definition and the monoidal structure; causality also supports decomposition through intermediate outputs.
Conditionals: Conditionals are unique up to almost sure equality, with the equality taken relative to the marginal distribution of the conditioned variable.This generalizes the usual uniqueness of conditional distributions.
Probability-space categories: For causal Markov categories, probability spaces and measure-preserving Markov kernels form ProbStoch(C) after quotienting morphisms by almost sure equality.Composition is well-defined under causality, and when conditionals exist this category is isomorphic to a category of couplings.
Bayesian inversion: Bayesian inversion equips ProbStoch(C) with a symmetric monoidal dagger functor whenever the underlying Markov category has conditionals.The result applies in particular to BorelStoch and generalizes an earlier explicit construction.
Almost sure determinism: Almost surely deterministic morphisms form a symmetric monoidal subcategory Prob(C) of ProbStoch(C) under causality.The paper also derives several sufficient conditions for almost sure determinism, including strict positivity and the existence of conditionals.

14. Sufficient statistics and the Fisher–Neyman factorization theorem

The paper defines statistical models, statistics, and sufficiency categorically through Markov kernels and conditional independence. It proves compositionality and an abstract characterization of sufficiency that specializes to Fisher–Neyman factorization in finite probability.

Models and statistics: A statistical model is a morphism p : Θ →X, while a statistic is a deterministic morphism s : X →V.This treats models as parametrized distributions and statistics as functions of the sample.
Models and statistics: Combining a statistic with a model produces the joint morphism Θ →V ⊗X and displays Θ ⊥⊥V | X.The conditional-independence formulation connects the categorical construction to the statistic’s role.
Sufficiency: A statistic is sufficient when a witness α : V →X makes the conditional-independence formulation Θ ⊥⊥X | V hold alongside Θ ⊥⊥V | X.The witness also almost surely splits the statistic and acts like an inference over sample outcomes consistent with its value.
Sufficiency: If s is sufficient for p and t is sufficient for the pushforward model sp, then ts is sufficient for p.Sufficiency therefore composes across successive reductions of the sample information.
Fisher–Neyman characterization: Under strict positivity, s is sufficient if and only if some α : V →X satisfies αsp = p and sα =sp-a.s. idV .These conditions provide an alternative characterization of sufficiency witnesses.
Fisher–Neyman characterization: In FinStoch, the characterization yields the Fisher–Neyman factorization into one term depending only on x and another depending on θ through s(x).Conversely, a Fisher–Neyman factorization constructs a witness satisfying the categorical conditions.
Scope: The paper leaves open whether the abstract characterization specializes to the general measure-theoretic Fisher–Neyman factorization theorem.The established finite-set correspondence does not settle the general measurable-space case.

15. Complete morphisms, ancillary statistics, and Basu’s theorem

The paper recasts completeness, ancillary statistics, and Basu’s theorem in Markov-category terms. Its definitions recover bounded completeness in Stoch and yield a categorical independence theorem for sufficient and ancillary statistics.

Completeness: Completeness is defined for a morphism f : X →Y by requiring gf = hf to imply g =f-a.s. h.Unlike the standard terminology, completeness depends on the composite morphism sp rather than separately on a statistic and model.
Completeness: In FinStoch, f is complete exactly when the affine hull of im(f) is a face of the probability simplex over Y.For f : I →Y, completeness is equivalent to being a Dirac measure and therefore to determinism.
Completeness: In Stoch, the categorical definition is equivalent to bounded completeness: vanishing integrals of bounded measurable β imply β = 0 f(−|x)-almost surely.The paper states that this is the standard measure-theoretically relevant notion.
Completeness and sufficiency: Every deterministic morphism is complete, and completeness simplifies sufficiency under strict positivity.If sp is complete, s is sufficient exactly when a witness α satisfies αsp = p.
Ancillarity: An ancillary statistic is defined by parameter-independence, expressed as Θ ⊥⊥T | I.This formalizes a statistic carrying no information about the model parameters.
Basu’s theorem: If s is sufficient, sp is complete, and a is ancillary, the joint morphism of s and a satisfies the categorical independence conclusion of Basu’s theorem.The proof factors the relevant morphism using sufficiency and ancillarity, then applies completeness.
Basu’s theorem: Because completeness becomes bounded completeness in Stoch, the categorical theorem essentially reproduces the standard Basu theorem there.The result therefore connects the abstract formulation to classical measure-theoretic statistics.

16. Minimal sufficient statistics and Bahadur’s theorem

The paper orders statistics by whether one can compute one from another almost surely, defines minimal sufficiency as a least sufficient statistic, and proves a categorical Bahadur theorem. Existence of minimal sufficient statistics remains open in general.

Bahadur’s theorem: Under strict positivity, if a model has a minimal sufficient statistic, every complete sufficient statistic is minimal sufficient.This is the paper’s categorical version of Bahadur’s theorem.
Informativeness: For statistics s and t, t ≤s when t equals cs almost surely under p for some morphism c.This relation forms a preorder in which more informative statistics lie higher.
Minimal sufficiency: A statistic is minimal sufficient when it is a least element among the sufficient statistics for the model.Any two minimal sufficient statistics determine each other in the almost-sure computational sense.
Bahadur’s theorem: The proof uses sufficiency witnesses and completeness of sp to show that the given statistic lies below its comparison with a minimal sufficient statistic.The argument relies on the almost-sure factorization relations supplied by the witnesses.
Open directions: The paper does not establish when every statistical model has a minimal sufficient statistic.It conjectures that suitable colimits and compatibility with the Markov-category structure may provide such existence results.
Open directions: A second proposed direction is to characterize the statistical models for which a given deterministic morphism is sufficient.This reverses the usual problem of finding a statistic for a fixed model.