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

@article{citeulike:2473908, abstract = {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 200?N?10000 and 200?N? 3000, respectively.}, author = {Madras, Neal and Sokal, Alan D. }, citeulike-article-id = {2473908}, doi = {10.1007/BF01022990}, journal = {Journal of Statistical Physics}, keywords = {monte-carlo, review, statistical-mechanics, theory}, month = {January}, number = {1}, pages = {109--186}, posted-at = {2008-06-25 12:34:16}, priority = {2}, title = {The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk}, url = {http://dx.doi.org/10.1007/BF01022990}, volume = {50}, year = {1988} }

TY - JOUR ID - citeulike:2473908 L3 - citeulike-article-id:2473908 TI - The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk JF - Journal of Statistical Physics VL - 50 IS - 1 SP - 109 EP - 186 N2 - 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 200?N?10000 and 200?N? 3000, respectively. KW - monte-carlo KW - review KW - statistical-mechanics KW - theory AU - Madras, Neal AU - Sokal, Alan PY - 1988/01/01/ UR - http://dx.doi.org/10.1007/BF01022990 ER -