Universality of the mean-field for the Potts model
Tóm tắt
We consider the Potts model with q colors on a sequence of weighted graphs with adjacency matrices
$$A_n$$
, allowing for both positive and negative weights. Under a mild regularity condition on
$$A_n$$
we show that the mean-field prediction for the log partition function is asymptotically correct, whenever
$${{\mathrm{tr}}}(A_n^2)=o(n)$$
. In particular, our results are applicable for the Ising and the Potts models on any sequence of graphs with average degree going to
$$+\infty $$
. Using this, we establish the universality of the limiting log partition function of the ferromagnetic Potts model for a sequence of asymptotically regular graphs, and that of the Ising model for bi-regular bipartite graphs in both ferromagnetic and anti-ferromagnetic domain. We also derive a large deviation principle for the empirical measure of the colors for the Potts model on asymptotically regular graphs.
Tài liệu tham khảo
Anandkumar, A., Tan, V., Huang, F., Willsky, A.: High-dimensional structure estimation in Ising models: local separation criterion. Ann. Stat. 40(3), 1346–1375 (2012)
Bayati, M., Gamarnik, D., Tetali, P.: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Ann. Probab. 41(6), 4080–4115 (2013)
Bai, Z.D.: Methodologies in spectral analysis of large-dimensional random matrices, a review (with discussion). Stat. Sin. 9(3), 611–662 (1999)
Bento, J., Montanari, A.: Which graphical models are difficult to learn? Neural Inf. Process. Syst. 22, 1303–1311 (2009)
Bhattacharya, B., Mukherjee, S.: Inference in Ising model (2015, preprint). arXiv:1507.07055
Biskup, M., Chayes, L.: Rigorous analysis of discontinuous phase transitions via mean-field bounds. Commun. Math. Phys. 238(1), 53–93 (2003)
Blanchard, P., Gandolfo, D., Ruiz, J., Wouts, M.: Thermodynamic vs topological phase transition: cusp in the Kertéz line. Europhys. Lett. 82(5), 50003 (2008)
Borgs, C., Chayes, J., Cohn, H., Zhao, Y.: An \(L_p\) theory of sparse convergence I: limits, sparse random graph models, and power law distributions (preprint). http://yufeizhao.com/papers/2014-LpLimit1
Borgs, C., Chayes, J., Cohn, H., Zhao, Y.: An \(L_p\) theory of sparse convergence II: LD convergence, quotients, and right convergence (preprint). http://yufeizhao.com/papers/2014-LpLimit2
Borgs, C., Chayes, J., Lovász, L., Sós, V.T., Vesztergombi, K.: Convergent sequences of dense graphs I: subgraph frequencies, metric properties and testing. Adv. Math. 219, 1801–1851 (2009)
Borgs, C., Chayes, J., Lovász, L., Sós, V.T., Vesztergombi, K.: Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. Math. 176, 151–219 (2012)
Bresler, G.: Efficiently learning Ising models on arbitrary graphs. Symposium on Theory of Computing (STOC), pp. 771–782 (2015)
Cant, A., Pearce, P.A.: Mean-field limits of the quantum Potts model. Commun. Math. Phys. 90(3), 373–383 (1983)
Chandler, D.: Introduction to Modern Statistical Mechanics. Oxford University Press, Oxford (1987)
Chatterjee, S.: Estimation in spin glasses: a first step. Ann. Stat. 35(5), 1931–1946 (2007)
Chatterjee, S., Dembo, A.: Nonlinear large deviations. Adv. Math. (to appear) arXiv:1401.3495v5
Coja-Oghlan, A., Lanka, A.: The spectral gap of random graphs with given expected degrees. Electron. J. Combin. 16(1), R138 (2009)
Costeniuc, M., Ellis, R.S., Touchette, H.: Complete analysis of phase transitions and ensemble equivalence for the Curie–Weiss–Potts model. J. Math. Phys. 46(6), 063301 (2005)
Chung, F., Lu, L., Vu, V.: The spectra of random graphs with given expected degrees. J. Internet Math. 1(3), 257–275 (2003)
Dembo, A., Montanari, A.: Ising models on locally tree-like graphs. Ann. Appl. Probab. 20(2), 565–592 (2010)
Dembo, A., Montanari, A.: Gibbs measures and phase transitions on sparse random graphs. Br. J. Probab. Stat. 24(2), 137–211 (2010)
Dembo, A., Montanari, A., Sen, S.: Extremal cuts of sparse random graphs. Ann. Probab. (to appear). arXiv:1503.03923
Dembo, A., Montanari, A., Sun, N.: Factor models on locally tree-like graphs. Ann. Probab. 41(6), 4162–4213 (2013)
Dembo, A., Montanari, A., Sly, A., Sun, N.: The replica symmetric solution for Potts models on d-regular graphs. Commun. Math. Phys. 327(2), 551–575 (2014)
Dembo, A., Zeitouni, O.: Large Deviations Techniques and Applications, vol. 38. Springer, Berlin (2009)
Dommers, S., Giardinà, C., van der Hofstad, R.: Ising models on power-law random graphs. J. Stat. Phys. 141(4), 638–660 (2010)
Eichelsbacher, P., Martschink, B.: On rates of convergence in the Curie–Weiss Potts model with an external field. Annales de I’Insitut Henri Poincaré Probabilités et Statistiques 51(1), 252–282 (2015)
Ellis, R.S., Newman, M.E.: The statistics of Curie–Weiss models. J. Stat. Phys. 19(2), 149–161 (1978)
Ellis, R.S., Wang, K.: Limit theorems for the empirical vector of the Curie–Weiss–Potts model. Stochastic Process. Appl. 35(1), 59–79 (1990)
Ellis, R.S., Wang, K.: Limit theorems for maximum likelihood estimators in the Curie–Weiss–Potts model. Stochastic Process. Appl. 40(2), 251–288 (1992)
Gamarnik, D.: Correlation decay method for decision, optimization, and inference in large-scale networks. Tutorials in Operations Research, INFORMS (2013)
Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs. Random Struct. Algorithms 27(2), 251–275 (2005)
Hopfield, J.: Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. 79(8), 2554–2558 (1982)
Ising, E.: Beitrag zur theorie der ferromagnetismus. Z. Phys. 31(1), 253–258 (1925)
Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22(5), 1087–1116 (1993)
Krivelevich, M., Sudakov, B.: The largest eigenvalue of sparse random graphs. Combin. Probab. Comput. 12(1), 61–72 (2003)
Lovász, L.: Large Networks and Graph Limits, vol. 60. AMS, Providence (2012)
Parisi, G.: Statistical Field Theory. Addison-Wesley, New York (1988)
Milman, V.D., Schechtman, G.: Asymptotic theory of finite-dimensional normed spaces. Lecture Notes in Mathematics, vol. 1200. Springer, Berlin (1986)
Niss, M.: History of the Lenz-Ising model 1920–1950: from ferromagnetic to cooperative phenomena. Archi. Hist. Exact Sci. 59(3), 267–318 (2005)
Potts, R.: Some generalized order-disorder transformations. Math. Proc. Camb. Philos. Soc. 48(1), 106–109 (1952)
Ravikumar, P., Wainwright, M.J., Lafferty, J.: High-dimensional Ising model selection using \(\ell _1\)-regularized logistic regression. Ann. Stat. 38(3), 1287–1319 (2010)
Sherrington, D., Kirkpatrick, S.: Solvable model of a spin-glass. Phys. Rev. Lett. 35(26), 1792–1796 (1975)
Sly, A., Sun, N.: Counting in two-spin models on \(d\)-regular graphs. Ann. Probab. 42(6), 2383–2416 (2014)
Talagrand, M.: The Parisi formula. Ann. Math. 163(2), 221–263 (2006)
Wainwright, M.J., Jaakkola, T.S., Willsky, A.S.: A new class of upper bounds on the log partition function. IEEE Trans. Inf. Theory 51(7), 2313–2335 (2005)
Wu, F.Y.: The Potts model. Rev. Modern Phys. 54(1), 235 (1982)