Mixing Time for Ising Model (On Two Special Graphs: the Line and the Circle)

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：142

、訪客IP：3.140.198.173

姓名

伊凱馬(Badr Saleh Badr Mohamed Elkamash) 查詢紙本館藏

畢業系所

數學系

論文名稱

(Mixing Time for Ising Model (On Two Special Graphs: the Line and the Circle))

相關論文

★ A Primer on BMO	★ Markov Processes And Brownian Motion
★ Convergence rates of harmonic measures and extremal lengths of sets in the upper half plane	★ 曼德博集合、朱利亞集合與演算法
★ Some Properties of Dipolar SLE	★ 分數積分算子的一種雙線性形式
★ 一維和二維的标准以及條件隨機遊走的性質

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在本論文中，我們研究了Ising模型的Glauber動力學。基於[10]的專著，我們提供了馬爾可夫鏈混合時間一般理論的詳細介紹，尤其是收斂到平穩測度的速率。
然後，我們計算出Ising模型的兩個特殊（也許是最重要）案例的細節：直線和圓。
我們的貢獻是
（1）我們針對這兩種特殊情況獲得了改進的估計；和
（2）我們提供了許多細節和例子和圖片示例來說明該理論。
更詳細地，我們證明在高溫下快速混合。我們確定混合時間是log(n)和log(1/e)的多項式。或者，顯示tmix在log(n)也足以進行快速混合。我們證明了Glauber動力學的混合時間為在高溫下具有n個頂點的直線和圓上的（鐵磁）伊辛模型的上限為n log n/e。

摘要(英)

In this thesis we study Glauber dynamics of one dimensional Ising models. We provide a detailed presentation of the general theory of the mixing times of Markov chains, especially the rate of convergence to stationary measures, based on the monograph of [10].
Then we work out the details of two special (and perhaps the most important) cases of Ising models: the line and the circle. Our contribution is that
(1) we obtain improved estimates for these two special cases; and
(2) we provide many examples with details and pictures to illustrate the theory.
In more details, we prove a fast mixing at high temperature. We establish that the mixing time is a polynomial in log(n) and log(1/e). Alternatively, we show that tmix is a polynomial in log(n). It is also enough for fast mixing. We show that the mixing time of Glauber dynamics for the (ferromagnetic) Ising model on a line and a circle with n vertices at high temperature has an upper bound of n log n/e.

關鍵字(中)

★ 伊辛模型
★ 格勞伯動力
★ 混合時間
★ 馬爾可夫鏈
★ 路徑耦合

關鍵字(英)

★ Ising Model
★ Glauber Dynamics
★ Mixing Time
★ Markov Chains
★ Path Coupling

論文目次

Chinese Abstract i
English Abstract ii
Acknowledgement iii
Table of Contents v
List of Figures vi
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Our Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Convergence Theorem for Markov Chains 4
2.1 Basic Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Uniqueness of Stationary Distributions . . . . . . . . . . . . . . . . . . . . 6
2.3 Existence of Stationary Distributions . . . . . . . . . . . . . . . . . . . . . 8
2.4 The Convergence Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 The Mixing Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 The Ising Model 20
3.1 Ising Model on the Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Ising Model on the Circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 The Glauber Dynamics 25
4.1 Glauber Dynamics for Some Models . . . . . . . . . . . . . . . . . . . . . . 25
4.1.1 Graph Colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2 Hardcore Conguration . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.3 Hardcore Model with Fugacity . . . . . . . . . . . . . . . . . . . . . 28
4.2 The Glauber Dynamics for the Gibbs Distribution L . . . . . . . . . . . 30
5 The Path Coupling Technique 35
5.1 Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 The Transportation Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.3 Path Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6 Fast Mixing in Ising Model 47
6.1 On the Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.2 On the Circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
References 56

參考文獻

[1] E. Ising. Beitrag zur Theorie des Ferromagnetismus. Z. Physik, v.31, No.1 (1925),
253-258.
[2] Onsager, Lars. Crystal statistics. I. A two-dimensional model with an order-disorder
transition. Physical Review, v. 65, No. 3-4 (1944), 117.
[3] Kasteleyn, Pieter W. The statistics of dimers on a lattice: I. The number of dimer
arrangements on a quadratic lattice. Physica, v. 27, No. 12 (1961), 1209-1225.
[4] Temperley, Harold NV and Fisher, Michael E. Dimer problem in statistical
mechanics-an exact result. Philosophical Magazine, v. 6, No. 68 (1961), 1061-1063.
[5] Kasteleyn, Pieter W. Dimer statistics and phase transitions. Journal of Mathematical
Physics, v. 4, No. 2 (1963), 287-293.
[6] E. W. Montroll, R. B. Potts, and J. C. Ward. Correlations and Spontaneous Magne-
tization of the Two-Dimensional Ising Model. J. Math. Phys, v.4 (1963), 308.
[7] C. Thompson. Mathematical Statistical Mechanics. Princeton University Press
(1972).
[8] B. M. McCoy and T. T. Wu. The Two-Dimensional Ising Model. Harvard University
Press (1973).
[9] B. A. Cipra. An introduction to the Ising model. The American Mathematical
Monthly, v. 91, No. 10 (1987), 937-959.
[10] Levin, David A and Peres, Yuval. Markov chains and mixing times. American Mathematical
Soc. (2009).
[11] J. Ding, Y. Peres. Mixing time for the Ising model: A uniform lower bound for all
graphs. Annales de l′IHP Probabilites et statistiques, v. 47, No. 4 (2011), 1020-1028.
[12] J. Ding, E. Lubetzky, Y. Peres. The mixing time evolution of Glauber dynamics for
the mean-eld Ising model. Communications in Mathematical Physics, v. 289, No. 2
(2009), 725-764.
[13] Ycart, Bernard. Cuto for Markov chains: some examples and applications. Complex
Systems (2001), 261-300.
[14] Russ Bubley and Martin Dyer. Path coupling: A technique for proving rapid mixing
in markov chains. In Foundations of Computer Science. Proceedings., 38th Annual
Symposium on, 223-231. IEEE, (1997)
[15] T. P. Hayes. Local uniformity properties for Glauber dynamics on graph colorings.
Random Structures and Algorithms, v. 43, No. 2 (2013), 139-180.
[16] T. P. Hayes, E. Vigoda. Coupling with the stationary distribution and improved sam-
pling for colorings and independent sets. The Annals of Applied Probability, v. 16,
No. 3 (2006), 1297-1318.
[17] E. Lubetzky, A. Sly. Cuto for the Ising model on the lattice. Inventiones mathematicae,
v. 191, No. 3 (2013), 719-755.
[18] A. Frieze, E. Vigoda. A survey on the use of Markov chains to randomly sample
colorings. (2005)
[19] A. Bianchi, F. Martinelli. Mixing time for Glauber dynamics beyond Zd. (2006)
[20] P. Tetali, J. C. Vera, E. Vigoda and L. Yang. Phase transition for the mixing time
of the Glauber dynamics for coloring regular trees. Proceedings of the twenty-rst
annual ACM-SIAM symposium on Discrete algorithms .SIAM. (2010)1646-1656.
[21] H. Nooitgedagt. Two convergence limits of Markov chains: Cut-o and Metastability
(2010)
[22] J. Ding. Mixing time for the Ising model and random walks. (2011)
[23] A. Codello. Chapter 5 Ising model and phase transitions. (2015)
[24] A. Freedman. Convergence theorem for nite Markov chains. (2017)
[25] D. Cordaro. Makov chains and coupling from the past. (2017)
[26] E. Shang. Introduction to Markov chains and Markov chain mixing. (2018)
[27] N. Berestycki. Mixing Times of Markov Chains Techniques and Examples. Notes
(2016)
[28] P. Sousi. Mixing times of Markov chains. Notes (2020)
[29] S.G. Brush. History of the Lenz-Ising Model. Reviews of modern physics, v. 39, No.
4 (1967), 883.

指導教授

方向(Xiang Fang)

審核日期

2020-7-7

推文