自避行走

在數學中，自避行走（簡稱：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]

閱論編概率論：隨機過程
離散時間（英語：Discrete-time stochastic process）	伯努利過程分支過程中餐館過程高爾頓-沃特森過程（英語：Galton–Watson process）獨立同分布馬爾可夫鏈莫蘭過程（英語：Moran process）隨機漫步循環擦除隨機漫步（英語：Loop-erased）自避行走
連續時間	貝塞爾過程出生-死亡過程維納過程/布朗運動布朗橋 Excursion（英語：Brownian excursion）分數布朗運動（英語：Fractional Brownian motion）幾何布朗運動 Meander（英語：Brownian meander）柯西過程（英語：Cauchy process） Contact process（英語：Contact process (mathematics)） Cox process（英語：科克斯过程） Diffusion process（英語：Diffusion process） Empirical process（英語：Empirical process）費勒過程（英語：Feller process）弗萊明-維奧過程（英語：Fleming–Viot process）伽馬過程（英語：Gamma process）亨特過程（英語：Hunt process） Interacting particle system（英語：Interacting particle system）s 伊藤積分伊藤過程跳躍擴散（英語：Jump diffusion）跳躍過程萊維過程 Local time（英語：Local time (mathematics)）馬爾可夫加過程（英語：Markov additive process）麥基恩-弗拉索夫過程（英語：McKean–Vlasov process）奧恩斯坦-烏倫貝克過程泊松過程複合泊松過程（英語：Compound Poisson process）非齊次泊松過程泊松點過程施拉姆-勒夫納演進半鞅 Sigma-martingale（英語：Sigma-martingale） Stable process（英語：Stable process） Superprocess（英語：Superprocess） Telegraph process（英語：Telegraph process） Variance gamma process（英語：Variance gamma process）維納過程 Wiener sausage（英語：Wiener sausage）
離散時間與連續時間	分支過程高斯過程隱馬爾可夫模型（HMM）馬可夫過程鞅鞅差序列（英語：Martingale difference sequence）局部鞅（英語：Local martingale） Sub- Super-（英語：Super-） Random dynamical system（英語：Random dynamical system） Regenerative process（英語：Regenerative process） Renewal process（英語：Renewal process）白雜訊
場及其它	狄利克雷過程（英語：Dirichlet process）高斯隨機場（英語：Gaussian random field）吉布斯測度（英語：Gibbs measure）霍普菲爾德神經網絡易辛模型馬爾可夫網絡滲流理論皮特曼-約爾過程（英語：Pitman–Yor process）點過程 Cox（英語：Point process#Cox point process）泊松過程玻茨模型隨機場隨機圖
時間序列模型	ARCH模型 ARIMA模型自我迴歸模型 ARMA模型廣義ARCH模型移動平均模型
金融模型	布萊克-德爾曼-托伊模型（英語：Black–Derman–Toy model）布萊克-卡拉辛斯基模型（英語：Black–Karasinski model）布萊克-舒爾斯模型陳模型 Constant elasticity of variance (CEV)（英語：Constant elasticity of variance model）科克斯-英格索爾-羅斯模型 (CIR)（英語：Cox–Ingersoll–Ross model） Garman–Kohlhagen（英語：Garman–Kohlhagen model） HJM框架赫斯頓模型（英語：Heston model） Ho–Lee（英語：Ho–Lee model）赫爾-懷特模型 LIBOR市場模型（英語：LIBOR market model） SABR volatility（英語：SABR volatility model）瓦西塞克模型（英語：Vasicek model）
精算學	Bühlmann（英語：Bühlmann model） Cramér–Lundberg（英語：Cramér–Lundberg model） Risk process（英語：Risk process） Sparre–Anderson（英語：Sparre–Anderson model）
等候理論	Bulk（英語：Bulk queue） Fluid（英語：Fluid queue） Generalized queueing network（英語：G-network） M/G/1（英語：M/G/1 queue） M/M/1 M/M/c（英語：M/M/c queue）
性質	右連左極函數 Continuous（英語：Continuous stochastic process） Continuous paths（英語：Sample-continuous process）遍歷性 Exchangeable（英語：Exchangeable random variables） Feller-continuous（英語：Feller-continuous process） Gauss–Markov（英語：Gauss–Markov process）馬爾可夫性質 Mixing（英語：Mixing (mathematics)） Piecewise deterministic（英語：Piecewise deterministic Markov process）可預測過程循序可測過程 Self-similar（英語：Self-similar process）平穩過程 Time-reversible（英語：Time reversibility）
極限定理	中心極限定理 Donsker's theorem（英語：Donsker's theorem） Doob's martingale convergence theorems（英語：Doob's martingale convergence theorems）遍歷理論 Fisher–Tippett–Gnedenko theorem（英語：Fisher–Tippett–Gnedenko theorem） Large deviation principle（英語：Large deviation principle）大數法則重對數律 Maximal ergodic theorem（英語：Maximal ergodic theorem） Sanov's theorem（英語：Sanov's theorem）
不等式	Burkholder–Davis–Gundy（英語：Burkholder–Davis–Gundy inequalities） Doob's martingale（英語：Doob's martingale inequality） Kunita–Watanabe（英語：Kunita–Watanabe inequality）
工具	Cameron–Martin formula（英語：Cameron–Martin formula）隨機變量的收斂 Doléans-Dade exponential（英語：Doléans-Dade exponential） Doob decomposition theorem（英語：Doob decomposition theorem） Doob–Meyer decomposition theorem（英語：Doob–Meyer decomposition theorem） Doob's optional stopping theorem（英語：Doob's optional stopping theorem） Dynkin's formula（英語：Dynkin's formula）費曼-卡茨公式右連左極函數 Girsanov theorem（英語：Girsanov theorem） Infinitesimal generator（英語：Infinitesimal generator (stochastic processes)）伊藤積分伊藤引理 Kolmogorov continuity theorem（英語：Kolmogorov continuity theorem） Kolmogorov extension theorem（英語：Kolmogorov extension theorem） Lévy–Prokhorov metric（英語：Lévy–Prokhorov metric） Malliavin calculus（英語：Malliavin calculus） Martingale representation theorem（英語：Martingale representation theorem） Optional stopping theorem（英語：Optional stopping theorem） Prohorov theorem（英語：Prohorov theorem）二次變差 Reflection principle（英語：Reflection principle (Wiener process)） Skorokhod integral（英語：Skorokhod integral） Skorokhod's representation theorem（英語：Skorokhod's representation theorem）右連左極函數 Snell envelope（英語：Snell envelope）隨機微分方程 Tanaka（英語：Tanaka equation）停時隨機積分 Uniform integrability（英語：Uniform integrability） Usual hypotheses（英語：Usual hypotheses）維納空間 Classical（英語：Classical Wiener space） Abstract 漂移項
相關領域	精算學計量經濟學遍歷理論極值理論（EVT） Large deviations theory（英語：Large deviations theory）數理金融學數理統計學概率論等候理論 Renewal theory（英語：Renewal theory） Ruin theory（英語：Ruin theory）統計學隨機分析時間序列分析機器學習
分類