Numerical methods for the self-avoiding walk

In an exact-enumeration study, one first generates a complete list of all SAWs up to a certain length (usually N w 15-35 steps), keeping track of the properties of interest such as the number of such walks or their squared end-to-end distances. One then performs an extrapolation to the limit N - oo, using techniques such as the ratio method. Fade approximants or differential approximants. ° Inherent in any such extrapolation is an assumption about the behavior of the coefficients beyond those actually computed. Sometimes this assumption is fairly explicit other times it is hidden in the details of the extrapolation method. In either case, the assumptions made have a profound effect on the numerical results obtained. For this reason, the claimed error bars in exact-enumeration/extrapolation studies should be viewed with a healthy skepticism. 

In a Monte Carlo study, by contrast, one aims to probe directly the regime of fairly long SAWs (usually N m 10 -10 steps). Complete enumeration is unfeasible, so one generates instead a random sample. The raw data then contain statistical errors, just as in a laboratory experiment. These errors can, however, be estimated—sometimes even a priori (see Section 2.7.3)— and they can in principle be reduced to an arbitrarily low level by the use of sufficient computer time. An extrapolation to the regime of extremely long SAWs is still required, but this extrapolation is much less severe than in the case of exact-enumeration studies, because the point of departure is already much closer to the asymptotic regime. 

A -step SAW. This rapid growth with N of the autocorrelation time—called critical slowing-down —made it difficult in practice to do high-precision simulations with N greater than about 30-100. 

The purpose of this chapter is thus to give a comprehensive overview of Monte Carlo methods for the self-avoiding walk, with emphasis on the extraordinarily efficient algorithms developed since 1981.1 shall also discuss briefly some of the physical results which have been obtained from this work. 

---