# Beyond Reweighting: Certified Improvements from New Transitions in Discrete MCMC

DevFeed: [Beyond Reweighting: Certified Improvements from New Transitions in Discrete MCMC](<https://devfeed.tech/articles/beyond-reweighting-certified-improvements-from-new-transitions-in-discrete-mcmc-133022.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.15668>)

Author: Yishan Xi, Tinglan Wang

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>)

Tags: [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [improvements](<https://devfeed.tech/tags/improvements.md>), [mcmc](<https://devfeed.tech/tags/mcmc.md>), [support](<https://devfeed.tech/tags/support.md>), [variance](<https://devfeed.tech/tags/variance.md>)

## AI overview

For reversible MCMC on a fixed target, adding allowed transitions can improve asymptotic variance beyond what reweighting existing transitions can achieve. The paper gives a necessary and sufficient dual condition and computable primal-dual certificates for proving strict improvement under a node-flow budget. It also constructs a case where one added edge cuts integrated autocorrelation time by an Ω(n) factor relative to optimal weighting on the original support. Experiments distinguish support quality from kernel construction: on augmented Ising supports, full weight optimization certified improvements in 24 of 24 conditions, while degree-based Metropolis-Hastings weighting certified none. The abstract also reports energy-informed edge selection and constrained stationary-flow optimization, but gives no further experimental details.

## Source excerpt

arXiv:2611.15668v1 Announce Type: new 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 $\Omega(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.