pith. sign in

arxiv: 1907.00779 · v1 · pith:ARGAFD44new · submitted 2019-06-28 · 🧮 math.PR · math.ST· stat.TH

Constrained Monte Carlo Markov Chains on Graphs

Roy Cerqueti , Emilio De Santis This is my paper

Pith reviewed 2026-05-25 13:38 UTC · model grok-4.3

classification 🧮 math.PR math.STstat.TH
keywords Markov chainsMonte Carlo samplinggraphsempirical convergencetarget distributionsupportconnectedness
0
0 comments X

The pith

A Markov chain on a graph can be built so its visits converge in frequency to any target distribution whose support the graph can reach.

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

The paper constructs a Markov chain whose states are vertices of a given graph and whose transitions are allowed only along the graph's edges. The chain is tuned so that the long-run fraction of time spent at each vertex matches the probabilities in a chosen reference distribution. The construction succeeds precisely when the graph's connectedness properties line up with the states that carry positive mass in the reference distribution. The argument therefore reduces to relating the support of the target measure to the connected components of the graph. This yields a sampling procedure that respects hard structural constraints while still guaranteeing the desired stationary frequencies.

Core claim

The paper establishes that, given any reference probability distribution on a finite set and any undirected graph on the same vertex set, a transition kernel supported only on the edges of the graph can be chosen so that the resulting Markov chain is ergodic on the support of the reference distribution and therefore has that distribution as its unique invariant measure; the empirical occupation measure of the chain then converges to the reference distribution almost surely.

What carries the argument

The graph-constrained transition kernel whose positive entries are restricted to the edges and whose invariant measure is forced to equal the given reference distribution whenever the graph connects the support.

If this is right

  • Standard ergodicity theorems apply directly once the chain is irreducible on the target's support.
  • The same construction works for any finite undirected graph whose adjacency relation respects the support.
  • Convergence of the empirical distribution holds almost surely along almost every trajectory of the chain.
  • The procedure yields a valid Monte Carlo sampler under arbitrary forbidden-transition constraints.
  • The required transition probabilities can be chosen explicitly from the target masses and the edge set.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result immediately supplies a sampler for distributions on networks when only certain state changes are physically allowed.
  • One could test the construction on small complete graphs versus path graphs to see how the mixing time scales with the target's support size.
  • The same support-connectedness condition may extend to directed graphs or to graphs that change slowly over time.
  • Sampling algorithms in graphical models could adopt this kernel when the model graph and the constraint graph coincide.

Load-bearing premise

The graph must connect every pair of states that both receive positive probability under the target distribution.

What would settle it

Take a target distribution with positive mass on two states that lie in different connected components of the graph and verify that no transition matrix supported only on the existing edges can make the chain visit both states with the required long-run frequencies.

read the original abstract

This paper presents a novel theoretical Monte Carlo Markov chain procedure in the framework of graphs. It specifically deals with the construction of a Markov chain whose empirical distribution converges to a given reference one. The Markov chain is constrained over an underlying graph, so that states are viewed as vertices and the transition between two states can have positive probability only in presence of an edge connecting them. The analysis is carried out on the basis of the relationship between the support of the target distribution and the connectedness of the graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to construct a Markov chain on the vertices of a graph, with transitions permitted only along edges, such that the chain's empirical distribution converges to an arbitrary target reference distribution on those vertices. The argument is said to rest on the relationship between the support of the target measure and the connectedness properties of the graph.

Significance. If the construction is carried out explicitly and the convergence is proved, the work would amount to a graph-theoretic restatement of the standard ergodic theorem for finite-state irreducible aperiodic Markov chains. No machine-checked proofs, reproducible code, or falsifiable predictions are mentioned, so the significance is limited to possible pedagogical value in constrained sampling settings.

major comments (1)
  1. [Abstract] No explicit transition matrix, proposal kernel, or acceptance probabilities are supplied in the provided text, so it is impossible to verify that the constructed chain is irreducible and aperiodic precisely on the support of the target (the only condition needed for the ergodic theorem to apply).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] No explicit transition matrix, proposal kernel, or acceptance probabilities are supplied in the provided text, so it is impossible to verify that the constructed chain is irreducible and aperiodic precisely on the support of the target (the only condition needed for the ergodic theorem to apply).

    Authors: The manuscript establishes a general theoretical procedure for constructing a graph-constrained Markov chain whose stationary distribution matches an arbitrary target, with convergence guaranteed precisely when the support of the target is connected in the graph. This relationship directly implies the required irreducibility (and, with standard aperiodicity adjustments, ergodicity) on the support without needing a single fixed transition matrix for all graphs. The full text derives the existence of suitable transition probabilities from the connectedness assumption rather than exhibiting one universal kernel. We agree that an illustrative explicit construction on a small graph would strengthen verifiability and will add one in a revised version. revision: partial

Circularity Check

0 steps flagged

No circularity; standard ergodic convergence on graph support

full rationale

The paper constructs a Markov chain on a graph whose stationary distribution matches a target, with the key condition being that the graph's connectedness contains the target's support. This is the minimal irreducibility requirement for the ergodic theorem to guarantee convergence of empirical averages; the abstract explicitly frames the analysis as resting on this relationship, which is a classical external fact rather than a self-referential definition or fitted input. No equations, self-citations, or ansatzes are visible that reduce the claim to its own inputs by construction. The derivation is self-contained against standard Markov chain theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the existence of transition probabilities that respect the graph edges while achieving the target stationary distribution; this implicitly uses standard Markov chain theory.

axioms (1)
  • standard math Standard Markov chain convergence theorems (irreducibility and aperiodicity imply convergence to unique stationary distribution) apply once the graph allows the required transitions.
    The paper's analysis hinges on the support-connectedness relationship, which presupposes these classical conditions.

pith-pipeline@v0.9.0 · 5597 in / 1092 out tokens · 26081 ms · 2026-05-25T13:38:12.378149+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Baldi, A

    P. Baldi, A. Frigessi, and M. Piccioni. Importance sampling for Gibbs random fields. Ann. Appl. Probab., 3(3):914–933, 1993

    work page 1993

  2. [2]

    Bartolucci, L

    F. Bartolucci, L. Scaccia, and A. Mira. Efficient Bayes factor est imation from the reversible jump output. Biometrika, 93(1):41–52, 2006

    work page 2006

  3. [3]

    Beltr´ an and C

    J. Beltr´ an and C. Landim. Tunneling and metastability of continuo us time Markov chains. J. Stat. Phys., 140(6):1065–1114, 2010

    work page 2010

  4. [4]

    Br´ emaud

    P. Br´ emaud. Markov chains , volume 31 of Texts in Applied Mathematics . Springer-Verlag, New York, 1999. Gibbs fields, Monte Carlo simulation, and queues

    work page 1999

  5. [5]

    Brooks, A

    S. Brooks, A. Gelman, G. L. Jones, and X.-L. Meng, editors. Handbook of Markov chain Monte Carlo. Chapman & Hall/CRC Handbooks of Modern Statistical Methods. CR C Press, Boca Raton, FL, 2011

    work page 2011

  6. [6]

    B. P. Carlin and S. Chib. Bayesian model choice via Markov chain Mon te Carlo methods. J. R. Stat. Soc. Series B

    work page

  7. [7]

    Cerqueti and E

    R. Cerqueti and E. De Santis. Stochastic Ising model with flipping sets of spins and fast decreasing temperature. Ann. Inst. Henri Poincar´ e Probab. Stat., 54(2):757–789, 2018

    work page 2018

  8. [8]

    D. J. Daley. Stochastically monotone Markov chains. Z. Wahrscheinlichkeitstheorie und Verw. Ge- biete, 10:305–317, 1968

    work page 1968

  9. [9]

    De Santis and A

    E. De Santis and A. Lissandrelli. Developments in perfect simulation of Gibbs measures through a new result for the extinction of Galton-Watson-like processes. J. Stat. Phys. , 147(2):231–251, 2012

    work page 2012

  10. [10]

    Diaconis

    P. Diaconis. The Markov chain Monte Carlo revolution. Bull. Amer. Math. Soc. (N.S.) , 46(2):179– 205, 2009

    work page 2009

  11. [11]

    Diaconis

    P. Diaconis. Some things we’ve learned (about Markov chain Mont e Carlo). Bernoulli, 19(4):1294– 1305, 2013

    work page 2013

  12. [12]

    Dobrushin

    R. Dobrushin. Central limit theorem for non-stationary Marko v chains. I. Teor. Veroyatnost. i Primenen., 1:72–89, 1956

    work page 1956

  13. [13]

    Fearnhead

    P. Fearnhead. Markov chain Monte Carlo, sufficient statistics, and particle filters. J. Comput. Graph. Statist. , 11(4):848–862, 2002

    work page 2002

  14. [14]

    J. A. Fill and J. Kahn. Comparison inequalities and fastest-mixing Markov chains. Ann. Appl. Probab., 23(5):1778–1816, 2013

    work page 2013

  15. [15]

    Frigessi, P

    A. Frigessi, P. di Stefano, C.-R. Hwang, and S. J. Sheu. Conve rgence rates of the Gibbs sampler, the Metropolis algorithm and other single-site updating dynamics. J. Roy. Statist. Soc. Ser. B , 55(1):205–219, 1993

    work page 1993

  16. [16]

    Frigessi, F

    A. Frigessi, F. Martinelli, and J. Stander. Computational comple xity of Markov chain Monte Carlo methods for finite Markov random fields. Biometrika, 84(1):1–18, 1997. CONSTRAINED MONTE CARLO MARKOV CHAINS ON GRAPHS 15

    work page 1997

  17. [17]

    Geman and D

    S. Geman and D. Geman. Stochastic relaxation, Gibbs distributio ns, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intellig ence, PAMI(6):721–741, 1984

    work page 1984

  18. [18]

    P. J. Green. Reversible jump Markov chain Monte Carlo computa tion and Bayesian model deter- mination. Biometrika, 82(4):711–732, 1995

    work page 1995

  19. [19]

    W. K. Hastings. Monte Carlo sampling methods using Markov chain s and their applications. Biometrika, 57:97–109, 1970

    work page 1970

  20. [20]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi. Optimization b y simulated annealing. Science, 220(4598):671–680, 1983

    work page 1983

  21. [21]

    Landim, M

    C. Landim, M. Loulakis, and M. Mourragui. Metastable Markov ch ains: from the convergence of the trace to the convergence of the finite-dimensional distributio ns. Electron. J. Probab., 23:Paper No. 95, 34, 2018

    work page 2018

  22. [22]

    Lindvall

    T. Lindvall. Lectures on the coupling method . Wiley Series in Probability and Mathematical Sta- tistics: Probability and Mathematical Statistics. John Wiley & Sons, I nc., New York, 1992. A Wiley-Interscience Publication

    work page 1992

  23. [23]

    Metropolis, A

    N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics , 21(6):1087–1092, 1953

    work page 1953

  24. [24]

    J. G. Propp and D. B. Wilson. Exact sampling with coupled Markov c hains and applications to statistical mechanics. In Proceedings of the Seventh International Conference on Ran dom Structures and Algorithms (Atlanta, GA, 1995) , volume 9, pages 223–252, 1996

    work page 1995

  25. [25]

    Sabidussi

    G. Sabidussi. Graph multiplication. Math. Z. , 72:446–457, 1959/1960

    work page 1959

  26. [26]

    L. Tierney. Markov chains for exploring posterior distributions . Ann. Stat. , 22(4):1701–1762, 1994. University of Macerata, Department of Economics and Law. Vi a Crescimbeni 20, I-62100, Macerata, Italy E-mail address : roy.cerqueti@unimc.it University of Rome La Sapienza, Department of Mathematics. Piazzale Aldo Moro, 5, I-00185, Rome, Italy E-mail add...

    work page 1994