cs.LGNov 11, 2026

Beyond Reweighting: Certified Improvements from New Transitions in Discrete MCMC

Authors: Yishan Xi, Tinglan Wang

Organizations: Independent Researcher.

Abstract

Optimizing transition probabilities on a fixed grap may leave substantial limitations on the efficiency of reversible Markov chain Monte Carlo (MCMC). We develop a framework for transition-support design that considers both allowed transitions and their stationary flows. For a fixed target distribution, observable, and node-flow budget, we derive a necessary and sufficient dual condition for support augmentation to strictly reduce the optimal value of the asymptotic variance, together with computable primal--dual certificates that establish improvements over every admissible original-support reweighting. We also construct a family in which adding a single edge reduces integrated autocorrelation time by an Ω(n)Ω(n) factor relative to optimal original-support weighting, demonstrating that structural limitations can impose arbitrarily large relative losses in estimation efficiency. To realize these gains, we investigate energy-informed edge selection and constrained stationary-flow optimization. Experiments on molecular and Ising state graphs distinguish the potential value of new transitions from the performance of kernels constructed on them: on identical augmented Ising supports, full weight optimization certifies strict improvements in 24/24 conditions, whereas degree-based Metropolis--Hastings weighting certifies none. Our results provide a principled approach to characterizing, certifying, and exploiting transition-support improvements in explicitly represented finite state spaces.

Figures & tables

Appendix figures & tables37 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Transformed Samplers with Variance Reduction

    Oct 7, 2026Siran Liu, Michalis Tisias, Petros DellaportasMarkov Chain Monte CarloVariance Reduction

  2. Non-Vacuous Certification of Transport MCMC via Oscillation-Controlled Normalizing Flows

    May 31, 2026Jun HuMarkov Chain Monte CarloNormalizing Flows