A categorical account of the Metropolis–Hastings algorithm

Rob Cornish, Andi Q. Wang · 2026

Read A categorical account of the Metropolis–Hastings algorithm by Rob Cornish, Andi Q. Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22911.txt.

Introduction

Rob Cornish and Andi Q. Wang recast a cornerstone sampling algorithm in the language of category theory. The algorithm, Metropolis–Hastings, builds a Markov chain whose long-run pattern matches a target distribution. It underlies much of Bayesian statistics and machine learning.

The authors ask whether the method can be stated and analyzed with categorical probability, a newer formal framework. They test the idea on a recent involutive version of the algorithm. A clean abstract form could reveal which parts of the method are essential, and guide new variants. Using a recent involutive variant as the case study keeps the categorical treatment concrete rather than purely abstract.

Catalog record

CREATORRob Cornish, Andi Q. Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22911

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A categorical account of the Metropolis–Hastings algorithm Rob Cornish, Andi Q. Wang 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. 1. Introduction Markov kernels are a fundamental concept in probability theory. Recall that a Markov kernel P:\mathcal{X}\to\mathcal{Y} encodes a family of probability distributions P(x,\mathrm{d}y) on the space \mathcal{Y} indexed by points x\in\mathcal{X} . Recent work on copy-discard (CD) categories and Markov categories ( Cho2019 ; Fritz2020 ) has sought to develop a synthetic framework for reasoning about systems of Markov kernels and their unnormalised counterparts algebraically. This approach has been applied successfully to a number of classical results from probability and statistics, yielding streamlined and more conceptual proofs than traditional measure-theoretic arguments ( Fritz2021 ; Rischel2020 ; Fritz2020 ; Moss2023 ) . In applied settings, Markov kernels are often regarded as “stochastic functions” and used to model conditional probability distributions , which in turn have a huge number of applications in computational statistics, machine learning, and computer science generally. It is therefore natural to ask: to what extent are Markov and CD categories ready for reasoning about contemporary methodology in these domains? Are they usable “as-is”, or are additional structures or concepts needed to handle the complexities of modern algorithms? We consider this question in the context of Markov chain Monte Carlo (MCMC) methods, and specifically the Metropolis–Hastings (MH) algorithm ( metropolis1953equation ; Hastings1970 ) , which is a foundational tool for sampling from complex probability distributions. We focus on a recent line of work which studies MH through the lens of involutions ( Neklyudov2020 ; Andrieu2020 ; Glatt-Holtz2023 ; Glatt-Holtz2024 ; cusumano2020automating ) , building on earlier foundational work ( Tierney1998 ; Green1995 ) . This perspective has already lead to a range of new methodology of interest to computational statistics practitioners ( Bou-Rabee2024 ; Liu2024 ; Xu2025 ) . A major contribution to the involutive approach is the framework of ( Andrieu2020 ) . This considers a Markov kernel \Pi_{\mathrm{MH}}:\mathcal{E}\to\mathcal{E} defined (1) \Pi_{\mathrm{MH}}(\xi,\mathrm{d}\xi^{\prime})\coloneqq\alpha(\xi)\,\delta_{\phi(\xi)}(\mathrm{d}\xi^{\prime})+(1-\alpha(\xi))\,\delta_{\xi}(\mathrm{d}\xi^{\prime}), where \alpha:\mathcal{E}\to[0,1] is a measurable function regarded as an acceptance probability , \phi:\mathcal{E}\to\mathcal{E} is a measurable involution (i.e. \phi=\phi^{-1} ), and \delta is the Dirac delta. Intuitively, given an input \xi , this kernel transitions to \phi(\xi) with probability \alpha(\xi) , and otherwise remains at \xi . By combining \Pi_{\mathrm{MH}} with a suitable state-space augmentation (see Section 2.4 ), it is shown in ( Andrieu2020 ) that a very wide variety of MH-type algorithms can be recovered as special cases (see also Appendix B for two examples). The main theoretical result of ( Andrieu2020 ) is their Theorem 3, which gives sufficient conditions under which \Pi_{\mathrm{MH}} is reversible with respect to a given target distribution. Reversibility in turn constitutes a key correctness guarantee for many MCMC algorithms. We state a summarised version of this result as follows (see Appendix A for our measure theory terminology and notation): Theorem 1.1. Suppose \mu is a finite measure on a measurable space \mathcal{E} , and \phi:\mathcal{E}\to\mathcal{E} is a measurable involution. Then there exists a measurable S\subseteq\mathcal{E} such that the restriction \mu|_{S} and its pushforward \mu|_{S}^{\phi} are equivalent as measures, and \mu|_{S^{c}} and its pushforward \mu|_{S^{c}}^{\phi} are singular. The kernel \Pi_{\mathrm{MH}} ( 1 ) above is then \mu|_{S} -reversible if (2) \alpha(\xi)=\begin{cases}\alpha(\phi(\xi))\,r(\xi)&\text{if $\xi\in S$,}\\ 0&\text{otherwise}.\end{cases} where r\coloneqq\frac{\mathrm{d}\mu|_{S}^{\phi}}{\mathrm{d}\mu|_{S}} denotes the Radon–Nikodym derivative. Summary of main results Given the important implications of Theorem 1.1 for MH-type procedures, it serves as a natural test case for the applicability of categorical probability. Our goal in this paper is to obtain this result synthetically using Markov and CD categories. For this, we find that three levels of structure are needed: • In Section 2 , we use Markov categories to formulate generic aspects of MCMC algorithms, such as invariance, reversibility and state-space augmentation. • In Section 3 , we use CD categories to reason about the first summand in ( 1 ): we prove reversibility of this term, and recover part of the condition ( 2 ). • However, to study the entire kernel \Pi_{\mathrm{MH}} , we need additional structure: for example, we need a way to “add” morphisms, and we need a way to reason about decompositions of morphisms into disjoint “parts”. In Section 4 , we therefore consider an enriched extension of CD categories. This allows us to provide a synthetic generalisation of Theorem 1.1 in the form of Theorems 4.27 and 4.43 below. The appendix contains some additional background and proofs, as well as two additional examples of MCMC-related techniques (the systematic-scan Gibbs sampler, and importance sampling) within categorical probability, which may be of interest to practitioners. We believe these results are interesting in their own right, as they involve arguments that are both more conceptual and more general than their measure-theoretic counterparts. We also hope our work illustrates how categorical tools may be used to analyse contemporary methodology in computational statistics more generally. Technical contributions In order to consider the full MH kernel \Pi_{\mathrm{MH}} , we study CD categories enriched over commutative monoids, which provides a minimal structure for reasoning about addition of morphisms. This enrichment is expressive, and permits formulating and proving results about abstract versions of the following important concepts from measure theory: • Substochastic kernels and probabilities (i.e. values in [0,1] ). • Finite and \sigma -finite kernels. • Pointwise absolute continuity between kernels. • Singular measures and Lebesgue decompositions . The enrichment combines well with string diagrams, allowing for straightforward graphical reasoning. It also integrates naturally with existing categorical approaches to probabilistic choice: when suitable coproducts exist, the subcategory of normalised morphisms carries the structure of a distributive Markov category ( ackerman2024probabilistic ) , relating our “algebraic” treatment of convex combinations to the “sampling” perspective. Importantly, we show that these tools are not merely descriptive, but may be used to obtain interesting results about probabilistic concepts. In the context of Theorem 1.1 , this enrichment allows us to reason about decompositions of \mu into parts supported on S and S^{c} , and to obtain the condition ( 2 ) via purely algebraic arguments. It also supplies a converse to Theorem 1.1 , which was not given in ( Andrieu2020 ) , and permits a straightforward extension to the historically more complex skew-reversible setting (Corollary 4.29 ). We believe these results suggest this enrichment may be useful in applications beyond MCMC also. 2. MCMC foundations in Markov categories 2.1. Recap: Markov categories We first recall the fundamentals of Markov

Read the complete text