💻 computer science

Order in Partial Markov Categories

This paper establishes that partial Markov categories are canonically preorder-enriched, explores the relationship between codiagonal maps and order properties, and proves that updating increases validity via a synthetic Cauchy–Schwarz inequality.

Original authors: Elena Di Lavore, Mario Román, Paweł Sobociński, Márk Széles

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Elena Di Lavore, Mario Román, Paweł Sobociński, Márk Széles

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Probability with "Maybe"

Imagine you are building a robot that makes decisions based on probability. Usually, we teach robots to handle total probabilities: "There is a 50% chance of rain, so I will bring an umbrella." The math works perfectly, and the robot always finishes its job.

But in the real world, things often go wrong. What if the robot tries to learn from evidence that contradicts its beliefs? For example, if it believes it's raining (100% chance) but the sensor says "It's a sunny desert," the robot can't just "update" its belief normally. The update process fails or becomes partial. It's like trying to divide by zero; the operation is undefined.

This paper introduces a new mathematical framework called Partial Markov Categories. Think of this as a "toolbox for broken or incomplete probability." It allows us to mathematically describe situations where a calculation might fail, stop halfway, or simply not apply.

The Main Discovery: A "Ladder" of Possibilities

The authors' biggest discovery is that in this new toolbox, every possible action (or "morphism") has a natural order.

The Analogy: The Ladder of Certainty
Imagine you have a list of different ways a robot could try to solve a problem.

Level 1 (Bottom): The robot tries, fails immediately, and gives up. (This is the "least" amount of work).
Level 2: The robot tries, gets stuck, but manages to output a tiny bit of info.
Level 3: The robot succeeds perfectly.

The paper proves that you can always arrange these actions on a ladder. If Action A is "less than" Action B, it means Action A is essentially a "broken" or "incomplete" version of Action B. You can get from A to B by "fixing" it or adding more information.

This is called Preorder Enrichment. In plain English: The math gives us a built-in ruler to measure how "complete" or "valid" a probabilistic step is.

Key Concepts Explained

1. The "Comparator" (The Equality Check)

In standard probability, you can copy data and throw data away. In this new framework, the authors introduce a special tool called a Comparator (or "Cap").

Metaphor: Imagine a magic mirror. If you put two objects in front of it, the mirror tells you if they are identical.
Why it matters: The paper shows that if your system has this "equality mirror," it automatically creates the "ladder" of order we mentioned above. The ability to check "Are these two things the same?" is what gives the system its structure.

2. The "Least Conditional" (The Minimal Fix)

In probability, we often need to calculate a "conditional" (e.g., "What is the chance of rain given that it is cloudy?").

The Problem: There might be many ways to calculate this. Some ways include "junk" or unnecessary noise.
The Solution: The authors prove that there is always a "Least Conditional."
Analogy: Imagine you are trying to fix a leaky pipe. You could patch it with a giant bucket of cement (overkill), or you could use a tiny, perfect drop of glue. The "Least Conditional" is that perfect, tiny drop of glue. It does exactly what is needed and nothing more. It is the most efficient, "minimal" way to update your beliefs.

3. Updating Increases Validity (The Cauchy-Schwarz Connection)

The paper ends with a famous result about Bayesian Updating (learning from new evidence).

The Intuition: If you have a belief (a prior) and you get new evidence, your belief should become "more valid" or "more certain" regarding that evidence.
The Math Magic: The authors use a synthetic version of the Cauchy-Schwarz inequality (a famous math rule about vectors and lengths) to prove this.
The Metaphor: Imagine you are guessing the weight of a mystery box.
- Before: You guess 5kg. Your confidence is low.
- Evidence: You see a label that says "Heavy."
- After: You update your guess to 10kg.
- The Result: The paper proves mathematically that after seeing the "Heavy" label, your belief in the "Heavy" label is now stronger (more valid) than it was before. The act of updating always increases the validity of the evidence you just saw.

Why Should You Care?

This paper isn't just about abstract math; it's about making AI and probability theory more robust.

Handling Failure: Real-world AI systems crash or encounter impossible data. This framework gives them a way to say, "I can't do this specific step, but here is the closest thing I can do," without breaking the whole system.
Better Reasoning: By understanding the "ladder" of probabilities, we can build better algorithms for medical diagnosis, self-driving cars, and financial modeling, where "partial" information is the norm, not the exception.
Unifying Theory: It connects different areas of math (like logic, probability, and computer science) under one roof, showing that the rules for "fixing broken calculations" are the same whether you are dealing with coins, sets, or complex neural networks.

Summary

The authors built a new mathematical language for imperfect probability. They discovered that in this language, every action has a rank on a ladder of completeness. They proved that if you can check for equality, you can find the most efficient way to update your beliefs. Finally, they showed that learning from evidence always makes that evidence "more true" in your updated worldview. It's a rigorous way of saying: "Even when things go wrong, there is a logical order to how we fix them."

1. Problem Statement

The paper addresses a fundamental limitation in Markov categories, a synthetic framework for probability theory. While Markov categories successfully model total probabilistic computations (where every process yields a result), they fail to capture partial probabilistic computations. In real-world scenarios, such as Bayesian updating, operations can be undefined if the evidence contradicts the prior belief (e.g., updating with an impossible event).

Standard Markov categories enforce the "naturality of discarding," implying that all maps are total. To model partiality, one must drop this axiom, leading to Copy-Discard (CD) categories. However, existing frameworks for partial probability (like quasi-Markov categories or restriction categories) often lack a unified, abstract way to reason about the ordering of morphisms (inequalities) and the existence of least conditionals (canonical ways to decompose processes).

The core problem is to establish a canonical preorder enrichment for partial Markov categories that:

Unifies various known orderings in probability theory.
Allows for inequational reasoning (e.g., proving that updating increases validity).
Clarifies the structural relationship between partiality, conditionals, and equality checks (comparators).

2. Methodology

The authors employ categorical probability theory using string diagrams and symmetric monoidal categories. Their methodology involves:

Defining New Structures: They introduce Copy-Discard-Compare (CDC) categories, which extend CD categories with "comparators" (maps $\mu: X \otimes X \to X$ ) or "caps" ( $\cap: X \otimes X \to I$ ) to assert equality of resources.
Constructing a Preorder: They define a conditional inequality ( $\sqsubseteq$ ) between parallel morphisms $f, g: X \to Y$ . $f \sqsubseteq g$ if $f$ can be obtained from $g$ via "conditional composition" with a witness morphism $r$ (representing a sub-probability or predicate).
Proving Enrichment: They demonstrate that this relation forms a preorder and that the monoidal structure (composition and tensor product) is monotone with respect to this order, thereby proving the category is preorder-enriched.
Analyzing Least Conditionals: They investigate the existence of "least" conditionals (smallest decompositions of a morphism) under both the new conditional order and the existing restriction order.
Synthetic Inequalities: They axiomatize the Cauchy-Schwarz inequality and the Means inequality within this categorical framework to derive properties of Bayesian updating.

3. Key Contributions

A. Canonical Preorder Enrichment

The paper proves that every partial Markov category is canonically enriched in the category of preorders.

Definition: For $f, g: X \to Y$ , $f \sqsubseteq g$ iff there exists a witness $r: Y \otimes X \to I$ such that $f = g \triangleleft r$ (where $\triangleleft$ is conditional composition).
Universality: This construction recovers well-known orderings in specific models:
- Pointwise order in subprobability kernels ( $FinStoch_{\leq 1}$ , $BorelStoch_{\leq 1}$ ).
- Restriction order in Cartesian restriction categories (partial functions).
- Subrelation order in Cartesian bicategories of relations.
Minimality: The conditional preorder is the least subunital preorder enrichment (where "true" is the maximal effect).

B. Relationship Between Comparators and Least Conditionals

The authors establish a deep structural link between the existence of comparators (equality checks) and least conditionals:

Theorem 4.4 & 4.6: In a copy-discard category, the existence of a $\preceq$ -least conditional for the copy map ( $\delta$ ) and identity map ($id$) is equivalent to the existence of a comparator (multiplication $\mu$ ) and a cap.
Specifically, the comparator $\mu$ is the least conditional of the copy map, and the cap $\cap$ is the least conditional of the identity map.
This implies that a category admits a "compare" structure if and only if it possesses these specific least conditionals.

C. Synthetic Cauchy-Schwarz and Validity Increase

The paper introduces a synthetic version of the Cauchy-Schwarz inequality and the Means inequality ( $QM \geq AM$ ) using the conditional preorder.

Validity Increase Theorem: Using these inequalities, they prove that Bayesian updating increases the validity of evidence.
Formally, for a prior state $\sigma$ and a predicate $p$ , the validity of $p$ in the posterior ( $p^\dagger_\sigma$ ) is greater than or equal to its validity in the prior ( $\sigma \# p$ ).
This result is derived abstractly without relying on specific measure-theoretic details, provided the category satisfies the synthetic Means inequality and has cancellative non-zero scalars.

4. Key Results

Theorem 3.3: Every partial Markov category is a preorder-enriched symmetric monoidal category under the conditional inequality.
Proposition 3.10 & 3.11: The conditional preorder coincides with the pointwise order in subprobability kernels and the restriction order in Cartesian restriction categories.
Theorem 4.4: In a Copy-Discard-Compare category, the comparator $\mu$ is the $\preceq$ -least conditional of the copy map $\delta$ .
Theorem 4.6: If a copy-discard category has least conditionals for copy and identity maps satisfying specific axioms, it is a Copy-Discard-Compare category.
Theorem 5.13: In a partial Markov category satisfying the Means inequality with cancellative non-zero scalars, updating a prior with a predicate increases the predicate's validity: $\sigma \# p \sqsubseteq p^\dagger_\sigma \# p$ .
Counter-examples: The paper notes that not all partial Markov categories have least conditionals (e.g., $BorelStoch_{\leq 1}$ lacks a least conditional for the Lebesgue measure), highlighting the necessity of the "discrete" or "balanced" assumptions for certain results.

5. Significance

Unification: The work provides a single, abstract framework that unifies disparate orderings found in probabilistic programming, partial functions, and relation theory. It shows that these are not ad-hoc constructions but instances of a general "conditional inequality."
Handling Partiality: It offers a rigorous categorical foundation for partial probabilistic computation, crucial for modeling real-world inference where data may be missing or contradictory.
Synthetic Reasoning: By deriving the "validity increase" property (a cornerstone of Bayesian inference) from abstract axioms (Cauchy-Schwarz/Means inequalities), the paper demonstrates the power of synthetic probability theory to recover deep probabilistic theorems without resorting to concrete measure theory.
Structural Insight: The equivalence between the existence of comparators and least conditionals reveals that the ability to "compare" resources is structurally tied to the existence of canonical, minimal probabilistic decompositions.

In summary, this paper advances the theory of categorical probability by formalizing how partiality induces a natural order, linking this order to the algebraic structure of the category (comparators), and using this structure to prove fundamental properties of Bayesian inference synthetically.