View source for Self-avoiding walk

{{Short description|Sequence of moves on a lattice}}
[[File:Self avoiding walk.svg|thumb|Self-avoiding walk on a 15×15 square lattice]]
[[File:Saw60 new.gif|thumb|Self-avoiding walk on a 20x20 square lattice, simulated using [[Particle filter|sequential Monte Carlo]]]]
{{unsolved|mathematics|Is there a formula or algorithm that can calculate the number of self-avoiding walks in any given lattice?}}

In [[Mathematics|mathematics]], a '''self-avoiding walk''' ('''SAW''') is a [[Sequence|sequence]] of moves on a [[Lattice (group)|lattice]] (a [[Lattice path|lattice path]]) that does not visit the same point more than once. This is a special case of the [[Graph theory|graph theoretical]] notion of a [[Path (graph theory)|path]]. A '''self-avoiding polygon''' ('''SAP''') is a closed self-avoiding walk on a lattice. 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 [[Physics:Computational physics|computational physics]], a self-avoiding walk is a chain-like path in {{math|'''R'''<sup>2</sup>}} or {{math|'''R'''<sup>3</sup>}} with a certain number of nodes, typically a fixed step length and has the property that it doesn't cross itself or another walk. A system of SAWs satisfies the so-called [[Physics:Excluded volume|excluded volume]] condition. In higher dimensions, the SAW is believed to behave much like the ordinary [[Random walk|random walk]].

SAWs and SAPs play a central role in the modeling of the [[Topology|topological]] and [[Knot theory|knot-theoretic]] behavior of thread- and loop-like molecules such as [[Biology:Protein|protein]]s. Indeed, SAWs may have first been introduced by the chemist [[Biography:Paul Flory|Paul Flory]]<ref>{{cite book|author=P. Flory|title=Principles of Polymer Chemistry|year=1953|publisher=Cornell University Press|isbn= 978-0-8014-0134-3|pages=672}}</ref> in order to model the real-life behavior of chain-like entities such as [[Physics:Solvent|solvent]]s and [[Chemistry:Polymer|polymer]]s, whose physical volume prohibits multiple occupation of the same spatial point.

SAWs are [[Fractal|fractal]]s. For example, in {{math|''d'' {{=}} 2}} the [[Fractal dimension|fractal dimension]] is 4/3, for {{math|''d'' {{=}} 3}} it is close to 5/3 while for {{math|''d'' ≥ 4}} the fractal dimension is {{math|2}}. The dimension is called the upper [[Physics:Critical dimension|critical dimension]] above which excluded volume is negligible. A SAW that does not satisfy the excluded volume condition was recently studied to model explicit [[Physics:Surface growth|surface geometry]] resulting from expansion of a SAW.<ref>{{cite journal|author=A. Bucksch|author2=G. Turk|author3=J.S. Weitz|title=The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion|year=2014| journal=PLOS ONE|volume=9|issue=1|article-number=e85585| doi=10.1371/journal.pone.0085585|pmid=24465607|pmc=3899046|arxiv=1304.3521|bibcode=2014PLoSO...985585B|doi-access=free}}</ref>{{clarify|reason=This "orphan" sentence is not explained in the article.|date=October 2023}} The average size of a self-avoiding walk increases with respect to its length according to an exponent that is the reciprocal of the fractal dimension. The [[Physics:Radius of gyration|radius of gyration]] of a SAW depends on the 3/4 power of length in two dimensions, and approximately the 3/5th power in three dimensions.

The properties of SAWs cannot be calculated analytically, so numerical [[Simulation|simulation]]s are employed. The [[Pivot algorithm|pivot algorithm]] is a common method for [[Markov chain Monte Carlo]] simulations for the uniform measure on {{mvar|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 [[Symmetry|symmetrical]] transformations (rotations and reflections) on the walk after the {{mvar|n}}th step to create a new walk.

Calculating the number of self-avoiding walks in any given lattice is a common [[Computational problem|computational problem]]. There is currently no known formula, although there are rigorous methods of approximation.<ref>{{cite journal|author=Hayes B|date=Jul–Aug 1998|title=How to Avoid Yourself|journal=American Scientist|volume=86|issue=4|page=314|doi=10.1511/1998.31.3301|url=http://bit-player.org/wp-content/extras/bph-publications/AmSci-1998-07-Hayes-self-avoidance.pdf}}</ref><ref>{{cite journal |author1=Liśkiewicz M |author2=Ogihara M |author3=Toda S |title=The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes |journal=Theoretical Computer Science |volume=304 |issue=1–3 |pages=129–56 |date=July 2003 | doi=10.1016/S0304-3975(03)00080-X |doi-access=free }}</ref>

==Universality==
One of the phenomena associated with self-avoiding walks and statistical physics models in general is the notion of [[Universality (dynamical systems)|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|connective constant]], defined as follows. Let {{mvar|c<sub>n</sub>}} denote the number of {{mvar|n}}-step self-avoiding walks. Since every {{math|(''n'' + ''m'')}}-step self avoiding walk can be decomposed into an {{mvar|n}}-step self-avoiding walk and an {{mvar|m}}-step self-avoiding walk, it follows that {{math|''c''<sub>''n''+''m''</sub> ≤ ''c<sub>n</sub>c<sub>m</sub>''}}. Therefore, the sequence {{math|{log ''c<sub>n</sub>''} }} is [[Subadditivity|subadditive]] and we can apply Fekete's lemma to show that the following limit exists:

:<math>\mu = \lim_{n \to \infty} c_n^{\frac{1}{n}}.</math>

{{mvar|μ}} is called the '''connective constant''', since {{mvar|c<sub>n</sub>}} depends on the particular lattice chosen for the walk so does {{mvar|μ}}. The exact value of {{mvar|μ}} is only known for the hexagonal lattice, found by [[Biography:Stanislav Smirnov|Stanislav Smirnov]] and Hugo Duminil-Copin, where it is equal to:<ref>{{cite journal|last1=Duminil-Copin|first1=Hugo|last2=Smirnov|first2=Stanislav|title=The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)|journal=Annals of Mathematics|date=1 May 2012|volume=175|issue=3|pages=1653–1665|doi=10.4007/annals.2012.175.3.14|arxiv=1007.0575|s2cid=59164280}}</ref>

:<math>\sqrt{2 + \sqrt{2}}.</math>

For other lattices, {{mvar|μ}} has only been approximated numerically, and is believed not to even be an [[Algebraic number|algebraic number]]. It is conjectured that<ref>{{cite journal | last1=Lawler | first1=Gregory F. | last2=Schramm | first2=Oded |  last3=Werner | first3=Wendelin | journal=Proceedings of Symposia in Pure Mathematics | pages=339–364 | publisher=American Mathematical Society | title=On the scaling limit of planar self-avoiding walk | date=2004 | volume=72 | issue=2 | doi=10.1090/pspum/072.2/2112127 | isbn=0-8218-3638-2 | arxiv=math/0204277| s2cid=16710180 }}</ref>

:<math>c_n \approx \mu^n n^{\frac{11}{32}}</math>

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

==Growing self-avoiding walk==
[[File:Self-avoiding walk gif.gif|thumb|alt=Growing and trapping walk|Several iterations of a growing self-avoiding walk on a square lattice, which terminate when the walk becomes trapped. The color scale evolve so that the latest step is yellow.]]
[[File:Saw7.png|thumb|alt=Shortest trapped SAW|A growing self-avoiding walk on a square lattice that has become trapped after taking its first step (green) in the upward direction. After its final step (red) there are no empty adjacent sites to hop to.]]
The growing self-avoiding walk (GSAW) is a [[Dynamical system|dynamical process]] in which a walk starts at the origin of a lattice and takes a step to an unoccupied site in a random direction. When there are no empty adjacent sites, the walk is said to be trapped, similar to the ending scenario in the video game [[Software:Snake (video game genre)|Snake]]. On a [[Square lattice|square lattice]] it is known from computer simulations that the average number of steps reached by a growing self-avoiding walk is approximately 71.<ref name="q608">{{cite journal | last1=Hemmer | first1=S. | last2=Hemmer | first2=P. C. | title=An average self-avoiding random walk on the square lattice lasts 71 steps | journal=The Journal of Chemical Physics | publisher=AIP Publishing | volume=81 | issue=1 | date=1984-07-01 | issn=0021-9606 | doi=10.1063/1.447349 | doi-access=free | pages=584–585 | bibcode=1984JChPh..81..584H | url=https://pubs.aip.org/aip/jcp/article-pdf/81/1/584/9721538/584_1_online.pdf | access-date=2025-09-07}}</ref> The shortest walk that leads to trapping on a square lattice is six steps, and can be achieved by starting on an empty lattice and moving up, right, right, down, down, left, and up. The average number of steps to trapping depends on the lattice or network, it is similar for the honeycomb lattice but near 78 for the triangular lattice. The average trapping length is much higher in three dimensions, being close to 4000 for the simple cubic lattice.<ref name="renner">{{cite thesis| last1=Renner| first1=A. | title=Self avoiding walks and lattice polymers | degree=masters | location=University of Vienna| date=1994}}</ref> The statistics of the traditional self-avoiding walk assume that each walk of a given length is equally likely, which is not the case for GSAWs. For example, there are 100 square lattice SAWs of length 4 starting at the origin, and four that are completely straight, such that there is a 0.04 probability of such a SAW being straight. However, a GSAW must make its first step in any direction with probability 1, its second in the same direction with probability 1/3, as with its third and fourth steps. Thus the probability of a GSAW being straight is 1/81≈0.012. For this reason, GSAWs are empirically observed in simulations to have a smaller scaling exponent (the relationship between the average [[Physics:Radius of gyration|radius of gyration]] and length) than the 3/4 predicted by the Flory model, and is observed to be close to 0.68.<ref name="o606">{{cite journal | last1=Lyklema | first1=J W | last2=Kremer | first2=K | title=Monte Carlo series analysis of irreversible self-avoiding walks. II. The growing self-avoiding walk | journal=Journal of Physics A: Mathematical and General | publisher=IOP Publishing | volume=19 | issue=2 | date=1986-02-01 | issn=0305-4470 | doi=10.1088/0305-4470/19/2/021 | pages=279–289 | bibcode=1986JPhA...19..279L }}</ref>

==Knots in self-avoiding polygons==
[[File:Trefcube Fixed.png|thumb|alt=Cubic knot|A trefoil knot occupying 24 vertices on a simple cubic lattice, the smallest knotted polygon.]]
Self-avoiding polygons in three dimensions may form knots.
On a simple cubic lattice the shortest knotted self-avoiding polygon is a trefoil knot that occupies 24 vertices.<ref name="b588">{{cite journal | last1=van Rensburg | first1=E J Janse | last2=Rechnitzer | first2=A | title=Minimal knotted polygons in cubic lattices | journal=Journal of Statistical Mechanics: Theory and Experiment | volume=2011 | issue=9 | date=2011-09-14 | issn=1742-5468 | doi=10.1088/1742-5468/2011/09/P09008 | doi-access=free | article-number=P09008 | arxiv=1107.2162 | bibcode=2011JSMTE..09..008J }}</ref>
As self-avoiding polygons of greater length are considered, the probability of finding knots increases. It is proven that as the length of a randomly chosen SAP increases, the probability of finding an [[Unknot|unknot]] decreases [[Exponential decay|exponentially]], implying that the probability of a self-avoiding polygon being knotted approaches 100% as its length increases.
The length of a SAP at which the probability of knotting on a face-centered cubic lattice reaches 50% is approximately 100,000, and this may vary in other lattices.<ref name="o708">{{cite journal | last1=Rensburg | first1=E J J van | last2=Whittington | first2=S G | title=The knot probability in lattice polygons | journal=Journal of Physics A: Mathematical and General | volume=23 | issue=15 | date=1990-08-07 | issn=0305-4470 | doi=10.1088/0305-4470/23/15/028 | pages=3573–3590 | bibcode=1990JPhA...23.3573V | url=https://iopscience.iop.org/article/10.1088/0305-4470/23/15/028 | access-date=2025-09-10| url-access=subscription }}</ref>
Self-avoiding walks that are not closed into polygons may also form entanglements that are colloquially recognized as knots, but these are not formally considered knots within [[Knot theory|knot theory]] unless the two ends of the walk are connected in some way.

==On networks==
Self-avoiding walks have also been studied in the context of [[Network theory|network theory]].<ref>{{cite journal |author= Carlos P. Herrero|year= 2005|title= Self-avoiding walks on scale-free networks|journal= Phys. Rev. E|volume= 71|issue= 3|page= 1728 |article-number= 016103|doi=10.1103/PhysRevE.71.016103|pmid= 15697654|arxiv= cond-mat/0412658|bibcode= 2005PhRvE..71a6103H|s2cid= 2707668}}</ref> In this context, it is customary to treat the SAW as a dynamical process, such that in every time-step a walker randomly hops between neighboring nodes of the network. The walk ends when the walker reaches a dead-end state, such that it can no longer progress to newly un-visited nodes. It was recently found that on [[Erdős–Rényi model|Erdős–Rényi]] networks, the distribution of path lengths of such dynamically grown SAWs can be calculated analytically, and follows the [[Gompertz distribution]].<ref>{{cite journal|last1=Tishby|first1=I.|last2=Biham|first2=O.|last3=Katzav|first3=E.|title=The distribution of path lengths of self avoiding walks on Erdős–Rényi networks|journal=Journal of Physics A: Mathematical and Theoretical|date=2016|volume=49|issue=28|article-number=285002|doi=10.1088/1751-8113/49/28/285002|arxiv=1603.06613|bibcode=2016JPhA...49B5002T|s2cid=119182848}}</ref> For arbitrary networks, the distribution of path lengths of the walk, the [[Degree distribution|degree distribution]] of the non-visited network and the [[First-hitting-time model|first-hitting-time]] distribution to a node can be obtained by solving a set of coupled recurrence equations.<ref>{{cite journal |last1=Colombani |first1=G. |last2=Bertagnolli |first2=G. |last3=Artime |first3=O. |title=Efficient network exploration by means of resetting self-avoiding random walkers |journal=Journal of Physics: Complexity |date=2023 |volume=4 |issue=4 |pages=04LT01 |doi=10.1088/2632-072X/acff33 |doi-access=free |arxiv=2310.03203 |bibcode=2023JPCom...4dLT01C }}</ref>

==Limits==
Consider the uniform measure on {{mvar|n}}-step self-avoiding walks in the full plane. It is currently unknown whether the limit of the uniform measure as {{math|''n'' → ∞}} induces a measure on infinite full-plane walks. However, [[Biography:Harry Kesten|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 [[Physics:Scaling limit|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 [[Physics:Scaling limit|scaling limit]] of the self-avoiding walk is conjectured to be described by [[Schramm–Loewner evolution]] with parameter {{math|''κ'' {{=}} {{sfrac|8|3}}.}}

== See also ==

* {{Annotated link|Critical phenomena}}
* {{Annotated link|Hamiltonian path}}
* {{Annotated link|Knight's tour}}
* {{Annotated link|Random walk}}
* {{Annotated link|Snake (video game genre)|Snake}}
* {{Annotated link|Universality (dynamical systems)|Universality}}
* Space-filling curves – All are self-avoiding.

==References==
{{Reflist}}

==Further reading==
{{Refbegin}}

# {{cite book
 | last = Madras | first = N.
 |author2=Slade, G.
  | year = 1996
 | title = The Self-Avoiding Walk
 | publisher = Birkhäuser
 | isbn = 978-0-8176-3891-7
 }}
# {{cite book
 | last = Lawler | first = G. F.
 | year = 1991
 | title = Intersections of Random Walks
 | publisher = Birkhäuser
 | isbn = 978-0-8176-3892-4
 }}
# {{cite journal
|author1=Madras, N. |author2=Sokal, A. D. |year= 1988
|title= The pivot algorithm – A highly efficient Monte-Carlo method for the self-avoiding walk
|journal= Journal of Statistical Physics
|volume= 50
|issue= 1–2
|doi= 10.1007/bf01022990
 |pages=109–186
 |bibcode=1988JSP....50..109M|s2cid=123272694 }}
# {{cite journal
|author=Fisher, M. E.
|year= 1966
|title= Shape of a self-avoiding walk or polymer chain
|journal= Journal of Chemical Physics
|volume= 44
|issue= 2
|pages= 616–622
|bibcode=1966JChPh..44..616F
|doi=10.1063/1.1726734
 }}

{{Refend}}

== External links ==
*{{OEIS el|1=A007764|2=Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid}}—the number of self-avoiding paths joining opposite corners of an ''N'' &times; ''N'' grid, for ''N'' from 0 to 12. Also includes an extended list up to ''N'' = 21.
*{{MathWorld|urlname=Self-AvoidingWalk|title=Self-Avoiding Walk}}
*[http://polymer.bu.edu/java/java/saw/saw.html Java applet of a 2D self-avoiding walk]
*[https://github.com/abucksch/FiberWalk Generic python implementation to simulate SAWs and expanding FiberWalks on a square lattices in n-dimensions.]
*[http://www.sas.upenn.edu/~vnanda/software.html Norris software] to generate SAWs on the [[Diamond cubic]].

{{Fractals}}
{{Stochastic processes}}

[[Category:Polygons]]
[[Category:Discrete geometry]]
[[Category:Computational physics]]
[[Category:Computational chemistry]]
[[Category:Variants of random walks]]

{{Sourceattribution|Self-avoiding walk}}