A method to reduce the rejection rate in Monte Carlo Markov chains

We present a method for Monte Carlo sampling on systems with discrete variables (focusing in the Ising case), introducing a prior on the candidate moves in a Metropolis–Hastings scheme which can significantly reduce the rejection rate, called the reduced-rejection-rate (RRR) method. The method employs same probability distribution for the choice of the moves as rejection-free schemes such as the method proposed by Bortz, Kalos and Lebowitz (BKL) (1975 J. Comput. Phys. 17 10–8); however, it uses it as a prior in an otherwise standard Metropolis scheme: it is thus not fully rejection-free, but in a wide range of scenarios it is nearly so. This allows to extend the method to cases for which rejection-free schemes become inefficient, in particular when the graph connectivity is not sparse, but the energy can nevertheless be expressed as a sum of two components, one of which is computed on a sparse graph and dominates the measure. As examples of such instances, we demonstrate that the method yields excellent results when performing Monte Carlo simulations of quantum spin models in presence of a transverse field in the Suzuki–Trotter formalism, and when exploring the so-called robust ensemble which was recently introduced in Baldassi et al (2016 Proc. Natl Acad. Sci. 113 E7655–62). Our code for the Ising case is publicly available (RRR Monte Carlo code https://github.com/carlobaldassi/RRRMC.jl), and extensible to user-defined models: it provides efficient implementations of standard Metropolis, the RRR method, the BKL method (extended to the case of continuous energy specra), and the waiting time method by Dall and Sibani (2001 Comput. Phys. Commun. 141 260–7).