Improving Markov chain sampling by adding new transitions

Beyond Reweighting: Certified Improvements from New Transitions in Discrete MCMC

Machine Learning

Summary

Markov chain Monte Carlo (MCMC) methods are used to estimate probabilities by randomly moving through possible states, but their speed depends on how they jump between states. The authors show that simply adjusting jump probabilities on an existing network of states is often not enough to make sampling faster. They develop a way to identify when adding new possible jumps (transitions) can drastically improve efficiency and prove how to certify these improvements. Their tests on models like molecules and magnets demonstrate that adding certain transitions can cut down waiting times, making estimates more accurate.

What this means in practice

  • For statistical modelers: Design transition supports in MCMC algorithms to drastically reduce estimation time by adding strategic new state transitions.
  • For computational chemists: Improve molecular simulations by augmenting state graphs with additional transitions that certify better mixing and sampling efficiency.

Authors

Yishan Xi, Tinglan Wang

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)$ 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.