Mixing time bounds for oriented kinetically constrained spin models

Paul Chleboun (University of Warwick)
Fabio Martinelli (Università Roma Tre)


We analyze the mixing time of a class of oriented kinetically constrained spin models (KCMs) on a d-dimensional lattice of n sites. A typical example is the North-East model, a 0-1 spin system on the two-dimensional integer lattice that evolves according to the following rule: whenever a site’s southerly and westerly nearest neighbours have spin 0, with rate one it resets its own spin by tossing a p-coin, at all other times its spin remains frozen. Such models are very popular in statistical physics because, in spite of their simplicity, they display some of the key features of the dynamics of real glasses. We prove that the mixing time is O(n log n) whenever the relaxation time is O(1). Our study was motivated by the “shape” conjecture put forward by G. Kordzakhia and S.P. Lalley.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-9

Publication Date: July 12, 2013

DOI: 10.1214/ECP.v18-2516


  • Aldous, David; Diaconis, Persi. The asymmetric one-dimensional constrained Ising model: rigorous results. J. Statist. Phys. 107 (2002), no. 5-6, 945--975. MR1901508
  • Bhatnagar, Nayantara; Caputo, Pietro; Tetali, Prasad; Vigoda, Eric. Analysis of top-swap shuffling for genome rearrangements. Ann. Appl. Probab. 17 (2007), no. 4, 1424--1445. MR2344312
  • Oriane Blondel. Front progression for the East model. arXiv.org, math.PR, December 2012.
  • Cancrini, N.; Martinelli, F.; Roberto, C.; Toninelli, C. Kinetically constrained spin models. Probab. Theory Related Fields 140 (2008), no. 3-4, 459--504. MR2365481
  • Caputo, Pietro; Lubetzky, Eyal; Martinelli, Fabio; Sly, Allan; Toninelli, Fabio Lucio. The shape of the $(2+1)\roman{d}$ SOS surface above a wall. C. R. Math. Acad. Sci. Paris 350 (2012), no. 13-14, 703--706. MR2971384
  • Caputo, Pietro; Martinelli, Fabio; Toninelli, Fabio Lucio. Convergence to equilibrium of biased plane partitions. Random Structures Algorithms 39 (2011), no. 1, 83--114. MR2839986
  • Chung, Fan; Diaconis, Persi; Graham, Ronald. Combinatorics for the East model. Adv. in Appl. Math. 27 (2001), no. 1, 192--206. MR1835679
  • R. Durrett. Lecture notes on particle systems and percolation. Lecture Notes in Mathematics, (1608), 1995.
  • Durrett, Richard. Oriented percolation in two dimensions. Ann. Probab. 12 (1984), no. 4, 999--1040. MR0757768
  • Faggionato, A.; Martinelli, F.; Roberto, C.; Toninelli, C. Aging through hierarchical coalescence in the East model. Comm. Math. Phys. 309 (2012), no. 2, 459--495. MR2864800
  • A. Faggionato, F. Martinelli, C. Roberto, and C. Toninelli. Universality in one dimensional hierarchical coalescence processes. Ann. Probab., 40(4):1377--1435, 2012.
  • Kordzakhia, George; Lalley, Steven P. Ergodicity and mixing properties of the northeast model. J. Appl. Probab. 43 (2006), no. 3, 782--792. MR2274800
  • Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937
  • Liggett, Thomas M. Interacting particle systems. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 276. Springer-Verlag, New York, 1985. xv+488 pp. ISBN: 0-387-96069-4 MR0776231
  • Liggett, Thomas M. Stochastic interacting systems: contact, voter and exclusion processes. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 324. Springer-Verlag, Berlin, 1999. xii+332 pp. ISBN: 3-540-65995-1 MR1717346
  • F~Martinelli and C~Toninelli. Kinetically constrained spin models on trees. Annals of Applied Probability, in press, 2012.
  • Roberto Oliveira. Mixing and hitting times for finite markov chains. Electron. J. Probab., 17, 2012.
  • Y~Peres and A~Sly. Mixing of the upper triangular matrix walk. Probability Theory and Related Fields, pages 1--11, 2011.
  • Yuval Peres and Perla Sousi. Mixing times are hitting times of large sets. 2011.
  • F. Ritort and P. Sollich. Glassy dynamics of kinetically constrained models. Advances in Physics, 52(4):219--342, 2003.
  • Saloff-Coste, Laurent. Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996), 301--413, Lecture Notes in Math., 1665, Springer, Berlin, 1997. MR1490046
  • P. Sollich and M.R. Evans. Glassy dynamics in the asymmetrically constrained kinetic ising chain. Phys. Rev. E, page 031504, 2003.
  • Toninelli, Cristina; Biroli, Giulio. A new class of cellular automata with a discontinuous glass transition. J. Stat. Phys. 130 (2008), no. 1, 83--112. MR2375957
  • Valiant, Paul. Linear bounds on the North-East model and higher-dimensional analogs. Adv. in Appl. Math. 33 (2004), no. 1, 40--50. MR2064356

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.