(3.238.130.97) 您好!臺灣時間:2021/05/13 23:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:伊凱馬
研究生(外文):Badr Saleh Badr Mohamed Elkamash
論文名稱(外文):Mixing Time for Ising Model (On Two Special Graphs: the Line and the Circle)
指導教授:方向方向引用關係
指導教授(外文):Xiang Fang
學位類別:碩士
校院名稱:國立中央大學
系所名稱:數學系
學門:數學及統計學門
學類:數學學類
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:67
中文關鍵詞:伊辛模型格勞伯動力混合時間馬爾可夫鏈路徑耦合
外文關鍵詞:Ising ModelGlauber DynamicsMixing TimeMarkov ChainsPath Coupling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:39
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
在本論文中,我們研究了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.
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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔