Exact sampling and fast mixing of Activated Random Walk

Abstract

Activated Random Walk (ARW) is an interacting particle system on the $d$-dimensional lattice ${\mathbb{Z}}^d$. On a finite subset $V\subset {\mathbb{Z}}^d$ it defines a Markov chain on $\{0,1{\}}^V$. We prove that when $V$ is a Euclidean ball intersected with ${\mathbb{Z}}^d$, the mixing time of the ARW Markov chain is at most $1+o(1)$ times the volume of the ball. The proof uses an exact sampling algorithm for the stationary distribution, a coupling with internal DLA, and an upper bound on the time when internal DLA fills the entire ball. We conjecture cutoff at time $\hat{I}\P$ times the volume of the ball, where $\hat{I}\P <1$ is the limiting density of the stationary state.

v3: final version for Electronic Journal of Probability