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

Neal Madras, Alan D. Sokal

    Research output: Contribution to journalArticle

    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 languageEnglish (US)
    Pages (from-to)109-186
    Number of pages78
    JournalJournal of Statistical Physics
    Volume50
    Issue number1-2
    DOIs
    StatePublished - Jan 1988

    Keywords

    • Monte Carlo
    • Self-avoiding walk
    • critical exponent
    • pivot algorithm
    • polymer

    ASJC Scopus subject areas

    • Statistical and Nonlinear Physics
    • Mathematical Physics

    Fingerprint Dive into the research topics of 'The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk'. Together they form a unique fingerprint.

  • Cite this