Generating self avoiding walks by Markov dependent elongations

Generation of long self-avoiding walks (SAW) is still a difficult problem, because any loops in the walk must be checked and avoided. When self-avoiding walks are sampled on lattice model by elongating the walk into randomly selected free (not already occupied by a segment of the walk) sites, the efficiency is improved but some chains are extremely oversampled. We have been investigating a very simple method to solve this problem. In this method, successive elongations of the walk follow an order k Markov model, defined in such a way that final emission rates of various walk configurations are as equal as possible. Markov model can prohibit some transitions corresponding to short loops, though long loops must be checked by conventional method. Since Markov dependence will be forgotten after k elongations, no net bias is caused on resultant walk configurations. This is the first method proposed for SAW oversampling that uses neither of recursive adjustments nor ordinary MCMC.