Nonlocal Monte Carlo algorithm for self-avoiding walks with fixed endpoints

We study a new Monte Carlo algorithm for generating self-avoiding walks with variable length (controlled by a fugacity) and fixed endpoints. The algorithm is a hybrid of local (BFACF) and nonlocal (cut-and-paste) moves. We find that the critical slowing-down, measured in units of computer time, is reduced compared to the pure BFACF algorithm: _CPU N^2.3 versus N^3.0. We also prove some rigorous bounds on the autocorrelation time for these and related Monte Carlo algorithms.     

Monte Carlo generation of self-avoiding walks with fixed endpoints and fixed length

We propose a new class of dynamic Monte Carlo algorithms for generating self-avoiding walks uniformly from the ensemble with fixed endpoints and fixed length in any dimension, and prove that these algorithms are ergodic in all cases. We also prove the ergodicity of a variant of the pivot algorithm.     

Dynamic critical exponent of the BFACF algorithm for self-avoiding walks

We study the dynamic critical behavior of the BFACF algorithm for generating self-avoiding walks with variable length and fixed endpoints. We argue theoretically, and confirm by Monte Carlo simulations in dimensions 2, 3, and 4, that the autocorrelation time scales as _int,N R~⁴R~N> ^4v .This paper is dedicated to our friend and colleague Jerry Percus on the occasion of his 65th birthday.     

The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk

The pivot algorithm is a dynamic Monte Carlo algorithm, first invented by Lal, which generates self-avoiding walks (SAWs) in a canonical (fixed-N) ensemble with free endpoints (hereN is the number of steps in the walk). We find that the pivot algorithm is extraordinarily efficient: one effectively independent sample can be produced in a computer time of orderN. This paper is a comprehensive study of the pivot algorithm, including: a heuristic and numerical analysis of the acceptance fraction and autocorrelation time; an exact analysis of the pivot algorithm for ordinary random walk; a discussion of data structures and computational complexity; a rigorous proof of ergodicity; and numerical results on self-avoiding walks in two and three dimensions. Our estimates for critical exponents are=0.7496±0.0007 ind=2 and= 0.592±0.003 ind=3 (95% confidence limits), based on SAWs of lengths 200N10000 and 200N 3000, respectively.     

Critical exponents,hyperscaling, and universal amplitude ratios for two- and three-dimensional self-avoiding walks

We make a high-precision Monte Carlo study of two- and three-dimensional self-avoiding walks (SAWs) of length up to 80,000 steps, using the pivot algorithm and the Karp-Luby algorithm. We study the critical exponentsv and 2 ₄ – as well as several universal amplitude ratios; in particular, we make an extremely sensitive test of the hyperscaling relationdv = 2 ₄ –. In two dimensions, we confirm the predicted exponentv=3/4 and the hyperscaling relation; we estimate the universal ratios <R _g ² >/<R _e ² >=0.14026±0.00007, <R _m ² >/<R _e ² >=0.43961±0.00034, and ^*=0.66296±0.00043 (68% confidence limits). In three dimensions, we estimatev=0.5877±0.0006 with a correctionto-scaling exponent ₁=0.56±0.03 (subjective 68% confidence limits). This value forv agrees excellently with the field-theoretic renormalization-group prediction, but there is some discrepancy for ₁. Earlier Monte Carlo estimates ofv, which were 0.592, are now seen to be biased by corrections to scaling. We estimate the universal ratios <R _g ² >/<R _e ² >=0.1599±0.0002 and ^*=0.2471±0.0003; since ^*>0, hyperscaling holds. The approach to ^* is from above, contrary to the prediction of the two-parameter renormalization-group theory. We critically reexamine this theory, and explain where the error lies. In an appendix, we prove rigorously (modulo some standard scaling assumptions) the hyperscaling relationdv = 2 ₄ – for two-dimensional SAWs.     

New Monte Carlo method for the self-avoiding walk

We introduce a new Monte Carlo algorithm for the self-avoiding walk (SAW), and show that it is particularly efficient in the critical region (long chains). We also introduce new and more efficient statistical techniques. We employ these methods to extract numerical estimates for the critical parameters of the SAW on the square lattice. We find=2.63820 ± 0.00004 ± 0.00030=1.352 ± 0.006 ± 0.025v=0.7590 ± 0.0062 ± 0.0042 where the first error bar represents systematic error due to corrections to scaling (subjective 95% confidence limits) and the second bar represents statistical error (classical 95% confidence limits). These results are based on SAWs of average length 166, using 340 hours CPU time on a CDC Cyber 170–730. We compare our results to previous work and indicate some directions for future research.     

Self-avoiding random walks on the hexagonal lattice

We use the algorithm recently introduce by A. Berretti and A. D. Sokal to compute numerically the critical exponents for the self-avoiding random walk on the hexagonal lattice. We find=1.3509±0.0057±0.0023v=0.7580±0.0049±0.0046=0.519±0.082±0.077 where the first error is the systematic one due to corrections to scaling and the second is the statistical error. For the effective coordination number we find=1.84779±0.00006±0.0017 The results support the Nienhuis conjecture=43/32 and provide a rough numerical check of the hyperscaling relationdv=2–. An additional analysis, taking the Nienhuis value of=(2+2^1/2)^1/2 for granted, gives=1.3459±0.0040±0.0008     

End patterns of self-avoiding walks

Consider a fixed end pattern (a short self-avoiding walk) that can occur as the first few steps of an arbitrarily long self-avoiding walk on ^d. It is a difficult open problem to show that asN , the fraction ofN-step self-avoiding walks beginning with this pattern converges. It is shown that asN , this fraction is bounded away from zero, and that the ratio of the fractions forN andN+2 converges to one. Similar results are obtained when patterns are specified at both ends, and also when the endpoints are fixed.     

Nonergodicity of local,length-conserving Monte Carlo algorithms for the self-avoiding walk

It is proved that every dynamic Monte Carlo algorithm for the self-avoiding walk based on a finite repertoire of local,N-conserving elementary moves is nonergodic (hereN is the number of bonds in the walk). Indeed, for largeN, each ergodic class forms an exponentially small fraction of the whole space. This invalidates (at least in principle) the use of the Verdier-Stockmayer algorithm and its generalizations for high-precision Monte Carlo studies of the self-avoiding walk.     

Two-dimensional oriented self-avoiding walks with parallel contacts

Oriented self-avoiding walks (OSAWs) on a square lattice are studied, with binding energies between steps that are oriented parallel across a face of the lattice. By means of exact enumeration and Monte Carlo simulation, we reconstruct the shape of the partition function and show that this system features of first-order phase transition from a free phase to a tight-spiral phase at _s =log(), where -2.638 is the growth constant for SAWs. With Monte Carlo simulations we show that parallel contacts happen predominantly between a step close to the end of the OSAW and another step nearby; this appears to cause the expected number of parallel contacts to saturate at large lengths of the OSAW.     

A note on mean-field behavior for self-avoiding walk on branching planes

We consider the critical behavior of the susceptibility of the self-avoiding walk on the graphT×Z, whereT is a Bethe lattice with degreek andZ is the one dimensional lattice. By directly estimating the two-point function using a method of Grimmett and Newman, we show that the bubble condition is satisfied whenk>2, and therefore the critical exponent associated with the susceptibility equals 1.     

Critical exponents for the self-avoiding random walk in three dimensions

We compute by direct Monte Carlo simulation the main critical exponents, , ₄, andv and the effective coordination number for the self-avoiding random walk in three dimensions on a cubic lattice. We find both hyperscaling relationsdv=2– anddv– 2 ₄+=0 satisfied ind = 3.     

Correction-to-Scaling Exponents for Two-Dimensional Self-Avoiding Walks

We study the correction-to-scaling exponents for the two-dimensional self-avoiding walk, using a combination of series-extrapolation and Monte Carlo methods. We enumerate all self-avoiding walks up to 59 steps on the square lattice, and up to 40 steps on the triangular lattice, measuring the mean-square end-to-end distance, the mean-square radius of gyration and the mean-square distance of a monomer from the endpoints. The complete endpoint distribution is also calculated for self-avoiding walks up to 32 steps (square) and up to 22 steps (triangular). We also generate self-avoiding walks on the square lattice by Monte Carlo, using the pivot algorithm, obtaining the mean-square radii to ≈ 0.01% accuracy up to N=4000. We give compelling evidence that the first non-analytic correction term for two-dimensional self-avoiding walks is Δ₁=3/2. We compute several moments of the endpoint distribution function, finding good agreement with the field-theoretic predictions. Finally, we study a particular invariant ratio that can be shown, by conformal-field-theory arguments, to vanish asymptotically, and we find the cancellation of the leading analytic correction.     

Random walks with short-range interaction and mean-field behavior

We introduce a model of self-repelling random walks where the short-range interaction between two elements of the chain decreases as a power of the difference in proper time. The model interpolates between the lattice Edwards model and the ordinary random walk. We show by means of Monte Carlo simulations in two dimensions that the exponentv _MF obtained through a mean-field approximation correctly describes the numerical data and is probably exact as long as it is smaller than the corresponding exponent for self-avoiding walks. We also compute the exponent and present a numerical study of the scaling functions.     

Loop-erased self-avoiding random walk in two and three dimensions

If(n) is the position of the self-avoiding random walk in ^d obtained by erasing loops from simple random walk, then it is proved that the mean square displacementE(¦(n)¦²) grows at least as fast as the Flory predictions for the usual SAW, i.e., at least as fast asn ^3/2 ford=2 andn ^6/5 ford=3. In particular, if the mean square displacement of the usual SAW grows liken ^1.18... ind=3, as expected, then the loop-erased process is in a different universality class.     

Thermodynamics of a dense self-avoiding walk with contact interactions

A lattice model is used to study the properties of an infinite self-avoiding linear polymer chain that occupies a fraction, 01, of sites on ad-dimensional hypercubic lattice. The model introduces an (attractive or repulsive) interaction energy between nonbonded monomers that are nearest neighbors on the lattice. The lattice cluster theory enables us to derive a double series expansion in and d^–1 for the chain free energy per segment while retaining the full dependence. Thermodynamic quantities, such as the entropy, energy, and mean number of contacts per segment, are evaluated, and their dependences on, , andd are discussed. The results are in good accordance with known limiting cases.     

Critical exponent for the loop erased self-avoiding walk by Monte Carlo methods

A Monte Carlo simulation was performed for loop-erased self-avoiding walks (LESAW) to ascertain the exponentv for the Z² and Z³ lattices. The estimated values were 2v=1.600±0.006 in two dimensions and 2v=1.232±0.008 in three dimensions, leading to the conjecturev=4/5 for the two-dimensional LESAW. These results add to existing evidence that the loop-erased self-avoiding walks are not in the same universality class as self-avoiding walks.     

High-precision Monte Carlo test of the conformai-invariance predictions for two-dimensional mutually avoiding walks

Let _l be the critical exponent associated with the probability thatl independentN-step ordinary random walks, starting at nearby points, are mutually avoiding. Using Monte Carlo methods combined with a maximum-likelihood data analysis, we find that in two dimensions ₂=0.6240±0.0005±0.0011 and ₃=1.4575±0.0030±0.0052, where the first error bar represents systematic error due to corrections to scaling (subjective 95% confidence limits) and the second error bar represents statistical error (classical 95% confidence limits). These results are in good agreement with the conformal-invariance predictions ₂=5/8 and ₃=35/24.     

Molecular trajectory algorithm for random walks on percolation systems at criticality in two and three dimensions

Random walk simulations based on a molecular trajectory algorithm are performed on critical percolation clusters. The analysis of corrections to scaling is carried out. It has been found that the fractal dimension of the random walk on the incipient infinite cluster is d_w=2.873±0.008 in two dimensions and 3.78 ± 0.02 in three dimensions. If instead the diffusion is averaged over all clusters at the threshold not subject to the infinite restriction, the corresponding critical exponent k is found to be k=0.3307±0.0014 for two-dimensional space and 0.199 ± 0.002 for three-dimensional space. Moreover, in our simulations the asymptotic behaviors of local critical exponents are reached much earlier than in other numerical methods.     

Bilocal Dynamics for Self-Avoiding Walks

We introduce several bilocal algorithms for lattice self-avoiding walks. We discuss their ergodicity in different confined geometries, for instance in strips and in slabs. A short discussion of the dynamical properties in the absence of interactions is given.