Pith. sign in

REVIEW 2 major objections 3 minor 39 references

A categorical account of the Metropolis-Hastings algorithm

T0 review · 2 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper establishes that the reversibility of an abstract Metropolis–Hastings kernel is equivalent, in a wide class of categorical probability settings, to one balancing equation holding almost everywhere.

desk verdict Good categorical framework, but the advertised full recovery of Theorem 1.1 overstates what is proven: the singular-part acceptance condition is never derived. read the letter →

arxiv 2601.22911 v2 pith:7VUPEENT submitted 2026-01-30 stat.CO math.CTmath.PR

Rob Cornish , Andi Q. Wang This is my paper · ORCID
classification stat.COmath.CTmath.PR MSC 18M0560J22
keywords Metropolis-HastingsMarkovcategoriesCDsemiadditivereversibilitybalancingconditionRadon-NikodymderivativeLebesguedecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether the correctness condition at the heart of Metropolis–Hastings—reversibility with respect to a target distribution—can be proved and characterised using categorical probability instead of measure-theoretic calculation. It shows that in a finitely cancellative semiadditive CD category (a setting with unnormalised kernels, addition of morphisms, and a workable notion of Radon–Nikodym derivative), the involutive MH kernel P_MH = α·φ + (1−α)·id is target-reversible if and only if the acceptance probability satisfies α = (α∘φ) ∗ r almost everywhere, where r is the Radon–Nikodym derivative of the target pushed forward through the involution. This recovers the classical involutive-MH balancing condition and supplies the previously missing converse. The same condition extends to skew-reversible samplers. A sympathetic reader should care because the paper reduces a correctness property of a widely used algorithm to one algebraic identity, showing that categorical tools can carry genuine statistical content.

What carries the argument

The load-bearing construction is the enrichment of CD categories over commutative monoids: hom-sets carry an addition operation, so the full MH kernel can be written as a convex combination of two morphisms. Two further notions carry the proof: finite morphisms, which behave cancellatively under addition, and Radon–Nikodym derivatives as effects between morphisms. Reversibility of the first summand α·φ is proved equivalent to the balancing condition by string-diagram manipulation, while the second summand is trivially reversible and substochastic; finite cancellativity lets the proof cancel it and conclude the equivalence for the whole kernel. Absolute continuity, singular measures, and Lebe

What would settle it

In the category of s-finite kernels, take a finite measure μ and a deterministic involution φ with μ∘φ^{-1} absolutely continuous with respect to μ, choose an acceptance function α satisfying α(ξ)=α(φ(ξ))r(ξ) for μ-almost every ξ, and check detailed balance of the kernel P_MH directly on a generating algebra. If any such α fails to give a μ-reversible kernel, Theorem 4.27 is false; if a reversible kernel exists whose α violates the balancing equation on a set of positive μ×μ measure, the converse is false. A sharper structural test is to construct a finitely cancellative semiadditive CD catego

Watch

Extended reading notes

Core claim

The central claim, Theorem 4.27, is an if-and-only-if statement: in a finitely cancellative semiadditive CD category, with finite target μ, deterministic involution φ, probability α, and Radon–Nikodym derivative r = d(φ∘μ)/dμ, the abstract Metropolis–Hastings kernel P_MH := α·φ + (1−α)·id is μ-reversible exactly when α = (α∘φ) ∗ r holds μ-almost everywhere. Here CD categories are the categorical framework for unnormalised kernels, and semiadditive means morphisms can be added. In the standard category of s-finite kernels this becomes the familiar statement that the Metropolis–Hastings kernel with involution φ is reversible with respect to μ precisely when its acceptance function obeys α(ξ)=α

Load-bearing premise

The theorem is conditional on the existence of the Radon–Nikodym derivative r = d(φ∘μ)/dμ in a finitely cancellative semiadditive CD category; the framework itself proves no general existence result, and for the classical instantiation the singular-part statement is imported from the standard Lebesgue decomposition theorem.

Editorial extensions

If this is right

  • The balancing condition is both necessary and sufficient: any reversible involutive MH kernel in this setting must satisfy it, not merely kernels constructed from a balancing function.
  • The same single equation characterises skew-reversible MH-type kernels, generalising earlier sufficient conditions and adding a converse.
  • Substochastic kernels, finiteness, absolute continuity, singularity, and Lebesgue decompositions become algebraic facts about addition and preorders, so the proof transfers to any category with the required structure.
  • The categorical framework supplies the decomposition and cancellation arguments; for the classical instantiation only the existence of Lebesgue decompositions is imported from measure theory.
  • Markov-category formulations of invariance, reversibility, and state-space augmentation extend to unnormalised CD settings, offering a unified language for correctness arguments in MCMC.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The result suggests that the balancing equation itself, not any particular balancing function, is the essential design constraint for involutive MH: new acceptance schemes could be obtained by solving α(ξ)=α(φ(ξ))r(ξ) directly.
  • A natural next step, left open by the paper, is a categorical Radon–Nikodym theorem deriving existence of derivatives and Lebesgue decompositions from order completeness; if such a theorem exists, MH correctness proofs could be fully synthetic.
  • Because the proof is internal to the category, other concrete finitely cancellative semiadditive CD categories are testable arenas: finding one where the balancing condition fails to characterise reversibility would pinpoint exactly which axioms the classical result depends on.
  • The preorder-based treatment of absolute continuity might transfer to other MCMC correctness arguments, such as those for continuous-time or Hamiltonian proposals, whenever they can be expressed as involutive kernels.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper develops a categorical framework for the Metropolis–Hastings kernel. It first formulates invariance, reversibility, and skew-reversibility in Markov categories, then moves to CD categories for the unnormalised first summand, and finally to CD categories enriched over commutative monoids ('semiadditive CD categories'). In this setting it defines substochastic morphisms, probabilities, cancellative/finite morphisms, absolute continuity via a preorder, singular morphisms via meets, and abstract Lebesgue decompositions. The main result, Theorem 4.27, gives an 'if and only if' for reversibility of the abstract MH kernel P_MH = α·φ + α^c·id: the balancing condition α = (α∘φ)∗r holds μ-a.e., assuming a Radon–Nikodym derivative r = d(φ∘μ)/dμ exists. Instantiating in sfKern gives a converse to the absolutely continuous (quasi-invariant) case of the Andrieu–Lee–Livingstone balancing condition, and Corollary 4.44 constructs the usual absolutely continuous/singular decomposition of μ under an involution. The paper claims to recover Theorem 1.1 and to supply a converse.

Significance. If completed, the paper would make a valuable contribution: it gives a clean synthetic proof of the balancing condition, a converse in the quasi-invariant case, a skew-reversible extension, and a reusable toolkit (CMon-enriched CD categories) for substochastic kernels, absolute continuity, and Lebesgue decompositions. The proofs are detailed and the hypotheses are explicit; the paper also honestly acknowledges in Corollary 4.44 that the existence of Lebesgue decompositions is imported from the classical theorem. No circularity is apparent: the balancing condition is derived from the categorical axioms rather than assumed. The main caveat is that the advertised recovery of Theorem 1.1 is incomplete for the singular component; this is fixable by qualification or by adding a missing argument.

major comments (2)
  1. [§4.6.1, Corollaries 4.28 and 4.44] Corollary 4.44 is said to give 'the remaining part of Theorem 1.1', but it only constructs S. It does not prove that μ-reversibility of P_MH forces α=0 on S^c. Theorem 4.27 is an iff only when r=d(φ∘μ)/dμ exists; in sfKern this means μ^φ≪μ, which for an involution φ implies μ≡μ^φ, so S is μ-null. Thus Corollary 4.28 covers only the quasi-invariant case, and the '0 otherwise' clause of (2) is not derived. The sufficiency of α=0 is trivial; the necessity—needed for a full converse—is missing. Example: E={0,1}, φ swap, μ=δ_0; the classical condition requires α(0)=0, but no categorical theorem applies because r does not exist. Please add such an argument or explicitly qualify the claimed recovery of Theorem 1.1.
  2. [Section 5 / conclusion] The conclusion states that the paper gives a 'purely algebraic derivation of their balancing condition in Theorem 1.1'. This is stronger than what is established, since the singular-part clause of the balancing condition is not derived categorically. The theorem statement of Theorem 4.27 and the surrounding discussion should either be expanded to handle the singular component or restricted to the absolutely continuous / quasi-invariant case.
minor comments (3)
  1. [Introduction / general] There are several typos: 'already lead to' should be 'already led to'; Corollary 4.28 has 'determinsitic' for 'deterministic'; Proposition 4.25 reads 'If both P and Q and are μ-reversible'.
  2. [Proof of Proposition 4.26] The cancelled summand is described only verbally as 'a composition of a finite morphism and a substochastic morphism'. A displayed string diagram or an explicit reference to Proposition 4.22 would improve readability.
  3. [Remark 4.23] The phrase 'restricting to a cancellative μ' is initially opaque before the reader recalls Proposition 4.17. Consider writing 'finite (equivalently, σ-finite) μ' when instantiating in sfKern.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the balancing condition is derived from categorical axioms, with the singular-component scope handled by an external decomposition theorem.

full rationale

The main derivation is self-contained. Theorem 4.27's balancing condition (32) is obtained by combining Theorem 3.9 (reversibility of the first summand iff equation (18), proved from Propositions 3.8 and 2.8) with Propositions 4.25 and 4.26 (sum decomposition and cancellation), rather than by assuming the target condition. Corollary 4.28 instantiates this result in sfKern and explicitly states that it fully recovers Theorem 1.1 only in the case where μ and μ^φ are mutually absolutely continuous so that the Radon–Nikodym derivative r exists. The remaining singular-part decomposition is recovered in Corollary 4.44 by importing the classical Lebesgue decomposition theorem [19], which is an external mathematical result, not a self-citation or a fitted input. The paper also acknowledges in its conclusion that it only isolates properties that Lebesgue decompositions should satisfy and leaves existence conditions to future work. A genuine scope gap exists: the necessity of α=0 on the singular component of Theorem 1.1 is not derived in the paper. However, that is a completeness/correctness limitation, not circularity: no part of the paper equates the desired singular-component acceptance condition with an input by construction, and the central iff theorem is not forced by prior work of the same authors. There are no load-bearing self-citations, fitted parameters renamed as predictions, or uniqueness claims imported from the authors' own prior work.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities: the paper's novel definitions are mathematical structure, not fitted quantities or unexplained physical objects. The assumptions listed are explicit hypotheses of the theorems.

assumptions (5)
  • domain assumption C is a finitely cancellative semiadditive CD category with monoidal CMon-enrichment.
    The whole of Section 4 assumes this structure to define addition of morphisms, substochasticity, and cancellation in Proposition 4.26 and Theorem 4.27.
  • domain assumption μ is finite and the Radon–Nikodym derivative r = d(φ∘μ)/dμ exists.
    Theorem 4.27 and Corollary 4.28 require this for the iff condition; in sfKern this means μ^φ ≪ μ. The singular part is only handled later via an external decomposition.
  • domain assumption C is zero-sum-free in Theorem 4.43.
    Needed for Proposition 4.34 implication P≤Q ⇒ P≪Q, which is used in the abstract Lebesgue-decomposition argument.
  • standard math Classical Lebesgue decomposition theorem for σ-finite measures (Halmos 1974).
    Used in Corollary 4.44 to obtain the decomposition S; the authors explicitly say existence of abstract Lebesgue decompositions is left to future work.
  • standard math Standard facts about CD and Markov categories, sfKern as a CD category, and s-finite kernels.
    The categorical framework builds on Cho–Jacobs, Fritz, and Staton; the paper does not re-prove these foundations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A categorical account of the Metropolis-Hastings algorithm." pith.science (2026). https://pith.science/paper/7VUPEENT

@misc{pith2026260122911,
  author       = {Pith},
  title        = {Pith review of: A categorical account of the Metropolis-Hastings algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7VUPEENT}},
  note         = {Machine review of arXiv:2601.22911}
}
abstract

Metropolis-Hastings (MH) is a foundational Markov chain Monte Carlo (MCMC) algorithm. In this paper, we ask whether it is possible to formulate and analyse MH in terms of categorical probability, using a recent involutive framework for MH-type procedures as a concrete case study. We show how basic MCMC concepts such as invariance and reversibility can be formulated in Markov categories, and how one part of the MH kernel can be analysed using standard CD categories. To go further, we then study enrichments of CD categories over commutative monoids. This gives an expressive setting for reasoning abstractly about a range of important probabilistic concepts, including substochastic kernels, finite and $\sigma$-finite measures, absolute continuity, singular measures, and Lebesgue decompositions. Using these tools, we give synthetic necessary and sufficient conditions for a general MH-type sampler to be reversible with respect to a given target distribution.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 1 linked inside Pith

  1. [1]

    Freer, Younesse Kaddar, Jacek Karwowski, Sean Moss, Daniel Roy, Sam Staton, and Hongseok Yang

    Nate Ackerman, Cameron E. Freer, Younesse Kaddar, Jacek Karwowski, Sean Moss, Daniel Roy, Sam Staton, and Hongseok Yang. Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets. Proceedings of the ACM on Programming Languages, 8(POPL):1819–1849, January 2024

    2024

  2. [2]

    A general perspective on the Metropolis-Hastings kernel

    Christophe Andrieu, Anthony Lee, and Sam Livingstone. A general perspective on the Metropolis-Hastings kernel. 2020

    2020

  3. [3]

    Peskun-Tierney ordering for Markovian Monte Carlo: Beyond the reversible scenario.Ann

    Christophe Andrieu and Samuel Livingstone. Peskun-Tierney ordering for Markovian Monte Carlo: Beyond the reversible scenario.Ann. Statist., 49(4):1958– 1981, 2021

    1958

  4. [4]

    GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo

    Nawaf Bou-Rabee, Bob Carpenter, and Milo Marsden. GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo. 2024

    2024

  5. [5]

    Lifting Markov chains to speed up mixing

    Fang Chen, Laszlo Lovasz, and Igor Pak. Lifting Markov chains to speed up mixing. InThe Annual ACM Symposium on Theory of Computing, pages 275–281. ACM, 1999

    1999

  6. [6]

    Disintegration and Bayesian inversion via string diagrams.Mathematical Structures in Computer Science, 29(7):938–971, 2019

    Kenta Cho and Bart Jacobs. Disintegration and Bayesian inversion via string diagrams.Mathematical Structures in Computer Science, 29(7):938–971, 2019

    2019

  7. [7]

    An intro- duction to effectus theory, 2015

    Kenta Cho, Bart Jacobs, Bas Westerbaan, and Abraham Westerbaan. An intro- duction to effectus theory, 2015

    2015

  8. [8]

    Lew, and Vikash K

    Marco Cusumano-Towner, Alexander K. Lew, and Vikash K. Mansinghka. Au- tomating involutive mcmc using probabilistic and differentiable programming, 2020

    2020

Show all 39 references
  1. [9]

    Persi Diaconis, Susan Holmes, and Radford M. Neal. Analysis of a nonreversible Markov chain sampler.The Annals of Applied Probability, 10(3):726–752, 2000

    2000

  2. [10]

    A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics.Advances in Mathematics, 370:107239, 2020

    Tobias Fritz. A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics.Advances in Mathematics, 370:107239, 2020

    2020

  3. [11]

    Weakly markov categories and weakly affine monads.arXiv preprint arXiv:2303.14049, 2023

    Tobias Fritz, Fabio Gadducci, Paolo Perrone, and Davide Trotta. Weakly markov categories and weakly affine monads.arXiv preprint arXiv:2303.14049, 2023

    2023 arXiv

  4. [12]

    Absolute continuity, supports and idempotent splitting in categorical probability

    Tobias Fritz, Tomáš Gonda, Antonio Lorenzin, Paolo Perrone, and Dario Stein. Absolute continuity, supports and idempotent splitting in categorical probability. 2023

    2023

  5. [13]

    De Finetti’s Theorem in Categor- ical Probability.Journal of Stochastic Analysis, 2(4), 2021

    Tobias Fritz, Tomáš Gonda, and Paolo Perrone. De Finetti’s Theorem in Categor- ical Probability.Journal of Stochastic Analysis, 2(4), 2021

    2021

  6. [14]

    When coproducts are biproducts.Mathe- matical Proceedings of the Cambridge Philosophical Society, 161(1):47–51, 2016

    Richard Garner and Daniel Schäppi. When coproducts are biproducts.Mathe- matical Proceedings of the Cambridge Philosophical Society, 161(1):47–51, 2016

    2016

  7. [15]

    Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images.IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):721–741, 1984

    Stuart Geman and Donald Geman. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images.IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6):721–741, 1984

    1984

  8. [16]

    On the accept-reject mechanism for Metropolis–Hastings algorithms.Annals of Applied Probability, 33(6B):5279–5333, 2023

    Nathan Glatt-Holtz, Justin Krometis, and Cecilia Mondaini. On the accept-reject mechanism for Metropolis–Hastings algorithms.Annals of Applied Probability, 33(6B):5279–5333, 2023

    2023

  9. [17]

    Parallel MCMC algorithms: theoretical foundations, algorithm design, case studies.Transactions of Mathematics and Its Applications, 8(2), 2024

    Nathan E Glatt-Holtz, Andrew J Holbrook, Justin A Krometis, and Cecilia F Mondaini. Parallel MCMC algorithms: theoretical foundations, algorithm design, case studies.Transactions of Mathematics and Its Applications, 8(2), 2024

    2024

  10. [18]

    Reversible Jump Markov Chain Monte Carlo Computation and Bayesian Model Determination.Biometrika, 82(4):711–732, 1995

    Peter J Green. Reversible Jump Markov Chain Monte Carlo Computation and Bayesian Model Determination.Biometrika, 82(4):711–732, 1995

    1995

  11. [19]

    Springer, 1974

    Paul R Halmos.Measure Theory, volume 18. Springer, 1974

    1974

  12. [20]

    W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications.Biometrika, 57(1):97–109, apr 1970

    1970

  13. [21]

    The geometry of tensor calculus, I.Advances in Mathematics, 88(1):55–112, 1991

    André Joyal and Ross Street. The geometry of tensor calculus, I.Advances in Mathematics, 88(1):55–112, 1991

    1991

  14. [22]

    Springer, 3 edition, 2021

    Olav Kallenberg.Foundations of Modern Probability, volume 99 ofProbability Theory and Stochastic Modelling. Springer, 3 edition, 2021

    2021

  15. [23]

    CUP Archive, 1982

    Gregory Maxwell Kelly.Basic concepts of enriched category theory, volume 64. CUP Archive, 1982

    1982

  16. [24]

    AutoStep: Locally adaptive involutive MCMC

    Tiange Liu, Nikola Surjanovic, Miguel Biron-Lattes, Alexandre Bouchard-Côté, and Trevor Campbell. AutoStep: Locally adaptive involutive MCMC. 2024

    2024

  17. [25]

    Springer Science & Business Media, 1998

    Saunders Mac Lane.Categories for the working mathematician, volume 5. Springer Science & Business Media, 1998

    1998

  18. [26]

    Rosenbluth, Marshall N

    Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of State Calculations by Fast Computing Machines.The Journal of Chemical Physics, 21(6):1087–1092, 1953

    1953

  19. [27]

    A category-theoretic proof of the ergodic de- composition theorem.Ergodic Theory and Dynamical Systems, 43(12):4166–4192, 2023

    Sean Moss and Paolo Perrone. A category-theoretic proof of the ergodic de- composition theorem.Ergodic Theory and Dynamical Systems, 43(12):4166–4192, 2023

    2023

  20. [28]

    MCMC for doubly- intractable distributions

    Iain Murray, Zoubin Ghahramani, and David MacKay. MCMC for doubly- intractable distributions. InProceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, UAI 2006, pages 359–366, 2012

    2006

  21. [29]

    Involutive MCMC: a Unifying Framework

    Kirill Neklyudov, Max Welling, Evgenii Egorov, and Dmitry Vetrov. Involutive MCMC: a Unifying Framework. InProceedings of the 37th International Conference on Machine Learning, volume 119, pages 7273–7282. PMLR, 2020

    2020

  22. [30]

    WORLD SCIENTIFIC, October 2023

    Paolo Perrone.Starting Category Theory. WORLD SCIENTIFIC, October 2023

    2023

  23. [31]

    Infinite products and zero-one laws in categorical probability.Compositionality, Volume 2 (2020)(3), 2020

    Eigil Fjeldgren Rischel and Tobias Fritz. Infinite products and zero-one laws in categorical probability.Compositionality, Volume 2 (2020)(3), 2020

    2020

  24. [32]

    Robert and George Casella.Monte Carlo Statistical Methods

    Christian P. Robert and George Casella.Monte Carlo Statistical Methods. Springer Texts in Statistics. Springer New York, New York, NY, second edition, 2004

    2004

  25. [33]

    Eigenvalue analysis of an irreversible random walk with skew detailed balance conditions.Physical Review E, 93(4):3–8, 2016

    Yuji Sakai and Koji Hukushima. Eigenvalue analysis of an irreversible random walk with skew detailed balance conditions.Physical Review E, 93(4):3–8, 2016

    2016

  26. [34]

    A survey of graphical languages for monoidal categories

    Peter Selinger. A survey of graphical languages for monoidal categories. InNew structures for physics, pages 289–355. Springer, 2010

    2010

  27. [35]

    Commutative semantics for probabilistic programming

    Sam Staton. Commutative semantics for probabilistic programming. In H Yang, editor,Programming Languages and Systems, volume 10201 ofLecture Notes in Computer Science, pages 855–879. Springer, Berlin, Heidelberg, 2017

    2017

  28. [36]

    Nonreversible mcmc from conditional invertible transforms: a complete recipe with convergence guarantees, 2021

    Achille Thin, Nikita Kotelevskii, Christophe Andrieu, Alain Durmus, Eric Moulines, and Maxim Panov. Nonreversible mcmc from conditional invertible transforms: a complete recipe with convergence guarantees, 2021

    2021

  29. [37]

    A note on Metropolis-Hastings kernels for general state spaces

    Luke Tierney. A note on Metropolis-Hastings kernels for general state spaces. The Annals of Applied Probability, 8(1):1–9, 1998

    1998

  30. [38]

    Turitsyn, Michael Chertkov, and Marija Vucelja

    Konstantin S. Turitsyn, Michael Chertkov, and Marija Vucelja. Irreversible Monte Carlo algorithms for efficient sampling.Physica D: Nonlinear Phenomena, 240(4-5):410–414, 2011

    2011

  31. [39]

    infinitesimal

    Zuheng Xu and Trevor Campbell. Asymptotically exact variational flows via involutive MCMC kernels. 2025. A Measure theory terminology and notation We include here some basic terminology and notation from measure theory that we use in the paper. Recall that akernelis a function...

    2025

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.