An optimal algorithm to generate extendable self-avoiding walks in arbitrary dimension

A self-avoiding walk (SAW) is extendable [Grimmett, G. R., A. E. Holroyd and Y. Peres, Extendable Self-Avoiding Walks, Ann. Inst. Henri Poincaré Comb. Phys. Interact., 1 (2014), pp. 61-75, Kremer, K. and J. W. Lyklema, Indefinitely growing self-avoiding walk, Phys. Rev. Lett. 54 (1985), pp. 267-269] if it can be extended into an infinite SAW. We give a simple proof that, for every lattice, extendable SAWs admit the same connective constant as the general SAWs and we give an optimal linear algorithm to generate random extendable SAWs. Our algorithm can generate every extendable SAW in dimension 2. For dimension d>2, it generates only a subset of the extendable SAWs. We conjecture that this subset is “large” and has the same connective constant as the extendable SAWs. Our algorithm produces a kinetic distribution of the extendable SAWs, for which the critical exponent ν is such that ν≈.57 for d=2, ν≈.51 for d=3 and ν≈.50 for d=4,5,6. Keywords: self-avoiding walk, connective constant, critical exponent ν, random generation.