Abstract
Markov Chain Monte Carlo (MCMC) methods are fundamental to sampling from complex probability distributions. In practice, fixed-order updates are often preferred for their computational efficiency. However, for multivariate binary distributions, this approach can result in reducible Markov chains that fail to converge. This paper introduces a modified Metropolis transition operator that incorporates a stochastic tie-breaker—flipping bits with probability 0.5 when state probabilities are equal. We prove that this modification guarantees ergodicity for all multivariate binary distributions, bridging a significant gap between MCMC theory and practice.
The Challenge of Fixed-Order Updates
The Metropolis algorithm is a workhorse of statistical computing. While random-order updates are theoretically robust, fixed-order updates (e.g., sequential scanning of variables) are frequently used in large-scale applications like neural networks and Ising models because they often exhibit faster convergence and better cache locality.
Despite their popularity, fixed-order updates carry a known risk: for certain binary distributions, the resulting Markov chain may become trapped in a subset of the state space. This lack of irreducibility means the sampler cannot explore the full distribution, leading to biased results. While this issue has been recognized for decades, it is often dismissed in practice as a rare edge case. This research provides a rigorous solution to ensure convergence is always guaranteed.
A Modified Metropolis Operator
The authors identify that the failure of the standard algorithm stems from its deterministic handling of "ties"—situations where the current state $x$ and a proposed state $f_i(x)$ (with the $i$-th bit flipped) have identical probabilities. The standard Metropolis rule typically accepts such flips with probability 1.
The proposed modification is deceptively simple. The new transition operator follows these rules:
- If $p(f_i(x)) > p(x)$, always accept the flip.
- If $p(f_i(x)) < p(x)$, accept with probability $p(f_i(x))/p(x)$.
- If $p(f_i(x)) = p(x)$, accept the flip with probability 0.5.
By allowing the chain to occasionally remain in its current state even when a flip is possible, the rigid, deterministic cycles that cause reducibility are broken.
Theoretical Guarantees and Irreducibility
Using a novel proof strategy based on graph theory and induction, the authors demonstrate that this modified operator ensures the Markov chain is both irreducible and aperiodic for any multivariate binary distribution. This implies that the chain is ergodic and will eventually converge to the target distribution regardless of the starting state.
A key theoretical insight is that the standard algorithm only fails when states differing by a single bit have exactly the same probability. In many real-world models with continuous parameters, this condition occurs with zero probability, explaining why the standard algorithm often works in practice. However, the modified operator provides a universal safety net for all cases.
Numerical Results: Spectral Gap Analysis
To validate the theory, the authors performed numerical experiments on $3 \times 3$ ferromagnetic Ising models. They calculated the spectral gap of the transition matrix, a metric where a value of 0 indicates a failure to converge and higher values indicate faster convergence.
The results confirm that in scenarios where the standard algorithm's spectral gap is zero (indicating non-convergence), the modified algorithm maintains a positive spectral gap. Furthermore, when both algorithms converge, the modified version performs comparably to or slightly better than the standard one. The study also compared the modified Metropolis operator to Gibbs sampling, finding that Metropolis can be more efficient at medium coupling strengths.
Conclusion
This work provides a definitive theoretical foundation for using fixed-order updates in multivariate binary distributions. By implementing a simple stochastic tie-breaker, researchers can enjoy the efficiency of fixed-order scanning without risking non-convergence. Given that this modification carries no performance penalty and offers a universal convergence guarantee, it represents a significant improvement for MCMC practitioners working with Ising models, Boltzmann machines, and related architectures.
Summary updated