×

Reconstruction for the Potts model. (English) Zbl 1234.60095

An infinite rooted tree is considered where every vertex has \(d\) children. The spin \(\sigma_{\rho}\) on the root \(\rho\) is chosen from \({\mathcal C}=\{1,\ldots,q\}\) according to some initial distribution and then propagates along the edges of the tree according to a transition matrix \(M\) with \(M_{i,j}=M_{i,k}\) for \(j,k\in {\mathcal C}\setminus \{i\}\) and \(M_{i,i}=1-p\). The associated reconstruction problem naturally arises in computational biology, information theory and statistical physics. The most general result on the reconstruction problem is the Kesten-Stigum bound which states that a reconstruction problem is solvable when \(\lambda^2d>1\), where \(\lambda=1-pq/(q-1)\). The author proves the first exact reconstruction threshold in a nonbinary model establishing the Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree \(d\). He further establishes that the Kesten-Stigum bound is not tight for the \(q\)-state Potts model when \(q\geq 5\). In this case, he gives the precise asymptotics of the threshold for fixed \(q\) as \(d\) goes to infinity.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

References:

[1] Achlioptas, D. and Coja-Oghlan, A. (2008). Algorithmic barriers from phase transition. In Proceedinds of FOCS’ 08 793-802.
[2] Berger, N., Kenyon, C., Mossel, E. and Peres, Y. (2005). Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Related Fields 131 311-340. · Zbl 1075.60003 · doi:10.1007/s00440-004-0369-4
[3] Bhatnagar, N. and Maneva, E. (2010). A computational method for bounding the probability of reconstruction on trees. SIAM J. Discrete Math. · Zbl 1236.60092
[4] Bleher, P. M., Ruiz, J. and Zagrebnov, V. A. (1995). On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Statist. Phys. 79 473-482. · Zbl 1081.82515 · doi:10.1007/BF02179399
[5] Borgs, C., Chayes, J. T., Mossel, E. and Roch, S. (2006). The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels. In FOCS 518-530. IEEE Comput. Soc., Berkeley, CA.
[6] Chayes, J. T., Chayes, L., Sethna, J. P. and Thouless, D. J. (1986). A mean field spin glass with short-range interactions. Comm. Math. Phys. 106 41-89. · doi:10.1007/BF01210926
[7] Daskalakis, C., Mossel, E. and Roch, S. (2006). Optimal phylogenetic reconstruction. In STOC’ 06: Proceedings of the 38 th Annual ACM Symposium on Theory of Computing 159-168. ACM, New York. · Zbl 1301.92054
[8] Dyer, M., Frieze, A., Hayes, T. P. and Vigoda, E. (2004). Randomly coloring constant degree graphs. In FOCS ’ 04: Proceedings of the 45 th Annual IEEE Symposium on Foundations of Computer Science ( FOCS’ 04) 582-589. IEEE Computer Society, Washington, DC. · Zbl 1272.05045
[9] Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (2000). Broadcasting on trees and the Ising model. Ann. Appl. Probab. 10 410-433. · Zbl 1052.60076 · doi:10.1214/aoap/1019487349
[10] Formentin, M. and Külske, C. (2009). On the purity of the free boundary condition Potts measure on random trees. Stochastic Process. Appl. 119 2992-3005. · Zbl 1181.60147 · doi:10.1016/j.spa.2009.03.008
[11] Gerschenfeld, A. and Montanari, A. (2007). Reconstruction for models on random graphs. In 48 th Annual Symposium on Foundations of Computer Science . Providence, RI.
[12] Ioffe, D. (1996). On the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys. 37 137-143. · Zbl 0848.60090 · doi:10.1007/BF00416016
[13] Kesten, H. and Stigum, B. P. (1966). Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Statist. 37 1463-1481. · Zbl 0203.17402 · doi:10.1214/aoms/1177699139
[14] Krza\ogonek kała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G. and Zdeborová, L. (2007). Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA 104 10318-10323 (electronic). · Zbl 1190.68031 · doi:10.1073/pnas.0703685104
[15] Martinelli, F., Sinclair, A. and Weitz, D. (2007). Fast mixing for independent sets, colorings, and other models on trees. Random Structures Algorithms 31 134-172. · Zbl 1138.82020 · doi:10.1002/rsa.20132
[16] Mézard, M. and Montanari, A. (2006). Reconstruction on trees and spin glass transition. J. Stat. Phys. 124 1317-1350. · Zbl 1113.82013 · doi:10.1007/s10955-006-9162-3
[17] Montanari, A., Restrepo, R. and Tetali, P. (2009). Reconstruction and clustering in random constraint satisfaction problems. Available at . · Zbl 1223.68077
[18] Mossel, E. (2001). Reconstruction on trees: Beating the second eigenvalue. Ann. Appl. Probab. 11 285-300. · Zbl 1021.90008 · doi:10.1214/aoap/998926994
[19] Mossel, E. (2004). Phase transitions in phylogeny. Trans. Amer. Math. Soc. 356 2379-2404 (electronic). · Zbl 1041.92018 · doi:10.1090/S0002-9947-03-03382-8
[20] Mossel, E. (2004). Survey: Information flow on trees. In Graphs , Morphisms and Statistical Physics. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 63 155-170. Amer. Math. Soc., Providence, RI. · Zbl 1066.94006
[21] Mossel, E. and Peres, Y. (2003). Information flow on trees. Ann. Appl. Probab. 13 817-844. · Zbl 1050.60082 · doi:10.1214/aoap/1060202828
[22] Mossel, E. and Sly, A. (2009). Gibbs rapidly samples colorings of g ( n , d / n ). Probab. Theory Related Fields 149 37-69. · Zbl 1213.05239 · doi:10.1007/s00440-009-0222-x
[23] Pollard, D. (1984). Convergence of Stochastic Processes . Springer, New York. · Zbl 0544.60045
[24] Semerjian, G. (2008). On the freezing of variables in random constraint satisfaction problems. J. Stat. Phys. 130 251-293. · Zbl 1139.82041 · doi:10.1007/s10955-007-9417-7
[25] Sly, A. (2009). Reconstruction of random colourings. Comm. Math. Phys. 288 943-961. · Zbl 1274.60163 · doi:10.1007/s00220-009-0783-7
[26] Zdeborová, L. and Krza\ogonek kała, F. (2007). Phase transitions in the coloring of random graphs. Phys. Rev. E (3) 76 031131, 29.
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.