DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.32

A Categorical Account of the Metropolis-Hastings Algorithm

Authors: Rob Cornish and Andi Q. Wang

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

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 σ-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.

Cite as

Rob Cornish and Andi Q. Wang. A Categorical Account of the Metropolis-Hastings Algorithm. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 32:1-32:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cornish_et_al:LIPIcs.LICS.2026.32,
  author =	{Cornish, Rob and Wang, Andi Q.},
  title =	{{A Categorical Account of the Metropolis-Hastings Algorithm}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{32:1--32:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.32},
  URN =		{urn:nbn:de:0030-drops-268195},
  doi =		{10.4230/LIPIcs.LICS.2026.32},
  annote =	{Keywords: Categorical probability, Metropolis-Hastings, Markov category, CD category}
}

Search Results

Documents authored by Cornish, Rob

A Categorical Account of the Metropolis-Hastings Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message