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.     

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 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.     

Monte Carlo study of self-avoiding surfaces

Two models of self-avoiding surfaces on the cubic lattice are studied by Monte Carlo simulations. Both the first model with fluctuating boundary and the second one with a fixed boundary are found to belong to the universality class of branched polymers. The algorithms as well as the methods used to extract the critical exponents are described in detail. The results are compared to other recent estimates in the literature.     

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 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.     

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.     

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.     

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.     

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.     

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.     

Random walk on distant mesh points Monte Carlo methods

A new technique for obtaining Monte Carlo algorithms based on the Markov chains with a finite number of states is suggested. Instead of the classical random walk on neighboring mesh points, a general way of constructing Monte Carlo algorithms that could be called random walk on distant mesh points is considered. It is applied to solve boundary value problems. The numerical examples indicate that the new methods are less laborious and therefore more efficient.In conclusion, we mention that all Monte Carlo algorithms are parallel and could be easily realized on parallel computers.     

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 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.     

Equation of Motion in Hybrid Monte Carlo

The equation of motion and molecular dynamics for simulating lattice field theory using the Hybrid Monte Carlo (HMC) algorithm are described. Some techniques for improving the HMC efficiency are discussed.     

A Monte Carlo algorithm for lattice ribbons

A lattice ribbon is a connected sequence of plaquettes subject to certain selfavoidance conditions. The ribbon can be closed to form an object which is topologically either a cylinder or a Möbius band, depending on whether its surface is orientable or nonorientable. We describe a grand canonical Monte Carlo algorithm for generating a sample of these ribbons, prove that the associated Markov chain is ergodic, and present and discuss numerical results about the dimensions and entanglement complexity of the ribbons.     

Two-sided bounds on the free energy from local states in Monte Carlo simulations

We show that a precise assessment of free energy estimates in Monte Carlo simulations of lattice models is possible by using cluster variation approximations in conjunction with the local states approximations proposed by Meirovitch. The local states method (LSM) utilizes entropy expressions which recently have been shown to correspond to a converging sequence of upper bounds on the thermodynamic limit entropy density (i.e., entropy per lattice site), whereas the cluster variation method (CVM) supplies formulas that in some cases have been proven to be, and in other cases are believed to be, lower bounds. We have investigated CVM-LSM combinations numerically in Monte Carlo simulations of the two-dimensional Ising model and the two-dimensional five-states ferromagnetic Potts model. Even in the critical region the combination of upper and lower bounds enables an accurate and reliable estimation of the free energy from data of a single run. CVM entropy approximations are therefore useful in Monte Carlo simulation studies and in establishing the reliability of results from local states methods.     

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.     

Worm Monte Carlo study of the honeycomb-lattice loop model

We present a Markov-chain Monte Carlo algorithm of worm   type that correctly simulates the O(n)$O(n)$ loop model on any (finite and connected) bipartite cubic graph, for any real n>0$n>0$, and any edge weight, including the fully-packed limit of infinite edge weight. Furthermore, we prove rigorously that the algorithm is ergodic and has the correct stationary distribution. We emphasize that by using known exact mappings when n=2$n=2$, this algorithm can be used to simulate a number of zero-temperature Potts antiferromagnets for which the Wang–Swendsen–Kotecký cluster algorithm is non-ergodic, including the 3-state model on the kagome lattice and the 4-state model on the triangular lattice. We then use this worm algorithm to perform a systematic study of the honeycomb-lattice loop model as a function of n?2$n?2$, on the critical line and in the densely-packed and fully-packed phases. By comparing our numerical results with Coulomb gas theory, we identify a set of exact expressions for scaling exponents governing some fundamental geometric and dynamic observables. In particular, we show that for all n?2$n?2$, the scaling of a certain return time in the worm dynamics is governed by the magnetic dimension of the loop model, thus providing a concrete dynamical interpretation of this exponent. The case n>2$n>2$ is also considered, and we confirm the existence of a phase transition in the 3-state Potts universality class that was recently observed via numerical transfer matrix calculations.     

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.