自避行走

在數學中，自避行走（簡稱：SAW，Self-Avoiding Walk）是一種格點上的隨機漫步，但是不能多次通過同一點。因此，SAW不是一種馬爾可夫鏈，但事實上，SAW模型在物理學、化學、生物學中有很多應用。

應用

溶劑和聚合物
蛋白質
高分子
紐結理論
隨機漫步
保羅·弗洛里學了化學中的自避行走。^[1]
網絡理論^[2]
Gompertz distribution^[3]
ER隨機圖
有數學家認為自避行走的縮放極限是一個 $κ = .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,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}8/3$ 的Schramm-Loewner演變。^[4]

介紹

自避行走是一個分形。^[5]^[6] 例如，^[7]


維度d	分形維數
$d = 2$	4/3
$d = 3$	5/3
$d \geq 4$	2	4是「upper critical dimension」（上面臨界維度）

沒有已知的公式用於計算給予格子的SAW數。^[8]^[9]

$m \times n$ 矩形點陣在只允許選擇減少曼哈頓距離的方向從一角往其對角行走的情況下有

{m+n \choose m,\ n}

個SAW。

普遍性

主要條目：普遍性 (物理學)

設 $c_{n}$ 是SAW數。這滿足 $c_{n}c_{m}\leq c_{n+m}$ 因此 $\log c_{n}$ 是次可加的以及

$\mu =\lim _{n\to \infty }c_{n}^{1/n}$

存在。格點六角形（hexagonal lattice）的 $\mu ={\sqrt {2+{\sqrt {2}}}}$ 。^[4]（斯坦尼斯拉夫·斯米爾諾夫）

某一猜想稱：當 $n\to \infty$ 的時候

$c_{n}\approx \mu ^{n}n^{11/32}$

上面的 $\mu$ 依賴格點，但是11/32這個數是普遍的。

參見

參考文獻

^ P. Flory. Principles of Polymer Chemistry. Cornell University Press. 1953: 672. ISBN 9780801401343.
^ Carlos P. Herrero. Self-avoiding walks on scale-free networks. Phys. Rev. E. 2005, 71 (3): 1728. Bibcode:2005PhRvE..71a6103H. PMID 15697654. arXiv:cond-mat/0412658  . doi:10.1103/PhysRevE.71.016103.
^ Tishby, I.; Biham, O.; Katzav, E. The distribution of path lengths of self avoiding walks on Erdős–Rényi networks. Journal of Physics A: Mathematical and Theoretical. 2016, 49 (28): 285002. Bibcode:2016JPhA...49B5002T. arXiv:1603.06613  . doi:10.1088/1751-8113/49/28/285002.
^ ^4.0 ^4.1 Duminil-Copin, Hugo; Smirnov, Stanislav. The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt2}$. arXiv:1007.0575 [math-ph]. 2011-06-27.
^ S. Havlin, D. Ben-Avraham. New approach to self-avoiding walks as a critical phenomenon. J. Phys. A. 1982, 15 (6): L321–L328 [2020-02-10]. Bibcode:1982JPhA...15L.321H. doi:10.1088/0305-4470/15/6/013. （原始內容存檔於2020-09-22）.
^ S. Havlin, D. Ben-Avraham. Theoretical and numerical study of fractal dimensionality in self-avoiding walks. Phys. Rev. A. 1982, 26 (3): 1728–1734 [2020-02-10]. Bibcode:1982PhRvA..26.1728H. doi:10.1103/PhysRevA.26.1728. （原始內容存檔於2018-11-12）.
^ A. Bucksch, G. Turk, J.S. Weitz. The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion. PLOS ONE. 2014, 9 (1): e85585. Bibcode:2014PLoSO...985585B. PMC 3899046  . PMID 24465607. arXiv:1304.3521  . doi:10.1371/journal.pone.0085585.
^ Hayes B. How to Avoid Yourself (PDF). American Scientist. Jul–Aug 1998, 86 (4): 314 [2020-02-10]. doi:10.1511/1998.31.3301. （原始內容存檔 (PDF)於2020-09-28）.
^ Liśkiewicz M; Ogihara M; Toda S. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theoretical Computer Science. July 2003, 304 (1–3): 129–56. doi:10.1016/S0304-3975(03)00080-X.

閱讀

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

[1] P. Flory. Principles of Polymer Chemistry. Cornell University Press. 1953: 672. ISBN 9780801401343.

[2] Carlos P. Herrero. Self-avoiding walks on scale-free networks. Phys. Rev. E. 2005, 71 (3): 1728. Bibcode:2005PhRvE..71a6103H. PMID 15697654. arXiv:cond-mat/0412658  . doi:10.1103/PhysRevE.71.016103.

[3] Tishby, I.; Biham, O.; Katzav, E. The distribution of path lengths of self avoiding walks on Erdős–Rényi networks. Journal of Physics A: Mathematical and Theoretical. 2016, 49 (28): 285002. Bibcode:2016JPhA...49B5002T. arXiv:1603.06613  . doi:10.1088/1751-8113/49/28/285002.

[:0-4] 4.0 ^4.1 Duminil-Copin, Hugo; Smirnov, Stanislav. The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt2}$. arXiv:1007.0575 [math-ph]. 2011-06-27.

[5] S. Havlin, D. Ben-Avraham. New approach to self-avoiding walks as a critical phenomenon. J. Phys. A. 1982, 15 (6): L321–L328 [2020-02-10]. Bibcode:1982JPhA...15L.321H. doi:10.1088/0305-4470/15/6/013. （原始內容存檔於2020-09-22）.

[6] S. Havlin, D. Ben-Avraham. Theoretical and numerical study of fractal dimensionality in self-avoiding walks. Phys. Rev. A. 1982, 26 (3): 1728–1734 [2020-02-10]. Bibcode:1982PhRvA..26.1728H. doi:10.1103/PhysRevA.26.1728. （原始內容存檔於2018-11-12）.

[7] A. Bucksch, G. Turk, J.S. Weitz. The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion. PLOS ONE. 2014, 9 (1): e85585. Bibcode:2014PLoSO...985585B. PMC 3899046  . PMID 24465607. arXiv:1304.3521  . doi:10.1371/journal.pone.0085585.

[8] Hayes B. How to Avoid Yourself (PDF). American Scientist. Jul–Aug 1998, 86 (4): 314 [2020-02-10]. doi:10.1511/1998.31.3301. （原始內容存檔 (PDF)於2020-09-28）.

[9] Liśkiewicz M; Ogihara M; Toda S. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theoretical Computer Science. July 2003, 304 (1–3): 129–56. doi:10.1016/S0304-3975(03)00080-X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]