Nonreversible Markov Chain Monte Carlo Algorithm for Efficient Generation of Self-Avoiding Walks
Zhao, Hanqing, Physics - Graduate School of Arts and Sciences, University of Virginia
Vucelja, Marija, Physics, University of Virginia
A Self-Avioding Walk (SAW) is defined as a contiguous sequence of moves on a lattice that does not cross itself. Typically one uses Monte Carlo approaches to generate SAW numerically. We introduce an efficient nonreversible Markov chain Monte Carlo algorithm to generate self-avoiding walks with a variable endpoint. In two dimensions, the new algorithm slightly outperforms the two-move nonreversible Berretti-Sokal algorithm, while for three-dimensional walks, it is 3--5 times faster. The new algorithm introduces nonreversible Markov chains that obey global balance and allow for three types of elementary moves on the existing self-avoiding walk: shorten, extend or alter conformation without changing the length of the walk.
MS (Master of Science)
nonreversible Markov chains, Markov chain Monte Carlo, Self-avoiding walk