在数学中,自避行走(简称:SAW,Self-Avoiding Walk)是一种格点上的随机漫步,但是不会多次访问同一点。所以SAW不是一种马尔可夫链。SAW模型在物理学、化学、生物学中有很多应用。
自避行走是一个分形。 例如,
没有已知的公式来计算给格子的SAW数。
× 矩形点阵在只允许选择减少曼哈顿距离的方向从一角往其对角行走的情况下有
个SAW。
主要条目:普遍性 (物理学)
设 c n {\displaystyle c_{n}} 是SAW数。这满足 c n c m ≤ c n + m {\displaystyle c_{n}c_{m}\leq c_{n+m}} 所以 log c n {\displaystyle \log c_{n}} 是次可加的以及
μ = lim n → ∞ c n 1 / n {\displaystyle \mu =\lim _{n\to \infty }c_{n}^{1/n}}
存在。格点六角形(hexagonal lattice)的 μ = 2 + 2 {\displaystyle \mu ={\sqrt {2+{\sqrt {2}}}}} 。(斯坦尼斯拉夫·斯米尔诺夫)
有猜想说:当 n → ∞ {\displaystyle n\to \infty } 的时候
c n ≈ μ n n 11 / 32 {\displaystyle c_{n}\approx \mu ^{n}n^{11/32}}
上面的 μ {\displaystyle \mu } 依赖格点,但是11/32这个数是普遍的。