Partial Markov Categories

Elena Di Lavore, Mario Román, Paweł Sobociński · 2025 · arxiv arXiv:2502.03477

Prereqs: 🍞 Fritz 2020 (Markov categories). 🍞 Staton 2025 (Hoare logic) helps.

Not every computation succeeds. A partial Markov category extends Fritz's Markov categories with restriction — morphisms can fail, observations can have zero probability, and Bayes' theorem handles the conditioning. This is where Pearl's conditioning and Jeffrey's updating both live.

Restriction — morphisms that can fail

A restriction category (nLab) gives each morphism a "domain of definition" — a partial identity that says where the morphism is defined. In probabilistic terms: some observations have zero probability, and conditioning on them is undefined.

Scheme

; A partial function: defined on some inputs, undefined on others
; Restriction: the domain where the function is defined

(define (partial-div x y)
  (if (= y 0) 'undefined (/ x y)))

(define (restriction f)
  ; Returns a predicate: where is f defined?
  (lambda (args)
    (not (eq? (apply f args) 'undefined))))

(define div-defined? (restriction partial-div))

(display "div(6,3) = ") (display (partial-div 6 3)) (newline)
(display "div(6,0) = ") (display (partial-div 6 0)) (newline)
(display "defined at (6,3)? ") (display (div-defined? '(6 3))) (newline)
(display "defined at (6,0)? ") (display (div-defined? '(6 0)))

Observations — conditioning on events

An observation is a partial morphism that "tests" whether an event occurred. If the event has zero probability, the observation is undefined — you can't condition on something that can't happen. This is the categorical version of "divide by zero in Bayes' rule."

Scheme

; Observation: condition a distribution on an event
; If P(event) = 0, conditioning is undefined

(define (condition dist event)
  ; dist: alist of (value . probability)
  ; event: predicate on values
  (let* ((matching (filter (lambda (p) (event (car p))) dist))
         (total (apply + (map cdr matching))))
    (if (= total 0)
      'undefined  ; can't condition on impossible event
      (map (lambda (p)
        (cons (car p) (/ (cdr p) total)))
      matching))))

(define dist '((1 . 0.3) (2 . 0.5) (3 . 0.2)))

(display "P(even): ")
(display (condition dist even?)) (newline)

(display "P(> 10): ")
(display (condition dist (lambda (x) (> x 10)))) (newline)
; Conditioning on impossible event is undefined

Bayes' theorem in the partial setting

Bayes' theorem becomes a theorem about partial morphisms: the posterior is defined exactly when the marginal likelihood is nonzero. The restriction structure tracks this automatically — no ad hoc division-by-zero guards needed.

Scheme

; Bayes' theorem: partial when marginal likelihood = 0

(define (bayes prior likelihood evidence)
  (let* ((joint (map (lambda (hp)
    (let ((h (car hp)) (ph (cdr hp)))
      (let ((pe (assoc evidence (likelihood h))))
        (if pe
          (cons h (* ph (cdr pe)))
          (cons h 0)))))
    prior))
    (total (apply + (map cdr joint))))
    (if (= total 0)
      'undefined  ; restriction: evidence has zero probability
      (map (lambda (jp)
        (cons (car jp) (/ (cdr jp) total))) joint))))

(define prior '((A . 0.4) (B . 0.6)))
(define (likelihood h)
  (if (eq? h 'A) '((yes . 0.8) (no . 0.2))
                  '((yes . 0.3) (no . 0.7))))

(display "P(H|yes): ") (display (bayes prior likelihood 'yes)) (newline)
(display "P(H|no):  ") (display (bayes prior likelihood 'no)) (newline)

; Impossible evidence
(define (likelihood2 h) '((yes . 0.0) (no . 1.0)))
(display "P(H|yes) with zero likelihood: ")
(display (bayes prior likelihood2 'yes))

Pearl vs Jeffrey updating

Pearl conditioning sets evidence to a certainty (hard observation). Jeffrey updating sets evidence to a distribution (soft observation). Both are instances of the same categorical structure — Jeffrey generalizes Pearl by allowing partial observations.

Scheme

; Pearl: hard evidence (certainty)
; Jeffrey: soft evidence (distribution over observations)

(define (pearl-update prior likelihood evidence)
  ; Condition on evidence = certain
  (let* ((joint (map (lambda (hp)
    (let* ((h (car hp)) (ph (cdr hp))
           (pe (cdr (assoc evidence (likelihood h)))))
      (cons h (* ph pe)))) prior))
    (total (apply + (map cdr joint))))
    (map (lambda (jp) (cons (car jp) (/ (cdr jp) total))) joint)))

(define (jeffrey-update prior likelihood evidence-dist)
  ; Weight by soft evidence distribution
  (let ((updated (map (lambda (hp)
    (let* ((h (car hp)) (ph (cdr hp))
           (weighted (apply + (map (lambda (ep)
             (* (cdr ep) (cdr (assoc (car ep) (likelihood h)))))
             evidence-dist))))
      (cons h (* ph weighted)))) prior)))
    (let ((total (apply + (map cdr updated))))
      (map (lambda (p) (cons (car p) (/ (cdr p) total))) updated))))

(define prior '((A . 0.5) (B . 0.5)))
(define (lk h) (if (eq? h 'A) '((e1 . 0.8) (e2 . 0.2))
                                '((e1 . 0.3) (e2 . 0.7))))

(display "Pearl (e1 certain): ")
(display (pearl-update prior lk 'e1)) (newline)
(display "Jeffrey (70% e1, 30% e2): ")
(display (jeffrey-update prior lk '((e1 . 0.7) (e2 . 0.3))))

; Pearl: hard evidence (certainty)
; Jeffrey: soft evidence (distribution over observations)

(define (pearl-update prior likelihood evidence)
  ; Condition on evidence = certain
  (let* ((joint (map (lambda (hp)
    (let* ((h (car hp)) (ph (cdr hp))
           (pe (cdr (assoc evidence (likelihood h)))))
      (cons h (* ph pe)))) prior))
    (total (apply + (map cdr joint))))
    (map (lambda (jp) (cons (car jp) (/ (cdr jp) total))) joint)))

(define (jeffrey-update prior likelihood evidence-dist)
  ; Weight by soft evidence distribution
  (let ((updated (map (lambda (hp)
    (let* ((h (car hp)) (ph (cdr hp))
           (weighted (apply + (map (lambda (ep)
             (* (cdr ep) (cdr (assoc (car ep) (likelihood h)))))
             evidence-dist))))
      (cons h (* ph weighted)))) prior)))
    (let ((total (apply + (map cdr updated))))
      (map (lambda (p) (cons (car p) (/ (cdr p) total))) updated))))

(define prior '((A . 0.5) (B . 0.5)))
(define (lk h) (if (eq? h 'A) '((e1 . 0.8) (e2 . 0.2))
                                '((e1 . 0.3) (e2 . 0.7))))

(display "Pearl (e1 certain): ")
(display (pearl-update prior lk 'e1)) (newline)
(display "Jeffrey (70% e1, 30% e2): ")
(display (jeffrey-update prior lk '((e1 . 0.7) (e2 . 0.3))))

Notation reference

Paper	Scheme	Meaning
f̄ (restriction)	(restriction f)	Domain where f is defined
obs_E	(condition dist event)	Observation (condition on event)
f†_π	(bayes prior lk ev)	Bayesian inverse (partial when P(ev)=0)
Pearl(e)	(pearl-update ...)	Hard conditioning
Jeffrey(q)	(jeffrey-update ...)	Soft conditioning

Neighbors

Other paper pages

🍞 Fritz 2020 — total Markov categories (the base that this extends)
🍞 Parzygnat 2020 — quantum Markov categories (different extension: dagger)
🍞 Cho, Jacobs 2015 — effectus theory (predicates as effects, related partiality)
🍞 Staton 2025 — Hoare logic (wp over partial morphisms)

Foundations (Wikipedia)

Translation notes

The examples use finite distributions with explicit zero-probability checks. The paper works with restriction categories and subdistribution monads, where partiality is built into the categorical structure via restriction idempotents. For example: the conditioning function on this page returns 'undefined when the event has zero probability. In the paper, this is a restriction idempotent — a morphism e with e;e = e that acts as a partial identity, and the zero-probability case is where the restriction is the zero morphism. The division-by-zero guard is the same; the categorical abstraction is not.

Every example is Simplified.

Ready for the real thing? arxiv

Read the paper. Start at §3 for partial Markov categories, §5 for observations and Bayes' theorem, §7 for Pearl and Jeffrey updates.

← Parzygnat 2020 · 16 of 21 by june.kim Panangaden 2009 · 18 of 21 →