arXiv:1608.05899

A method to reduce the rejection rate in Monte Carlo Markov Chains on Ising spin models

Carlo Baldassi

Published Aug 21, 2016• 1 citation

Abstract

We present a method for Monte Carlo sampling on Ising spin systems, introducing a prior on the candidate moves in a Metropolis-Hastings scheme which can significantly reduce the rejection rate. The method can be regarded as an modification of the rejection-free method of Bortz, Kalos and Lebowitz (BKL) [Bortz et al. 1975], which was developed under two assumptions: i) low connectivity, and ii) that the energy shift induced by flipping one spin can only assume a small number of values. Our method employs the same probability distribution for the choice of the moves as BKL, but 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; moreover, it is easily extensible to more general situations which cannot be treated with the BKL method, in particular when the energy of the system can be written as the sum of two components, only one of which satisfies the assumptions at the basis of the BKL method. We provide two families of examples of such situations: graphs with heterogeneous continuous-valued couplings, and Monte Carlo simulations of quantum spin models in presence of a transverse field in the Suzuki-Trotter formalism. Our code is publicly available [this https URL], and extensible to user-defined models.

Related papers

Collective Monte Carlo updates through tensor network renormalization

Miguel Frías-Pérez, Michael Mariën, David Pérez-Garcı́a +2 more

We introduce a Metropolis-Hastings Markov chain for Boltzmann distributions of classical spin systems. It relies on approximate tensor network contractions to propose correlated collective updates at each step of the evolution. We present benchmark computations for a wide variety of instances of the two-dimensional Ising model, including ferromagnetic, antiferromagnetic, (fully) frustrated and Edwards-Anderson spin glass instances, and we show that, with modest computational effort, our Markov chain achieves sizeable acceptance rates, even in the vicinity of critical points. In each of the situations we have considered, the Markov chain compares well with other Monte Carlo schemes such as the Metropolis or Wolff’s algorithm: equilibration times appear to be reduced by a factor that varies between 40 40 and 2000 2000 , depending on the model and the observable being monitored. We also present an extension to three spatial dimensions, and demonstrate that it exhibits fast equilibration for finite ferro- and antiferromagnetic instances. Additionally, and although it is originally designed for a square lattice of finite degrees of freedom with open boundary conditions, the proposed scheme can be used as such, or with slight modifications, to study triangular lattices, systems with continuous degrees of freedom, matrix models, a confined gas of hard spheres, or to deal with arbitrary boundary conditions.

SciPost PhysicsMay 22, 202311 citations

Collective Monte Carlo updates through tensor network renormalization

Miguel Frías-Pérez, Michael Mariën, David Pérez García +2 more

We introduce a Metropolis-Hastings Markov chain for Boltzmann distributions of classical spin systems. It relies on approximate tensor network contractions to propose correlated collective updates at each step of the evolution. We present benchmarks for a wide variety of instances of the two-dimensional Ising model, including ferromagnetic, antiferromagnetic, (fully) frustrated and Edwards-Anderson spin glass cases, and we show that, with modest computational effort, our Markov chain achieves sizeable acceptance rates, even in the vicinity of critical points. In each of the situations we have considered, the Markov chain compares well with other Monte Carlo schemes such as the Metropolis or Wolff algorithm: equilibration times appear to be reduced by a factor that varies between 40 and 2000, depending on the model and the observable being monitored. We also present an extension to three spatial dimensions, and demonstrate that it exhibits fast equilibration for finite ferro and antiferromagnetic instances. Additionally, and although it is originally designed for a square lattice of finite degrees of freedom with open boundary conditions, the proposed scheme can be used as such, or with slight modifications, to study triangular lattices, systems with continuous degrees of freedom, matrix models, a confined gas of hard spheres, or to deal with arbitrary boundary conditions.

arXiv:2104.13264Apr 27, 20211 citation

Markov Chain Monte Carlo Method without Detailed Balance

Hidemaro Suwa, Synge Todo

We present a specific algorithm that generally satisfies the balance condition without imposing the detailed balance in the Markov chain Monte Carlo. In our algorithm, the average rejection rate is minimized, and even reduced to zero in many relevant cases. The absence of the detailed balance also introduces a net stochastic flow in a configuration space, which further boosts up the convergence. We demonstrate that the autocorrelation time of the Potts model becomes more than 6 times shorter than that by the conventional Metropolis algorithm. Based on the same concept, a bounce-free worm algorithm for generic quantum spin models is formulated as well.

arXiv:1007.2262Physical Review LettersSep 17, 2010148 citations

Rejection-free quantum Monte Carlo in continuous time from transition path sampling

Luke Causer, Konstantinos Sfairopoulos, Jamie F. Mair +1 more

Continuous-time quantum Monte Carlo refers to a class of algorithms designed to sample the thermal distribution of a quantum Hamiltonian through exact expansions of the Boltzmann exponential in terms of stochastic trajectories which are periodic in imaginary time. Here, we show that for (sign-problem-free) quantum many-body systems with discrete degrees of freedom—such as spins on a lattice—this sampling can be done in a rejection-free manner using transition path sampling (TPS). The key idea is to converge the trajectory ensemble through updates where one individual degree of freedom is modified across all time while the remaining unaltered ones provide a time-dependent background. The ensuing single-body dynamics provides a way to generate trajectory updates exactly, allowing one to obtain the target ensemble efficiently via rejection-free TPS. We demonstrate our method on the transverse field Ising model in one and two dimensions, and on the quantum triangular plaquette (or Newman-Moore) model. We show that despite large autocorrelation times, our method is able to efficiently recover the respective quantum phase transition of each model. We also discuss the connection to rare event sampling in continuous-time Markov dynamics. Published by the American Physical Society 2024

arXiv:2305.08935Physical review. B./Physical review. BJan 16, 20242 citations

Concentrated Monte Carlo sampling for local observables in quantum spin chains

Wenxuan Zhang, Dingzu Wang, Dario Poletti

Monte Carlo methods are widely used to estimate observables in many-body quantum systems. However, conventional sampling schemes often require a large number of samples to achieve sufficient accuracy. In this work we propose the concentrated Monte Carlo sampling approach, which builds on the idea that in systems with only short range correlations, to obtain accurate expectation values for local observables, one would favor detailed information in the surroundings of this observable compared to far away from it. In this approach we consider all possible configurations in the surroundings of a local observable, and unique samples from the remaining of the setup drawn using Markov chain Monte Carlo. We have tested the performance of this approach for ground states of the spin-1/2 tilted Ising model in different phases, and also for thermal states in the a spin-1 bilinear-biquadratic model. Our results demonstrate that CMCS yields higher accuracy for local observables in short-range correlated states while requiring substantially fewer samples, showcasing in which regimes one can obtain acceleration for the evaluation of expectation values.

quant-pharXiv:2512.05440Dec 8, 20250 citations

Introduction to Monte Carlo methods for an Ising Model of a Ferromagnet

Jacques Kotze

This discussion serves as an introduction to the use of Monte Carlo simulations as a useful way to evaluate the observables of a ferromagnet. Key background is given about the relevance and effectiveness of this stochastic approach and in particular the applicability of the Metropolis-Hastings algorithm. Importantly the potentially devastating effects of spontaneous magnetization are highlighted and a means to avert this is examined. An Ising model is introduced and used to investigate the properties of a two dimensional ferromagnet with respect to its magnetization and energy at varying temperatures. The observables are calculated and a phase transition at a critical temperature is also illustrated and evaluated. Lastly a finite size scaling analysis is undertaken to determine the critical exponents and the Curie temperature is calculated using a ratio of cumulants with differing lattice sizes. The results obtained from the simulation are compared to exact calculations to endorse the validity of this numerical process. A copy of the code used, written in C++, is enclosed and is freely available for use and modification under the General Public License.

arXiv:0803.0217Mar 3, 200816 citations