Glauber dynamics on trees and hyperbolic graphs. (English) Zbl 1075.60003
The main goal of the paper is to determine which geometric properties of a graph are most relevant to the mixing rate of the Glauber dynamics on particale systems. The paper contains six sections. In Section 2.1 a connection between the geometry of a graph and mixing time of Glauber dynamics on it is described. In Sections 2.3–4 Glauber dynamics for the Ising model on regular trees is studied. For these trees it is shown that the mixing time is polynomial at all temperatures, the range of temperatures for which the spectral gap is bounded away from zero is characterized. It is proven that on infinite regular trees, there is a range of temperatures in which the inverse spectral gap is bounded, even though there are many different Gibbs measures. In Section 5 Glauber dynamics for families of finite graphs of bounded degree are studied. Section 6 contains relevant problems that are open.
Reviewer: Utkir Rozikov (Tashkent)
References:
| [1] | Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs. Book in preparation 2000, Current version available at http://www.stat.berkeley.edu/users/aldous/book.html |
| [2] | Berg, Comm. Math. Phys., 152, 161 (1) |
| [3] | Bleher, J. Stat. Phys, 79, 473 (1995) · Zbl 1081.82515 |
| [4] | Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in Markov chains. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 1997, pp. 223-231 |
| [5] | Chen, M.F.: Trilogy of couplings and general formulas for lower bound of spectral gap. Probability towards 2000, Lecture Notes in Statist., 128, Springer, New York, 1998, pp. 123-136 · Zbl 1044.60513 |
| [6] | Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York, 1991 · Zbl 0762.94001 |
| [7] | Dyer, J. Algor., 35, 17 (2000) · Zbl 0961.05063 |
| [8] | Evans, Ann. Appl. Prob., 10, 410 (2000) · Zbl 1052.60076 |
| [9] | Fortuin, I. Introduction and relation to other models. Physica, 57, 536 (1972) |
| [10] | Fortuin, Comm. Math. Phys., 22, 89 (1971) · Zbl 0346.06011 |
| [11] | Haggstrom, Ann. Probab., 30, 443 (2002) |
| [12] | Ioffe, Lett. Math. Phys., 37, 137 (1996) · Zbl 0848.60090 |
| [13] | Janson, S., Luczak, T., Ruciński, A.: Random Graphs. Wiley, New York, 2000 · Zbl 0968.05003 |
| [14] | Jerrum, Rand. Struc. Alg., 7, 157 (1995) · Zbl 0833.60070 |
| [15] | Jerrum, Siam J. Comput., 18, 1149 (1989) · Zbl 0723.05107 |
| [16] | Jerrum, Siam J. Comput., 22, 1087 (1993) · Zbl 0782.05076 |
| [17] | Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Crete, Greece, 2001 · Zbl 1323.68571 |
| [18] | Katok, S.: Fuchsian Groups. University of Chicago Press, 1992 · Zbl 0753.30001 |
| [19] | Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs. 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 568-578 |
| [20] | Kinnersley, Infor. Proc. Lett., 42, 345 (1992) · Zbl 0764.68121 |
| [21] | Liggett, T.: Interacting particle systems. Springer, New York, 1985 · Zbl 0559.60078 |
| [22] | Luby, M., Vigoda, E.: Approximately Counting Up To Four. In: proceedings of the 29th Annual Symposium on Theory of Computing (STOC), 1997, pp. 682-687 · Zbl 0963.68150 |
| [23] | Luby, Rand. Struc. Alg., 15, 229 (1999) |
| [24] | Magnus, W.: Noneuclidean tessellations and their groups. Academic Press, New York and London, 1974 · Zbl 0293.50002 |
| [25] | Martinelli, F.: Lectures on Glauber dynamics for discrete spin models. Lectures on probability theory and statistics (Saint-Flour, 1997) Lecture Notes in Math. 1717, Springer, Berlin, 1998, pp. 93-191 · Zbl 1051.82514 |
| [26] | Martinelli, F., Sinclair, A., Weitz, D.: Glauber dynamics on trees: Boundary conditions and mixing time. Preprint 2003, available at http://front.math.ucdavis.edu/math.PR/0307336 · Zbl 1076.82010 |
| [27] | Mossel, Ann. Appl. Probab., 11, 285 (1) · Zbl 1021.90008 |
| [28] | Mossel, Rand. Struc. Alg., 13, 81 (1998) · Zbl 0959.05112 |
| [29] | Mossel, E., Peres Y.: Information flow on trees. To appear in Ann. Appl. Probab., 2003 · Zbl 1050.60082 |
| [30] | Nacu, S.: Glauber dynamics on the cycle is monotone. To appear, Probab. Theory Related Fields, 2003 · Zbl 1068.82014 |
| [31] | Paterson, A.L.T.: Amenability. American Mathematical Soc., Providence, 1988 · Zbl 0648.43001 |
| [32] | Propp, Rand. Struc. Alg., 9, 223 (1996) |
| [33] | Peres, Y., Winkler, P.: In preparation, 2003 |
| [34] | Randall, J. Math. Phys., 41, 1598 (2000) · Zbl 0974.60052 |
| [35] | Robertson, I. Excluding a forest. J. Comb. Theory Series B, 35, 39 (1983) · Zbl 0521.05062 |
| [36] | Saloff-Coste, L.: Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996) Lecture Notes in Math. 1665, Springer, Berlin, 1997, pp. 301-413 · Zbl 0885.60061 |
| [37] | Vigoda, Probabilistic techniques in equilibrium and nonequilibrium statistical physics. J. Math. Phys., 41, 1555 (3) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
