Mixing times for a constrained Ising process on the torus at low density

Abstract

We study a kinetically constrained Ising process (KCIP) associated with a graph G and density parameter p; this process is an interacting particle system with state space {0, 1}G. The stationary distribution of the KCIP Markov chain is the Binomial(|G|,p) distribution on the number of particles, conditioned on having at least one particle. The ‘constraint’ in the name of the process refers to the rule that a vertex cannot change its state unless it has at least one neighbour in state ‘1’. The KCIP has been proposed by statistical physicists as a model for the glass transition, and more recently as a simple algorithm for data storage in computer networks. In this note, we study the mixing time of this process onthetorusG=Zd,d≥3,inthelow-densityregimep= c forarbitrary0<c<∞;this L |G|regime is the subject of a conjecture of Aldous and is natural in the context of computer networks. Our results provide a counterexample to Aldous’ conjecture, suggest a natural modification of the conjecture, and show that this modification is correct up to logarithmic factors. The methods developed in this paper also provide a strategy for tackling Aldous’ conjecture for other graphs.