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

Neal Madras; Alan D. Sokal

doi:10.1007/BF01022990

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

Neal Madras, Alan D. Sokal

Research output: Contribution to journal › Article › peer-review

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 (here N 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 order N. 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 in d=2 and υ= 0.592±0.003 in d=3 (95% confidence limits), based on SAWs of lengths 200≤N≤10000 and 200≤N≤ 3000, respectively.

Original language	English (US)
Pages (from-to)	109-186
Number of pages	78
Journal	Journal of Statistical Physics
Volume	50
Issue number	1-2
DOIs	https://doi.org/10.1007/BF01022990
State	Published - Jan 1988

Keywords

Monte Carlo
Self-avoiding walk
critical exponent
pivot algorithm
polymer

ASJC Scopus subject areas

Statistical and Nonlinear Physics
Mathematical Physics

Access to Document

10.1007/BF01022990

Cite this

@article{8e55877bd08f47a1a71eac09f18d4e1d,

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

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 (here N 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 order N. 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 in d=2 and υ= 0.592±0.003 in d=3 (95% confidence limits), based on SAWs of lengths 200≤N≤10000 and 200≤N≤ 3000, respectively.",

keywords = "Monte Carlo, Self-avoiding walk, critical exponent, pivot algorithm, polymer",

author = "Neal Madras and Sokal, {Alan D.}",

year = "1988",

month = jan,

doi = "10.1007/BF01022990",

language = "English (US)",

volume = "50",

pages = "109--186",

journal = "Journal of Statistical Physics",

issn = "0022-4715",

publisher = "Springer New York",

number = "1-2",

}

TY - JOUR

T1 - The pivot algorithm

T2 - A highly efficient Monte Carlo method for the self-avoiding walk

AU - Madras, Neal

AU - Sokal, Alan D.

PY - 1988/1

Y1 - 1988/1

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 (here N 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 order N. 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 in d=2 and υ= 0.592±0.003 in d=3 (95% confidence limits), based on SAWs of lengths 200≤N≤10000 and 200≤N≤ 3000, respectively.

AB - 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 (here N 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 order N. 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 in d=2 and υ= 0.592±0.003 in d=3 (95% confidence limits), based on SAWs of lengths 200≤N≤10000 and 200≤N≤ 3000, respectively.

KW - Monte Carlo

KW - Self-avoiding walk

KW - critical exponent

KW - pivot algorithm

KW - polymer

UR - http://www.scopus.com/inward/record.url?scp=5944256461&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=5944256461&partnerID=8YFLogxK

U2 - 10.1007/BF01022990

DO - 10.1007/BF01022990

M3 - Article

AN - SCOPUS:5944256461

SN - 0022-4715

VL - 50

SP - 109

EP - 186

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

IS - 1-2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this