Self-avoiding walk

In mathematics, a self-avoiding walk (SAW) is a sequence of moves on a lattice (a lattice path) that does not visit the same point more than once. This is a special case 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]^{[dubious – discuss]} 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 $R 2$ or $R 3$ 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 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠4/3⁠$ , for $d = 3$ it is close to $⁠ 5 / 3 ⁠$ while for $d \geq 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^{[citation needed]}. 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 \times n$ rectangular lattice.

Universality

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 $c n$ 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 $c n + m \leq c n c m$ . Therefore, the sequence ${log c n}$ 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 $c n$ 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 \to \infty$ , 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.

Self-avoiding walks on networks

Self-avoiding walks have also been studied in the context of network theory.^[8] 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 networks, the distribution of path length's of such dynamically grown SAW's can be calculated analytically, and follows the Gompertz distribution.^[9]

Limits

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 \to \infty$ 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 ⁠ .$

References

^ P. Flory (1953). Principles of Polymer Chemistry. Cornell University Press. p. 672. ISBN 9780801401343.
^ 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.
^ 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.
^ A. Bucksch, G. Turk, J.S. Weitz (2014). "The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion". PLOS ONE. 9 (1): e85585. doi:10.1371/journal.pone.0085585.{{cite journal}}: CS1 maint: multiple names: authors list (link) CS1 maint: unflagged free DOI (link)
^ Hayes B (Jul–Aug 1998). "How to Avoid Yourself". American Scientist. 86 (4). doi:10.1511/1998.31.3301.
^ 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.
^ Duminil-Copin, Hugo; Smirnov, Stanislav (1 May 2012). "The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)". Annals of Mathematics. 175 (3): 1653–1665. doi:10.4007/annals.2012.175.3.14.
^ Carlos P. Herrero (2005). "Self-avoiding walks on scale-free networks". Phys. Rev. E. 71 (3): 1728. doi:10.1103/PhysRevE.71.016103.
^ Tishby, Biham, Katzav (2016), The distribution of path lengths of self avoiding walks on Erdős-Rényi networks, arXiv:1603.06613.

External links

OEIS: A007764: the number of self-avoiding paths joining opposite corners of an N × N grid, for N from 0 to 12. Also includes an extended list up to N = 21.
Weisstein, Eric W. "Self-Avoiding Walk". MathWorld.
Java applet of a 2D self-avoiding walk
Generic python implementation to simulate SAWs and expanding FiberWalks on a square lattices in n-dimensions.
Norris software to generate SAWs on the Diamond cubic.

[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". PLOS ONE. 9 (1): e85585. doi:10.1371/journal.pone.0085585.{{cite journal}}: CS1 maint: multiple names: authors list (link) CS1 maint: unflagged free DOI (link)

[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] Duminil-Copin, Hugo; Smirnov, Stanislav (1 May 2012). "The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2)". Annals of Mathematics. 175 (3): 1653–1665. doi:10.4007/annals.2012.175.3.14.

[8] Carlos P. Herrero (2005). "Self-avoiding walks on scale-free networks". Phys. Rev. E. 71 (3): 1728. doi:10.1103/PhysRevE.71.016103.

[9] Tishby, Biham, Katzav (2016), The distribution of path lengths of self avoiding walks on Erdős-Rényi networks, arXiv:1603.06613.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v t e Fractals
Characteristics	Fractal dimensions Assouad Box-counting Higuchi Correlation Hausdorff Packing Topological Recursion Self-similarity
Iterated function system	Barnsley fern Cantor set Koch snowflake Menger sponge Sierpiński carpet Sierpiński triangle Apollonian gasket Fibonacci word Space-filling curve Blancmange curve De Rham curve Minkowski Dragon curve Hilbert curve Koch curve Lévy C curve Moore curve Peano curve Sierpiński curve Z-order curve String T-square n-flake Vicsek fractal Gosper curve Pythagoras tree Weierstrass function
Strange attractor	Multifractal system
L-system	Fractal canopy Space-filling curve H tree
Escape-time fractals	Burning Ship fractal Julia set Filled Newton fractal Douady rabbit Lyapunov fractal Mandelbrot set Misiurewicz point Multibrot set Newton fractal Tricorn Mandelbox Mandelbulb
Rendering techniques	Buddhabrot Orbit trap Pickover stalk
Random fractals	Brownian motion Brownian tree Brownian motor Fractal landscape Lévy flight Percolation theory Self-avoiding walk
People	Michael Barnsley Georg Cantor Bill Gosper Felix Hausdorff Desmond Paul Henry Gaston Julia Niels Fabian Helge von Koch Paul Lévy Aleksandr Lyapunov Benoit Mandelbrot Hamid Naderi Yeganeh Lewis Fry Richardson Wacław Sierpiński
Other	Coastline paradox Fractal art List of fractals by Hausdorff dimension The Fractal Geometry of Nature (1982 book) The Beauty of Fractals (1986 book) Chaos: Making a New Science (1987 book) Kaleidoscope Chaos theory

v t e Stochastic processes
Discrete time	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding Biased Maximal entropy
Continuous time	Additive process Bessel process Birth–death process pure birth Brownian motion Bridge Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Dyson Brownian motion Empirical process Feller process Fleming–Viot process Gamma process Geometric process Hawkes process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage
Both	Branching process Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process Stochastic chains with memory of variable length White noise
Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Poisson Random field Random graph
Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive–moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model
Financial models	Binomial options pricing model Black–Derman–Toy Black–Karasinski Black–Scholes Chan–Karolyi–Longstaff–Sanders (CKLS) Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White Korn-Kreer-Lenssen LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie
Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson
Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c
Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise-deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible
Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem Zero–one laws (Blumenthal, Borel–Cantelli, Engelbert–Schmidt, Hewitt–Savage, Kolmogorov, Lévy)
Inequalities	Burkholder–Davis–Gundy Doob's martingale Doob's upcrossing Kunita–Watanabe Marcinkiewicz–Zygmund
Tools	Cameron–Martin formula Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Karhunen–Loève theorem Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract
Disciplines	Actuarial mathematics Control theory Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Signal processing Statistics Stochastic analysis Time series analysis Machine learning
List of topics Category

Universality

Self-avoiding walks on networks

Limits

References

Further reading

External links