the missing normalization equation in probabilistic programming

Work on probability theory without updating is common.

• A Synthetic Approach to Markov Kernels (Fritz, 2020): affine.
• Disintegration and Bayesian Inversion via String Diagrams (Cho, Jacobs, 2017): affine.
• A Convenient Category for Higher-Order Probability Theory (Heunen et al, 2017): measurable base.

We focus on work that allows ‘updating’ or ‘scoring’.

• Kozen, 1981: misses normalization.
• Panangaden, 1999: misses normalization.
• Staton, 2017: misses normalization, added as a primitive.
• Cho, Jacobs, 2017: misses normalization, uses subdistributions.
• Faggian, Ronchi della Rocca, 2019: uses subdistributions.
• Borgstrom, Dal Lago, et al, 2017: uses subdistributions.
• Jacobs, Széles, Stein, 2025: normalization as a primitive.
• Jacobs, Stein, 2023: uses multisets.
• Dash, Kaddar, Paquet, Staton, 2022: uses an affine monad but then an unnormalized one.
• Staton, Yang, Wood, Heunen, Kammar, 2016: uses unnormalized distributions.
• Di Lavore, Román, Sobocinski: uses subdistributions and normalization as property.

See also.

• substochastic versus unnormalized kernels
• probabilistic programming

Gallery

From Commutative Semantics for Probabilistic Programming (Staton, 2017).

From Disintegration and Bayesian Inversion via String Diagrams (Cho, Jacobs, 2017).

From Semantics for Probabilistic Programming, Higher-Order Functions, Continuous Distributions, and Soft Constraints (Staton, Yang, Wood, Heunen, Kammar, 2016).

From Contextual Equivalence for Probabilistic Programs with Continuous Random Variables and Scoring (Culpepper, Cobb).