Introduction
The Metropolis algorithm is a cornerstone of Markov Chain Monte Carlo (MCMC) methods. In practical applications, such as training Restricted Boltzmann Machines or simulating Ising models, variables are often updated in a fixed, deterministic order (a "fixed scan") rather than a random one. While computationally efficient, fixed-order updates for multivariate binary distributions can lead to a lack of ergodicity, where the Markov chain becomes reducible and fails to converge to the target distribution. This paper addresses this theoretical gap by proposing a simple modification to the Metropolis transition operator.
The Modified Metropolis Operator
The standard Metropolis algorithm for binary variables accepts a proposed state flip with probability 1 if the new state is more or equally probable. The authors identify that the deterministic acceptance of equally probable states is the root cause of reducibility in fixed-order scans. They propose a modified operator:
- If the proposed state is more probable, accept with probability 1.
- If the proposed state is less probable, accept with the standard probability ratio.
- If the proposed state has the exact same probability, accept with a probability of 0.5.
By introducing this stochasticity for equal-probability transitions, the authors use graph theory to prove that the resulting Markov chain is irreducible and aperiodic for any multivariate binary distribution, regardless of the update order. This seemingly minor change allows the Markov chain to occasionally stay in its current state, breaking the deterministic loops that plague the standard algorithm.
Empirical Evaluation and Results
The authors evaluate the algorithm using $3 \times 3$ ferromagnetic Ising models, comparing the spectral gaps of Gibbs sampling, standard Metropolis, and the modified Metropolis algorithm. The spectral gap is a direct measure of convergence speed; a gap of zero indicates a failure to converge.
As shown in the results, the standard Metropolis algorithm fails completely (spectral gap = 0) on the periodic Ising model due to the "equal probability trap." The modified algorithm, however, ensures convergence across all tested scenarios. In cases where the standard algorithm does converge (e.g., non-periodic boundaries), the modified version maintains comparable performance, even outperforming standard Metropolis at moderate coupling strengths ($J$).
Conclusion
This work provides a robust theoretical foundation for fixed-order Metropolis updates in binary systems. The proposed modification is computationally trivial to implement and guarantees convergence without sacrificing the efficiency of fixed scans. The authors suggest this modified operator should become the standard implementation for Metropolis MCMC in multivariate binary settings, closing a long-standing gap between MCMC theory and practice.
Summary updated