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.     

A Faster Implementation of the Pivot Algorithm for Self-Avoiding Walks

The pivot algorithm is a Markov Chain Monte Carlo algorithm for simulating the self-avoiding walk. At each iteration a pivot which produces a global change in the walk is proposed. If the resulting walk is self-avoiding, the new walk is accepted; otherwise, it is rejected. Past implementations of the algorithm required a time O(N) per accepted pivot, where N is the number of steps in the walk. We show how to implement the algorithm so that the time required per accepted pivot is O(N ^q ) with q<1. We estimate that q is less than 0.57 in two dimensions, and less than 0.85 in three dimensions. Corrections to the O(N ^q ) make an accurate estimate of q impossible. They also imply that the asymptotic behavior of O(N ^q ) cannot be seen for walk lengths which can be simulated. In simulations the effective q is around 0.7 in two dimensions and 0.9 in three dimensions. Comparisons with simulations that use the standard implementation of the pivot algorithm using a hash table indicate that our implementation is faster by as much as a factor of 80 in two dimensions and as much as a factor of 7 in three dimensions. Our method does not require the use of a hash table and should also be applicable to the pivot algorithm for off-lattice models.     

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.     

Monte Carlo Study of Four-Dimensional Self-avoiding Walks of up to One Billion Steps

We study self-avoiding walks on the four-dimensional hypercubic lattice via Monte Carlo simulations of walks with up to one billion steps. We study the expected logarithmic corrections to scaling, and find convincing evidence in support the scaling form predicted by the renormalization group, with an estimate for the power of the logarithmic factor of 0.2516(14), which is consistent with the predicted value of 1/4. We also characterize the behaviour of the pivot algorithm for sampling four dimensional self-avoiding walks, and conjecture that the probability of a pivot move being successful for an N-step walk is \(O([ \log N ]^{-1/4})\).     

Monte Carlo tests of stochastic Loewner evolution predictions for the 2D self-avoiding walk

The conjecture that the scaling limit of the two-dimensional self-avoiding walk (SAW) in a half plane is given by the stochastic Loewner evolution (SLE) with kappa = 8/3 leads to explicit predictions about the SAW. A remarkable feature of these predictions is that they yield not just critical exponents but also probability distributions for certain random variables associated with the self-avoiding walk. We test two of these predictions with Monte Carlo simulations and find excellent agreement, thus providing numerical support to the conjecture that the scaling limit of the SAW is SLE(8/3).     

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.     

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.     

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.     

Step-step correlations in restricted and self-avoiding random walks

Static step-step correlations for restricted and self-avoiding random walks (SARW) on quadratic and simple cubic lattices are studied with the help of Monte Carlo simulation technique. For the SARW ofN steps our results, for largeN tend to the theoretically predicted values. An analysis of the correlations for SARW in terms of the individual restrictions indicate that its value between steps at a distancer have a dominant contribution coming from the restriction prohibiting polygon closures of sides2r (r2). Our results also show that the contribution of successive restrictions to the mean-square end-to-end distance of a SARW decay with the same exponent as that of the correlations for the SARW.     

On Continuous-Time Self-Avoiding Random Walk in Dimension Four

We study the distribution of the end-to-end distance of continuous-time self-avoiding random walks (CTRW) in dimension four from two viewpoints. From a real-space renormalization-group map on probabilities, we conjecture the asymptotic behavior of the end-to-end distance of a weakly self-avoiding random walk (SARW) that penalizes two-body interactions of random walks in dimension four on a hierarchical lattice. Then we perform the Monte Carlo computer simulations of CTRW on the four-dimensional integer lattice, paying special attention to the difference in statistical behavior of the CTRW compared with the discrete-time random walks. In this framework, we verify the result already predicted by the renormalization-group method and provide new results related to enumeration of self-avoiding random walks and calculation of the mean square end-to-end distance and gyration radius of continous-time self-avoiding random walks.     

Join- and-cut algorithm for self-avoiding walks with variable length and free endpoints

We introduce a new Monte Carlo algorithm for generating self-avoiding walks of variable length and free endpoints. The algorithm works in the unorthodox ensemble consisting of all pairs of SAWs such that the total number of stepsN _tot in the two walks is fixed. The elementary moves of the algorithm are fixed-N (e.g., pivot) moves on the individual walks, and a novel join- and-cut move that concatenates the two walks and then cuts them at a random location. We analyze the dynamic critical behavior of the new algorithm, using a combination of rigorous, heuristic, and numerical methods. In two dimensions the autocorrelation time in CPU units grows as N^1.5, and the behavior improves in higher dimensions. This algorithm allows high-precision estimation of the critical exponent.     

Monte carlo study of the interacting self-avoiding walk model in three dimensions

We consider self-avoiding walks on the simple cubic lattice in which neighboring pairs of vertices of the walk (not connected by an edge) have an associated pair-wise additive energy. If the associated force is attractive, then the walk can collapse from a coil to a compact ball. We describe two Monte Carlo algorithms which we used to investigate this collapse process, and the properties of the walk as a function of the energy or temperature. We report results about the thermodynamic and configurational properties of the walks and estimate the location of the collapse transition.     

Efficient Implementation of the Pivot Algorithm for Self-avoiding Walks

The pivot algorithm for self-avoiding walks has been implemented in a manner which is dramatically faster than previous implementations, enabling extremely long walks to be efficiently simulated. We explicitly describe the data structures and algorithms used, and provide a heuristic argument that the mean time per attempted pivot for N-step self-avoiding walks is O(1) for the square and simple cubic lattices. Numerical experiments conducted for self-avoiding walks with up to 268 million steps are consistent with o(log N) behavior for the square lattice and O(log N) behavior for the simple cubic lattice. Our method can be adapted to other models of polymers with short-range interactions, on the lattice or in the continuum, and hence promises to be widely useful.     

Polymers and g|φ|4 theory in four dimensions

We investigate the approach to the critical point and the scaling limit of a variety of models on a four-dimensional lattice, including g|φ|₄⁴ theory and the self-avoiding random walk. Our results, both theoretical and numerical, provide strong evidence for the triviality of the scaling limit and for logarithmic corrections to mean field scaling laws, as predicted by the perturbative renormalization group. We relate logarithmic corrections to scaling to the triviality of the scaling limit. Our numerical analysis is based on a novel, high-precision Monte Carlo technique.     

Study of Monte Carlo methods for generating self-avoiding walks

The concept of fractal dimensionality is used to study different statistical methods for generating self-avoiding walks (SAWs). The reliability of SAWs traced by the enrichment technique and the dynamic Monte Carlo technique is verified. The number of dynamic cycles which represent a single independent SAW ofN ₀ steps is found to be about 0.1N ₀ ³ . We show that the enrichment process for generating SAWs may be presented as a critical phenomenon.     

Exponential convergence to equilibrium for a class of random-walk models

We prove exponential convergence to equilibrium (L ² geometric ergodicity) for a random walk with inward drift on a sub-Cayley rooted tree. This randomwalk model generalizes a Monte Carlo algorithm for the self-avoiding walk proposed by Berretti and Sokal. If the number of vertices of levelN in the tree grows asC _N ~ ^N N ^–1 , we prove that the autocorrelation time satisfies N² N¹⁺     

The statistical error of green's function Monte Carlo

The statistical error in the ground state energy as calculated by Green's Function Monte Carlo (GFMC) is analyzed and a simple approximate formula is derived which relates the error to the number of steps of the random walk, the variational energy of the trial function, and the time step of the random walk. Using this formula it is argued that as the thermodynamic limit is approached withN identical molecules, the computer time needed to reach a given error per molecule increases asN ^h where 0.5 <b < 1.5 and as the nuclear chargeZ of a system is increased the computer time necessary to reach a given error grows asZ ^5.5. Thus GFMC simulations will be most useful for calculating the properties of lowZ elements. The implications for choosing the optimal trial function from a series of trial functions is also discussed.     

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.     

From random to self-avoiding walks

A brief review will be given of the current situation in the theory of self-avoiding walks (SAWs). The Domb-Joyce model first introduced in 1972 consists of a random walk on a lattice in which eachN step configuration has a weighting factor Π _i=0 ^N?2 Π_j=i+2/N(1?ωδ_ij). Herei andj are the lattice sites occupied by the ith and jth points of the walk. When ω=0 the model reduces to a standard random walk, and when ω=1 it is a self-avoiding walk. The universality hypothesis of critical phenomena will be used to conjecture the behavior of the model as a function ofω for largeN. The implications for the theory of dilute polymer solutions will be indicated.     

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.