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.     

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.     

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.     

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.     

Asymptotic distributions for self-avoiding walks constrained to strips,cylinders, and tubes

A transfer matrix method for treating self-avoiding walks on a lattice is developed. Single walks confined to infinitely long strips, cylinders, or tubes are considered, particularly in the limit where the length of the walk becomes infinite compared to the transverse dimensions. In this case relevant distributions are demonstrated to be asymptotically Gaussian. Explicit numerical results are given for a few of the narrower systems. Similar results for self-avoiding cycles are indicated, too. Finally, the behavior of the various distributions as a function of strip width is discussed.Supported by the Robert A. Welch Foundation, Houston, Texas.     

Flory approximant for self-avoiding walks on fractals

A Flory approximant for the exponent describing the end-to-end distance of a self-avoiding walk (SAW) on fractals is derived. The approximant involves the fractal dimensionalities of the backbone and of the minimal path, and the exponent describing the resistance of the fractal. The approximant yields values which are very close to those available from exact and numerical calculations.     

Hierarchical Monte Carlo methods for fractal random fields

Two hierarchical Monte Carlo methods for the generation of self-similar fractal random fields are compared and contrasted. The first technique, successive random addition (SRA), is currently popular in the physics community. Despite the intuitive appeal of SRA, rigorous mathematical reasoning reveals that SRA cannot be consistent with any stationary power-law Gaussian random field for any Hurst exponent; furthermore, there is an inherent ratio of largest to smallest putative scaling constant necessarily exceeding a factor of 2 for a wide range of Hurst exponentsH, with 0.30<H<0.85. Thus, SRA is inconsistent with a stationary power-law fractal random field and would not be useful for problems that do not utilize additional spatial averaging of the velocity field. The second hierarchical method for fractal random fields has recently been introduced by two of the authors and relies on a suitable explicit multiwavelet expansion (MWE) with high-moment cancellation. This method is described briefly, including a demonstration that, unlike SRA, MWE is consistent with a stationary power-law random field over many decades of scaling and has low variance.     

Monte Carlo simulation of many-arm star polymers in two-dimensional good solvents in the bulk and at a surface

A Monte Carlo technique is proposed for the simulation of statistical properties of many-arm star polymers on lattices. In this vectorizing algorithm, the length of each arml is increased by one, step by step, from a starting configuration withl=1 orl=2 which is generated directly. This procedure is carried out for a large sample (e.g., 100,000 configurations). As an application, we have studied self-avoiding stars on the square lattice with arm lengths up tol _max=125 and up tof=20 arms, both in the bulk and in the geometry where the center of the star is adsorbed on a repulsive surface. The total number of configurations, which behaves asNl ^{G–1 fl} , where=2.6386 is the usual effective coordination number for self-avoiding walks on the square lattice, is analyzed, and the resulting exponents G=(f) and _s (f) for the bulk and surface geometries are found to be compatible with predictions of Duplantier and Saleur based on conformai invariance methods. We also obtain distribution functions for the monomer density and the distance of the end of an arm from its center. The results are consistent with a scaling theory developed by us.     

Monte Carlo molecular dynamics simulations for two-dimensional magnets

A combined Monte Carlo molecular dynamics simulation technique is used to study thedynamic structure factor on a square lattice for isotropic Heisenberg and planar classical ferromagnetic spin Hamiltonians.     

Bilinear quantum Monte Carlo: Expectations and energy differences

We propose a bilinear sampling algorithm in the Green's function Monte Carlo for expectation values of operators that do not commute with the Hamiltonian and for differences between eigenvalues of different Hamiltonians. The integral representations of the Schrödinger equations are transformed into two equations whose solution has the form _a(x) t(x, y)_b(y), where _a and _b are the wavefunctions for the two related systems andt(x, y) is a kernel chosen to couplex andy. The Monte Carlo process, with random walkers on the enlarged configuration spacex y, solves these equations by generating densities whose asymptotic form is the above bilinear distribution. With such a distribution, exact Monte Carlo estimators can be obtained for the expectation values of quantum operators and for energy differences. We present results of these methods applied to several test problems, including a model integral equation, and the hydrogen atom.     

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¹⁺     

Error Estimation in the Histogram Monte Carlo Method

We examine the sources of error in the histogram reweighting method for Monte Carlo data analysis. We demonstrate that, in addition to the standard statistical error which has been studied elsewhere, there are two other sources of error, one arising through correlations in the reweighted samples, and one arising from the finite range of energies sampled by a simulation of finite length. We demonstrate that while the former correction is usually negligible by comparison with statistical fluctuations, the latter may not be, and give criteria for judging the range of validity of histogram extrapolations based on the size of this latter correction.     

The Convergence of Markov Chain Monte Carlo Methods: From the Metropolis Method to Hamiltonian Monte Carlo

From its inception in the 1950s to the modern frontiers of applied statistics, Markov chain Monte Carlo has been one of the most ubiquitous and successful methods in statistical computing. The development of the method in that time has been fueled by not only increasingly difficult problems but also novel techniques adopted from physics. Here, the history of Markov chain Monte Carlo is reviewed from its inception with the Metropolis method to the contemporary state‐of‐the‐art in Hamiltonian Monte Carlo, focusing on the evolving interplay between the statistical and physical perspectives of the method.     

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     

Exact Monte Carlo for few-fermion systems

We have reconsidered the fundamental difficulties of fermion Monte Carlo as applied to few-body systems. We conclude that necessary ingredients of successful algorithms include the following: There must be equal populations of random walkers that carry positive and negative weights. The positions of positive walkers should be selected from a distribution that uses Green's functions to couple all walkers. The positions of negative walkers should be generated from those of positive walkers by means of odd permutations. The correct importance functions that take into account the global interactions of the populations are different for positive and negative walkers. Use of such importance functions breaks the symmetry that otherwise would exist between configurations (of the entire population) and configurations derived by interchanging positive and negative walkers. Based upon these observations, we have constructed a stable and accurate algorithm that solves a fully-polarized, three-dimensional, three-body model problem.     

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.     

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.     

Fast vectorized algorithm for the Monte Carlo simulation of the random field Ising model

An algorithm for the simulation of the 3-dimensional random field Ising model with a binary distribution of the random fields is presented. It uses multi-spin coding and simulates 64 physically different systems simultaneously. On one processor of a Cray YMP it reaches a speed of 184 million spin updates per second. For smaller field strength we present a version of the algorithm that can perform 242 million spin updates per second on the same machine.     

Monte Carlo法模拟油滴的理论分布

在密立根油滴实验中,应用Monte Carlo法数值地模拟实验室条件下可能的油滴带电量Q、平衡电压U和匀速运动时间t的理论分布,分别从三维分布、时间分布及数量方面比较3种选择油滴的标准,给出较合理的结论.     

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.