Self-avoiding walk

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Self avoiding walk.svg

In mathematics, a self-avoiding walk (SAW) is a sequence of moves on a lattice that does not visit the same point more than once. This is a special case (and, so far, the best studied one) of the graph theoretical notion of a path. A self-avoiding polygon (SAP) is a closed self-avoiding walk on a lattice. SAWs were first introduced by the chemist Paul Flory[1] in order to model the real-life behavior of chain-like entities such as solvents and polymers, whose physical volume prohibits multiple occupation of the same spatial point. Very little is known rigorously about the self-avoiding walk from a mathematical perspective, although physicists have provided numerous conjectures that are believed to be true and are strongly supported by numerical simulations.

In computational physics a self-avoiding walk is a chain-like path in R2 or R3 with a certain number of nodes, typically a fixed step length and has the imperative property that it doesn't cross itself or another walk. A system of self-avoiding walks satisfies the so-called excluded volume condition. In higher dimensions, the self-avoiding walk is believed to behave much like the ordinary random walk. SAWs and SAPs play a central role in the modelling of the topological and knot-theoretic behaviour of thread- and loop-like molecules such as proteins. SAW is a fractal.[2][3] For example, in d = 2 the fractal dimension is 4/3, for d = 3 it is close to 5/3 while for d ≥ 4 the fractal dimension is 2. The dimension is called the upper critical dimension above which excluded volume is negligible. A SAW that does not satisfy the excluded volume condition was recently studied to model explicit surface geometry resulting from expansion of a SAW.[4]

The properties of SAWs cannot be calculated analytically, so numerical simulations are employed. The pivot algorithm is a common method for Markov chain Monte Carlo simulations for the uniform measure on n-step self-avoiding walks. The pivot algorithm works by taking a self-avoiding walk and randomly choosing a point on this walk, and then applying a symmetry operation (rotations and reflections) on the walk after the nth step to create a new walk. Calculating the number of self-avoiding walks in any given lattice is a common computational problem. There is currently no known formula for determining the number of self-avoiding walks, although there are rigorous methods for approximating them.[5][6] Finding the number of such paths is conjectured to be an NP-hard problem. For self-avoiding walks from one end of a diagonal to the other, with only moves in the positive direction, there are exactly

{m+n \choose m,n}

paths for an m × n rectangular lattice.


One of the phenomena associated with self-avoiding walks and 2-dimensional statistical physics models in general is the notion of universality, that is, independence of macroscopic observables from microscopic details, such as the choice of the lattice. One important quantity that appears in conjectures for universal laws is the connective constant, defined as follows. Let cn denote the number of n-step self-avoiding walks. Since every (n + m)-step self avoiding walk can be decomposed into an n-step self-avoiding walk and an m-step self-avoiding walk, it follows that cn+mcncm. Therefore the sequence {log cn} is subadditive and we can apply Fekete's lemma to show that the following limit exists:

\mu = \lim_{n \to \infty} c_n^{\frac{1}{n}}.

μ is called the connective constant, since cn depends on the particular lattice chosen for the walk so does μ. The exact value of μ is only known for the hexagonal lattice, where it is equal to:[7]

\sqrt{2 + \sqrt{2}}.

For other lattices, μ has only been approximated numerically, and is believed to not even be an algebraic number. It is conjectured that

c_n \approx \mu^n n^{\frac{11}{32}}

as n → ∞, where μ depends on the lattice, but the power law correction n^{\frac{11}{32}} does not; in other words, this law is believed to be universal.


Consider the uniform measure on n-step self-avoiding walks in the full plane. It is currently unknown whether the limit of the uniform measure as n → ∞ induces a measure on infinite full-plane walks. However, Harry Kesten has shown that such a measure exists for self-avoiding walks in the half-plane. One important question involving self-avoiding walks is the existence and conformal invariance of the scaling limit, that is, the limit as the length of the walk goes to infinity and the mesh of the lattice goes to zero. The scaling limit of the self-avoiding walk is conjectured to be described by Schramm–Loewner evolution with parameter κ = 8/3.

Self-avoiding walks in popular culture[edit]

The computer video game Snake is an example of a self-avoiding walk.


  1. ^ P. Flory (1953). Principles of Polymer Chemistry. Cornell University Press. p. 672. ISBN 9780801401343. 
  2. ^ S. Havlin, D. Ben-Avraham (1982). "New approach to self-avoiding walks as a critical phenomenon". J. Phys. A 15: 321. doi:10.1088/0305-4470/15/6/013. 
  3. ^ S. Havlin, D. Ben-Avraham (1982). "Theoretical and numerical study of fractal dimensionality in self-avoiding walks". Phys. Rev. A 26 (3): 1728. Bibcode:1982PhRvA..26.1728H. doi:10.1103/PhysRevA.26.1728. 
  4. ^ A. Bucksch, G. Turk, J.S. Weitz (2014). "The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion". PLoSOne 9 (1): e85585. doi:10.1371/journal.pone.0085585. 
  5. ^ Hayes B (Jul–Aug 1998). "How to Avoid Yourself". American Scientist 86 (4). doi:10.1511/1998.31.3301. 
  6. ^ Liśkiewicz M, Ogihara M, Toda S (July 2003). "The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes". Theoretical Computer Science 304 (1–3): 129–56. doi:10.1016/S0304-3975(03)00080-X. 
  7. ^ This is a recent result from Duminil-Copin and Smirnov: H. Duminil-Copin; S. Smirnov (2010). "The connective constant of the honeycomb lattice equals \sqrt{2+\sqrt2}". arXiv preprint arXiv:1007.0575 (2010). 

Further reading[edit]

  1. Madras, N.; Slade, G. (1996). The Self-Avoiding Walk. Birkhäuser. ISBN 978-0-8176-3891-7. 
  2. Lawler, G. F. (1991). Intersections of Random Walks. Birkhäuser. ISBN 978-0-8176-3892-4. 
  3. Madras, N.; Sokal, A. D. (1988). "The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk". Journal of Statistical Physics 50. 
  4. Fisher, M. E. (1966). "Shape of a self-avoiding walk or polymer chain". Journal of Chemical Physics 44 (2): 616. Bibcode:1966JChPh..44..616F. doi:10.1063/1.1726734. 

External links[edit]