×

zbMATH — the first resource for mathematics

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.

MSC:
60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
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] van den Berg, J.: A uniqueness condition for Gibbs measures, with application to the 2-dimensional Ising antiferromagnet. Comm. Math. Phys. 152 (1), 161–166 (1993) · Zbl 0768.60098 · doi:10.1007/BF02097061
[3] Bleher, P.M., Ruiz, J., Zagrebnov, V.A.: On the purity of limiting Gibbs state for the Ising model on the Bethe lattice. J. Stat. Phys 79, 473–482 (1995) · Zbl 1081.82515 · doi:10.1007/BF02179399
[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, M., Greenhill, C.: On Markov chains for independent sets. J. Algor. 35, 17–49 (2000) · Zbl 0961.05063 · doi:10.1006/jagm.1999.1071
[8] Evans, W., Kenyon, C., Peres, Y., Schulman, L.J.: Broadcasting on trees and the Ising Model. Ann. Appl. Prob. 10, 410–433 (2000) · Zbl 1052.60076 · doi:10.1214/aoap/1019487349
[9] Fortuin, C.M., Kasteleyn, P.W.: On the random-cluster model. I. Introduction and relation to other models. Physica 57, 536–564 (1972)
[10] Fortuin, C.M., Kasteleyn, P.W., Ginibre, J.: Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22, 89–103 (1971) · Zbl 0346.06011 · doi:10.1007/BF01651330
[11] Haggstrom, O., Jonasson, J., Lyons, R.: Explicit isoperimetric constants and phase transitions in the random-cluster model. Ann. Probab. 30, 443–473 (2002) · Zbl 1025.60044 · doi:10.1214/aop/1020107775
[12] Ioffe, D.: A note on the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys. 37, 137–143 (1996) · Zbl 0848.60090 · doi:10.1007/BF00416016
[13] Janson, S., Luczak, T., Ruciński, A.: Random Graphs. Wiley, New York, 2000
[14] Jerrum, M.: A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Rand. Struc. Alg. 7, 157–165 (1995) · Zbl 0833.60070 · doi:10.1002/rsa.3240070205
[15] Jerrum, M., Sinclair, A.: Approximating the permanent. Siam J. Comput. 18, 1149–1178 (1989) · Zbl 0723.05107 · doi:10.1137/0218077
[16] Jerrum, M., Sinclair, A.: Polynomial time approximation algorithms for the Ising model. Siam J. Comput. 22, 1087–1116 (1993) · Zbl 0782.05076 · doi:10.1137/0222066
[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 · Zbl 1075.60003
[20] Kinnersley, N.G.: The vertex seperation number of a graph equals its path-width. Infor. Proc. Lett. 42, 345–350 (1992) · Zbl 0764.68121 · doi:10.1016/0020-0190(92)90234-M
[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, M., Vigoda, E.: Fast Convergence of the Glauber Dynamics for Sampling Independent Sets, Statistical physics methods in discrete probability, combinatorics and theoretical computer science. Rand. Struc. Alg. 15, 229–241 (1999) · Zbl 0941.65010 · doi:10.1002/(SICI)1098-2418(199910/12)15:3/4<229::AID-RSA3>3.0.CO;2-X
[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
[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, E.: Reconstruction on trees: Beating the second eigenvalue. Ann. Appl. Probab. 11 (1), 285–300 (2001) · Zbl 1021.90008 · doi:10.1214/aoap/998926994
[28] Mossel, E.: Recursive reconstruction on periodic trees. Rand. Struc. Alg. 13, 81–97 (1998) · Zbl 0959.05112 · doi:10.1002/(SICI)1098-2418(199808)13:1<81::AID-RSA5>3.0.CO;2-O
[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
[32] Propp, J., Wilson, D.: Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics. Rand. Struc. Alg. 9, 223–252 (1996) · Zbl 0859.60067 · doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O
[33] Peres, Y., Winkler, P.: In preparation, 2003
[34] Randall, D., Tetali, P.: Analyzing Glauber dynamics by comparison of Markov chains. J. Math. Phys. 41, 1598–1615 (2000) · Zbl 0974.60052 · doi:10.1063/1.533199
[35] Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory Series B 35, 39–61 (1983) · Zbl 0521.05062 · doi:10.1016/0095-8956(83)90079-5
[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, E.: Improved bounds for sampling colorings. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. J. Math. Phys. 41 (3), 1555–1569 (2001) · Zbl 0978.60083
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.