博碩士論文 107221601 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:18 、訪客IP:3.235.25.169
姓名 伊凱馬(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★ 曼德博集合、朱利亞集合與演算法
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 在本論文中,我們研究了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 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Con guration . . . . . . . . . . . . . . . . . . . . . . . . . 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
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明