State–Predicate Duality

In a markov-category the two ways of feeding a channel carry opposite variance, whether from the left or from the right. A state pushes forward covariantly and a predicate pulls back contravariantly, and pairing the two returns the expectation. This is the categorical skeleton of the “arrangement ⇔ table” reading of probabilistic computation.

Fix a Markov category with a chosen object of scalars , a commutative semiring . A state on is a morphism , and a predicate, also called an effect, on is a morphism into an effect object, in the simplest case a map valued in scalars. States act by post-composition and so vary covariantly in the channel, whereas predicates act by pre-composition and vary contravariantly. The two meet in the scalar pairing

read as the expectation of the observable in the state .

Definition. States push forward, predicates pull back

A channel transports states forward, , and predicates backward, . Adjointness of the two actions is the identity , i.e. . This is associativity of composition, now read as “change of variables commutes with taking expectations”.

Property. The algebra is semiring-valued

Predicates on form an -module, since pointwise sum and scalar multiple make a commutative-semiring-valued function algebra, with the always-true predicate. Assembled over the base category, these predicate algebras form a predicate fibration / Hoare logic. Substochastic and possibilistic models differ only in the choice of (, the Boolean semiring, the tropical semiring), so the same diagrams recompute in each.

Remark. Arrangement ⇔ table

A string-diagram fixes an arrangement of wires and boxes; evaluating it against a state and reading off a predicate produces a table of numbers in . State–predicate duality is what makes that pass well-defined regardless of where the diagram is cut. Contracting from the left accumulates a state, and contracting from the right accumulates a predicate. Probabilistic computation then becomes a discipline of contracting diagrams rather than manipulating densities.

References

• Kenta Cho and Bart Jacobs, “Disintegration and Bayesian inversion via string diagrams”, MSCS 29 (2019), arXiv:1709.00322
• Bart Jacobs, “New Directions in Categorical Logic, for Classical, Probabilistic and Quantum Logic”, Logical Methods in Computer Science 11 (2015), arXiv:1205.3940