# Separation cutoff for Activated Random Walks

Alexandre Bristiel (ENS Lyon) and Justin Salez (Paris-Dauphine)

###### Abstract

We consider Activated Random Walks on arbitrary finite networks, with
particles being inserted at random and absorbed at the boundary. Despite the
non-reversibility of the dynamics and the lack of knowledge on the stationary
distribution, we explicitly determine the relaxation time of the process, and
prove that separation cutoff is equivalent to the product condition. We also
provide sharp estimates on the center and width of the cutoff window. Finally,
we illustrate those results by establishing explicit separation cutoffs on
various networks, including: (i) large finite subgraphs of any fixed infinite
non-amenable graph, with absorption at the boundary and (ii) large finite
vertex-transitive graphs with absorption at a single vertex. The latter result
settles a conjecture of Levine and Liang. Our proofs rely on the refined
analysis of a strong stationary time recently discovered by Levine and Liang
and involving the IDLA process.

###### Contents

  1. 1 Introduction
    1. 1.1 Background and motivation
    2. 1.2 Setup
    3. 1.3 Main results
    4. 1.4 Examples
    5. 1.5 Implications for total-variation distance
  2. 2 Proofs
    1. 2.1 Reduction to IDLA
    2. 2.2 Monotonicity and concavity
    3. 2.3 Proof of Theorem 1
    4. 2.4 Proof of Theorem 2
    5. 2.5 Proof of Theorem 3

##  1 Introduction

###  1.1 Background and motivation

Introduced a decade ago by Rolla and Sidoravicius [20], the _Activated Random
Walks_ (ARW) process has quickly become the best candidate in the fascinating
quest for a universal model of _self-organized criticality_ [8, 9, 18, 17]. In
a nutshell, this interacting particle system involves two species called
_active_ and _sleeping_ : active particles perform random walks and fall
asleep at a constant rate $\lambda\in(0,\infty)$, while sleeping particles
become active upon contact with another particle. On an infinite transitive
graph $\mathbb{G}$ such as $\mathbb{\mathbb{Z}}^{d}$, a central question is
that of _stabilization_ : if we start with one active particle at the origin
and a Bernoulli($\zeta$) configuration of sleeping particles, will the active
species almost-surely die out? Rolla, Sidoravicius and Zindy [21] showed the
existence of a critical density $\zeta_{c}=\zeta_{c}(\mathbb{G})$ below which
the answer is yes and above which it is no. This phase transition is moreover
known to be non-trivial (i.e., $0<\zeta_{c}<1$) for many transitive graphs
[24], including $\mathbb{Z}^{d}$ for all $d\geq 1$ [25, 12, 10]. We refer to
the survey [19] for additional details and references.

The present paper is concerned with the much less understood _finitary setup_
, recently considered by Basu, Ganguly, Hoffman and Richey [3] or Levine and
Liang [15]. Specifically, we restrict the ARW dynamics to a large but finite
domain $V$ in $\mathbb{G}$ and kill any particle that exits $V$. Clearly, if
we add an active particle to a configuration of sleeping particles, then the
process will eventually stabilize to a new, random configuration of sleeping
particles almost-surely. Iterating this procedure gives rise to a natural
Markov chain on sleeping configurations, whose behavior is expected to be
closely related to that of the unrestricted dynamics on $\mathbb{G}$. In
particular, it is believed to exhibit the following form of self-organized
criticality: in a suitable double limit where both the number of iterations
and the size of the domain $V$ tend to infinity, the proportion of occupied
sites in $V$ should spontaneously concentrate around the critical value
$\zeta_{c}(\mathbb{G})$ for stabilization on the infinite graph $\mathbb{G}$.
Even more remarkably, the worst-case total-variation distance to equilibrium
of the chain is expected to drop abruptly from $1-o(1)$ to $o(1)$ (a phase
transition known as a _cutoff_) as the number of steps passes the critical
threshold $|V|(\zeta_{c}(\mathbb{G})+o(1))$. See the recent work [15] and the
forthcoming paper [16] for details.

Motivated by those fascinating predictions, we here investigate the mixing
properties of the above Markov chain on arbitrary finite networks, when
convergence to equilibrium is measured in the (stronger) _separation
distance_. In particular, we explicitly determine the relaxation time, we
obtain sharp bounds on the separation mixing time, and we completely
characterize the occurrence of a separation cutoff. Finally, we illustrate
those results by establishing explicit cutoffs on various concrete geometries.
Before we can state our precise results, let us define our setup more
formally.

###  1.2 Setup

#### Geometry.

Throughout the paper, $V$ is a finite set whose elements are called _sites_.
The geometry of our model is specified by a _sub-stochastic matrix_ on $V$,
i.e., a function $K\colon V^{2}\to[0,1]$ such that

$\displaystyle\forall x\in V,\quad\sum_{y\in V}K(x,y)$ $\displaystyle\leq$
$\displaystyle 1.$

The latter naturally describes the evolution of a _killed random walk_
(henceforth referred to as a $K-$walk) which, when alive at a site $x\in V$,
jumps to a new site $y\in V$ at rate $K(x,y)$ and is killed at rate
$1-\sum_{y\in V}K(x,y)$. We will always assume that the matrix $K$ is _non-
degenerate_ in the sense that no principal sub-matrix of $K$ is stochastic:
this guarantees that the $K-$walk is killed eventually almost-surely,
regardless of where it starts. Here is a simple generic example to keep in
mind, and to which we shall come back later.

######  Example 1 (Restriction of an infinite graph).

Let $\mathbb{G}=(V_{\mathbb{G}},E_{\mathbb{G}})$ be a locally finite, infinite
connected graph, and let $P_{\mathbb{G}}\colon V^{2}_{\mathbb{G}}\to[0,1]$
denote the associated random-walk transition matrix, i.e.

$\displaystyle P_{\mathbb{G}}(x,y)$ $\displaystyle:=$
$\displaystyle\left\\{\begin{array}[]{ll}\frac{1}{\deg(x)}&\textrm{ if
}\\{x,y\\}\in E_{\mathbb{G}}\\\ 0&\textrm{else}.\end{array}\right.$

Now, choose a finite set $V\subseteq V_{\mathbb{G}}$. Then, the restriction
$K:=P_{\mathbb{G}}[V]$ of $P_{\mathbb{G}}$ to $V^{2}$ is a non-degenerate sub-
stochastic matrix, which describes the evolution of a random walk on
$\mathbb{G}$ killed upon exiting $V$.

#### Dynamics.

The instantaneous state of our interacting particle system is described by a
_configuration_ $\eta\in\\{0,{\rm{s}},1,2,\ldots\\}^{V}$, with the following
interpretation: each site $x\in V$ is either empty ($\eta(x)=0$), or occupied
by a single _sleeping_ particle ($\eta(x)={\rm{s}}$), or occupied by an
arbitrary number $k\geq 1$ of _active_ particles ($\eta(x)=k$). Given a
parameter $\lambda\in(0,\infty)$, we then consider the following continuous-
time Markovian evolution on the space of configurations:

  * •

active particles perform independent $K-$walks, but fall asleep at rate
$\lambda$ when alone on a site;

  * •

sleeping particles do not move, but become active upon contact with another
particle.

Note that any configuration $\eta$ without active particles (i.e.,
$\eta\in\\{0,{\rm{s}}\\}^{V}$) is stable under this dynamics. In fact, our
non-degeneracy assumption on $K$ guarantees that the process will eventually
be absorbed in such a stable configuration almost-surely, from any initial
configuration. This random procedure is called _stabilization_. Note that it
may significantly reduce the total number of particles in the system, but can
not augment it. Following [15], we now compensate it with a simple insertion
mechanism to define an ergodic Markov chain on stable configurations.

#### The ${\rm ARW}(K,\lambda,\nu)$ chain.

Fix a probability distribution $\nu$ on $V$ whose support intersects every
connected component of $K$, so that every site has a chance of being visited
by a $K-$walk starting from $\nu$. A natural example to keep in mind is of
course the uniform law on $V$, henceforth denoted by $\mathcal{U}(V)$ or
simply $\mathcal{U}$. Finally, consider the discrete-time Markov chain on the
set $\mathcal{X}:=\\{0,{\rm{s}}\\}^{V}$ which, at each step, turns the current
state $\eta$ into a new, random state $\xi$ as follows:

  1. 1.

make $\eta$ unstable by adding one active particle at a $\nu-$distributed
random site;

  2. 2.

run the ARW dynamics to obtain a (random) stable configuration $\xi$.

Write $P\colon\mathcal{X}^{2}\to[0,1]$ for the corresponding transition
matrix. Our assumptions on the parameters $(K,\lambda,\nu)$ guarantee that $P$
is irreducible and aperiodic. In particular, we have

$\displaystyle\forall\eta,\eta^{\prime}\in\mathcal{X},\qquad
P^{t}\left(\eta,\eta^{\prime}\right)$
$\displaystyle\xrightarrow[t\to\infty]{}$ $\displaystyle\pi(\eta^{\prime}),$
(2)

where $\pi=\pi P$ denotes the unique invariant distribution of the chain. We
note that the latter is far from explicit, and that very little is known about
it, despite fascinating predictions [15, 16]. We are here interested in the
speed at which the convergence (2) occurs. Formalizing this requires a few
definitions, which we now briefly recall. We refer the unfamiliar reader to
the book [14] for details.

#### Separation distance, relaxation time and mixing time.

There are many natural ways to measure the distance to equilibrium of a Markov
chain at a given time $t\in\mathbb{N}$. We will here focus on the so-called
_separation distance_ (see Section 1.5 for a comparison with the total-
variation distance):

$\displaystyle{\rm d}_{{\textsc{sep}}}(t)$ $\displaystyle:=$
$\displaystyle\max_{\eta,\eta^{\prime}\in\mathcal{X}}\left(1-\frac{P^{t}(\eta,\eta^{\prime})}{\pi(\eta^{\prime})}\right).$

The function ${\rm d}_{{\textsc{sep}}}\colon\mathbb{N}\to[0,1]$ is non-
increasing, with ${\rm d}_{{\textsc{sep}}}(0)=1$ and ${\rm
d}_{{\textsc{sep}}}(+\infty)=0$. In our case, it is moreover sub-
multiplicative (see Lemma 2 below). By Gelfand’s formula, we classically have

$\displaystyle\left({\rm d}_{{\textsc{sep}}}(t)\right)^{1/t}\
\xrightarrow[t\to\infty]{}\ \rho,\ $ where $\displaystyle\rho\ :=\
\max\left\\{|z|\colon z\in\mathbb{C}\setminus\\{1\\}\textrm{ is an eigenvalue
of }P\right\\}.$ (3)

In light of this, a first natural time-scale for the Markov chain is the so-
called _relaxation time_ :

$\displaystyle{\rm t}_{\textsc{rel}}$ $\displaystyle:=$
$\displaystyle\frac{1}{1-\rho}.$

This “near-equilibrium” parameter has, however, very little to say about the
early behavior of the chain, because the geometric decay ${\rm
d}_{{\textsc{sep}}}(t)\approx\rho^{t}$ promised by (3) is only valid in the
$t\to\infty$ limit. In the “far-from-equilibrium” regime, a more appropriate
time-scale is the (separation) _mixing time_ :

$\displaystyle{\rm t}_{\textsc{sep}}(\varepsilon)$ $\displaystyle:=$
$\displaystyle\inf\\{t\in\mathbb{N}\colon{\rm
d}_{{\textsc{sep}}}(t)\leq\varepsilon\\}.$

The default value for the precision parameter $\varepsilon\in(0,1)$ is $1/2$,
in which case we simply write ${\rm t}_{\textsc{sep}}={\rm
t}_{\textsc{sep}}(1/2)$. Note that replacing $1/2$ with any smaller value
$\varepsilon$ can not increase ${\rm t}_{\textsc{sep}}$ by more than the
multiplicative factor $\log_{2}\left(\frac{1}{\varepsilon}\right)$, thanks to
the sub-multiplicativity of ${\rm d}_{{\textsc{sep}}}$.

###  1.3 Main results

The high-level message of our paper is that the mixing behavior of the ${\rm
ARW}(K,\lambda,\nu)$ chain is essentially dictated by a very simple single-
particle statistics, namely, the hitting probabilities

$\displaystyle p(x)$ $\displaystyle:=$
$\displaystyle{\mathbf{P}}_{\nu}\left(\tau_{x}<\tau_{\dagger}\right),\quad
x\in V.$ (4)

Here and throughout the paper, we use the notation ${\mathbf{P}}_{\nu}$ for
the law of a $K-$walk with initial distribution $\nu$ (henceforth referred to
as a $(K,\nu)-$walk), and write $\tau_{\dagger}$ for its life-time and
$\tau_{x}$ for the hitting time of $x$. Intuitively, a small value of $p(x)$
means that the site $x$ is poorly connected. The presence of such “remote
sites” constitutes a natural obstruction to mixing, because a particle
sleeping there may have to wait for a very long time before being activated.
Perhaps surprisingly, our results below will show that this is the main
obstruction to mixing.

######  Remark 1 (Reversible network).

There is a useful alternative expression for $p(x)$ in the case where

$\displaystyle\forall x,y\in V,\quad\nu(y)K(y,x)$ $\displaystyle=$
$\displaystyle\nu(x)K(x,y).$ (5)

Indeed, this identity remains true if we replace $K$ with the Green’s function
$\mathcal{G}=I+K+K^{2}+\cdots$, and we may then divide through by
$\mathcal{G}(x,x)$ and sum over all $y\in V$ to arrive at the identity

$\displaystyle\forall x\in V,\quad p(x)$ $\displaystyle=$
$\displaystyle\frac{\nu(x){\mathbf{E}}_{x}[\tau_{\dagger}]}{\mathcal{G}(x,x)}.$

Note that the detailed balance condition (5) always holds in Example 1, with
$\nu(x)\propto\deg(x)$.

#### Relaxation time.

Our first main result is the exact determination of the relaxation time of the
${\rm ARW}(K,\lambda,\nu)$ chain in full generality, and despite the total
lack of reversibility of the dynamics.

######  Theorem 1 (Relaxation time).

The relaxation time of the ${\rm ARW}(K,\lambda,\nu)$ chain is exactly given
by

$\displaystyle{\rm t}_{\textsc{rel}}$ $\displaystyle=$
$\displaystyle\left(\min_{x\in V}p(x)\right)^{-1}.$

#### Window and cutoff.

Our second main result concerns the _cutoff phenomenon_ , a remarkable phase
transition in the convergence to equilibrium of certain processes [6].
Specifically, a sequence of ergodic Markov chains (indexed by $n$) exhibits a
separation cutoff if for any fixed $\alpha\geq 0$,

$\displaystyle{\rm d}_{{\textsc{sep}}}^{(n)}\left(\lfloor\alpha{\rm
t}_{\textsc{sep}}^{(n)}\rfloor\right)$
$\displaystyle\xrightarrow[n\to\infty]{}$
$\displaystyle\left\\{\begin{array}[]{ll}1&\textrm{ if }\alpha<1\\\ 0&\textrm{
if }\alpha>1.\end{array}\right.$

An equivalent formulation is that the time-scale over which the distance to
equilibrium drops from near $1$ to near $0$ (known as the _mixing window_) is
much smaller than the center of the window, i.e.

$\displaystyle\forall\varepsilon\in(0,1/2),\quad{\rm
t}_{\textsc{sep}}^{(n)}(\varepsilon)-{\rm
t}_{\textsc{sep}}^{(n)}(1-\varepsilon)$ $\displaystyle=$ $\displaystyle
o\left({\rm t}_{\textsc{sep}}^{(n)}\right).$

Here and throughout the paper, we use the standard notations $a_{n}=o(b_{n})$,
$a_{n}=\Omega(b_{n})$ and $a_{n}=O(b_{n})$ to respectively mean that the
sequence $({a_{n}}/{b_{n}})_{n\geq 1}$ vanishes as $n\to\infty$, is bounded
away from $0$, and is bounded away from $+\infty$. Establishing a cutoff is a
notoriously delicate task, which a priori requires the determination of ${\rm
t}_{\textsc{sep}}^{(n)}(\varepsilon)$ within a multiplicative precision
$1+o(1)$. A well-known simple necessary condition is the so-called _product
condition_ :

$\displaystyle{\rm t}_{\textsc{rel}}^{(n)}$ $\displaystyle=$ $\displaystyle
o\left({\rm t}_{\textsc{sep}}^{(n)}\right).$ (7)

Unfortunately, the latter is too weak to guarantee cutoff in general (see [14,
Example 18.7] for a generic counter-example). Nevertheless, the condition (7)
has been shown to guarantee separation cutoff for birth-and-death chains [7],
and for exclusion processes with reservoirs [22]. Our second main result adds
all ARW chains to this short list, and provides an estimate on the mixing
window.

######  Theorem 2 (Mixing window and cutoff).

For any $\varepsilon\in(0,1/2)$, the ${\rm ARW}(K,\lambda,\nu)$ chain
satisfies

$\displaystyle{\rm t}_{\textsc{sep}}(\varepsilon)-{\rm
t}_{\textsc{sep}}(1-\varepsilon)$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{8{\rm t}_{\textsc{rel}}{\rm
t}_{\textsc{sep}}}{\varepsilon}}.$

In particular, a sequence of ${\rm ARW}$ chains exhibits cutoff if and only if
it satisfies (7).

#### Mixing time.

Our third main result is a two-sided estimate on the mixing time of the ${\rm
ARW}(K,\lambda,\nu)$ chain, which will be shown to be sharp in many concrete
examples. The estimate involves two simple statistics $\mathcal{L}$ and
$\mathcal{R}$, which are related to the hitting probabilities $(p(x)\colon
x\in V)$ as follows:

$\displaystyle\mathcal{L}\ :=\ \left(\frac{1}{|V|}{\sum_{x\in
V}p(x)}\right)^{-1},$ $\displaystyle\mathcal{R}\ :=\ |V|\max_{x\in
V}\left\\{\frac{{\mathbf{P}}_{\mathcal{U}}(\tau_{x}<\tau_{\dagger})}{p(x)}\right\\}.$

Observe that the sum $\sum_{x\in V}p(x)$ is exactly the expected _range_
(number of distinct visited vertices) of a $(K,\nu)-$walk, and is thus at most
the expected life-time ${\mathbf{E}}_{\nu}[\tau_{\dagger}]$. In other words,

$\displaystyle\mathcal{L}$ $\displaystyle\geq$
$\displaystyle\frac{|V|}{{\mathbf{E}}_{\nu}[\tau_{\dagger}]}.$ (8)

Note also that the parameter $\mathcal{R}$ compares the actual hitting
probabilities $(p(x)\colon x\in V)$ with those that would be obtained if $\nu$
was the uniform law $\mathcal{U}$. In particular, we have $\mathcal{R}=|V|$
when $\nu=\mathcal{U}$.

######  Theorem 3 (Sharp mixing-time estimates).

We have $\mathcal{L}\ \leq{\rm t}_{\textsc{rel}}\leq\ \mathcal{R}$ and

$\displaystyle\max\left\\{{\rm
t}_{\textsc{rel}},|V|,\frac{\mathcal{L}\log|V|}{5}\right\\}\ \leq$
$\displaystyle{\rm t}_{\textsc{sep}}$ $\displaystyle\leq\
\left(\sqrt{\mathcal{R}}+3\sqrt{{\rm t}_{\textsc{rel}}\log|V|}\right)^{2}.$

Those lower and upper bounds match in the following two generic situations:
for each $n\geq 1$, consider an ${\rm ARW}(K_{n},\lambda_{n},\nu_{n})$ chain
and write ${\rm t}_{\textsc{rel}}^{(n)},{\rm
t}_{\textsc{sep}}^{(n)},\mathcal{R}^{(n)},\mathcal{L}^{(n)}$ for the
associated statistics.

  * •

If $\mathcal{L}^{(n)},\mathcal{R}^{(n)}=\Theta(|V_{n}|)$, then ${\rm
t}_{\textsc{rel}}^{(n)}=\Theta(|V_{n}|)$ and ${\rm
t}_{\textsc{sep}}^{(n)}=\Theta\left(|V_{n}|\log|V_{n}|\right)$.

  * •

If $\nu_{n}=\mathcal{U}(V_{n})$ and ${\rm
t}_{\textsc{rel}}^{(n)}=o\left(\frac{|V_{n}|}{\log|V_{n}|}\right)$, then ${\rm
t}_{\textsc{sep}}^{(n)}=|V_{n}|+o(|V_{n}|)$.

Let us now illustrate those results by providing explicit cutoffs on several
concrete geometries.

###  1.4 Examples

#### Non-amenable graphs.

Our first application concerns the setup of Example 1. Let $\mathbb{G}$ be an
infinite graph with bounded degrees, and recall that $\mathbb{G}$ is called
_non-amenable_ (see, e.g., [26]) if

$\displaystyle\inf\left\\{\frac{|\partial V|}{|V|}\colon V\subseteq
V_{\mathbb{G}},\quad 0<|V|<\infty\right\\}$ $\displaystyle>$ $\displaystyle
0.$

where $\partial V$ is the set of vertices in $V_{\mathbb{G}}\setminus V$
having a neighbor in $V$. A simple example is the infinite $3-$regular tree.
By virtue of Cheeger inequalities, non-amenability translates into the
existence of a spectral gap for the random-walk operator $P_{\mathbb{G}}$:
there exists $\gamma_{\mathbb{G}}\in(0,1)$ such that

$\displaystyle\sum_{x,y\in
V_{\mathbb{G}}}\deg(x)P_{\mathbb{G}}^{t}(x,y)f(x)f(y)$ $\displaystyle\leq$
$\displaystyle(1-\gamma_{\mathbb{G}})^{t}\sum_{x\in
V_{\mathbb{G}}}\deg(x)f^{2}(x),$

for any $t\in\mathbb{N}$ and any function $f\colon
V_{\mathbb{G}}\to\mathbb{R}$ such that the right-hand side is finite. Taking
$f={\bf 1}_{V}$ for some finite set $V\subseteq V_{\mathbb{G}}$, we deduce
that the random walk started from the degree-biased law
$\nu(x)\propto\deg(x){\bf 1}_{V}(x)$ and killed upon exiting $V$ satisfies

$\displaystyle{\mathbf{E}}_{\nu}\left[\tau_{\dagger}\right]$
$\displaystyle\leq$ $\displaystyle\frac{1}{\gamma_{\mathbb{G}}}.$

We may then replace $\nu$ with the uniform law $\mathcal{U}$ by paying a
factor equal to the maximum degree of $\mathbb{G}$. In view of (8) and
Theorems 2 and 3, we deduce the following general result.

######  Corollary 1 (Cutoff on non-amenable graphs).

Let $\mathbb{G}=(\mathbb{V},\mathbb{E})$ be an infinite non-amenable graph
with bounded degrees. For each $n\geq 1$, choose an arbitrary $n-$element
subset $V_{n}\subseteq\mathbb{V}$, and set $K_{n}=P_{\mathbb{G}}[V_{n}]$,
$\nu_{n}=\mathcal{U}(V_{n})$, and $\lambda_{n}\in(0,\infty)$. Then, the ${\rm
ARW}(K_{n},\lambda_{n},\nu_{n})$ chain satisfies

$\displaystyle{\rm t}_{\textsc{rel}}^{(n)}\ =\ \Theta(n),$ $\displaystyle{\rm
t}_{\textsc{sep}}^{(n)}\ =\ \Theta(n\log n),$

and there is a separation cutoff with window $O(n\sqrt{\log n})$.

#### Vertex-transitive graphs with a sink.

Our second application confirms a conjecture of Levine and Liang [15,
Conjecture 9]. Let $G$ be a finite connected graph. Recall that $G$ is
_vertex-transitive_ if for any vertices $x,y\in V_{G}$, there is an edge-
preserving bijection $\phi\colon V_{G}\to V_{G}$ that maps $x$ to $y$. In
words, $G$ “looks the same from every vertex”. Under this assumption, various
random-walk statistics admit considerably simplified expressions, as recorded
by Aldous [1]. In particular, Proposition 3 therein states that the random
walk on $G$ started from the uniform law satisfies

$\displaystyle{\mathbb{P}}\left(\tau_{x}<\tau_{z}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2},$

for any $x\neq z\in V_{G}$. Note that the left-hand side is exactly
$\frac{|V_{G}|-1}{|V_{G}|}p(x)$, where $p(x)$ is the hitting probability of
$x$ by a random walk starting from $\nu=\mathcal{U}(V_{G}\setminus\\{z\\})$
and killed upon hitting $z$.

######  Corollary 2 (Cutoff on transitive graphs with a sink).

For each $n\in\mathbb{N}$, let $G_{n}$ be a connected vertex-transitive graph
on $n+1$ vertices, and let $V_{n}$ be obtained by removing one vertex. Take
$K_{n}=P_{G_{n}}[V_{n}]$, $\nu_{n}=\mathcal{U}(V_{n})$ and
$\lambda_{n}\in(0,\infty)$. Then, the ${\rm ARW}(K_{n},\lambda_{n},\nu_{n})$
chain satisfies

$\displaystyle{\rm t}_{\textsc{rel}}^{(n)}\ =\ \frac{2n}{n+1},$
$\displaystyle{\rm t}_{\textsc{sep}}^{(n)}\ =\ n+o(n),$

and there is a separation cutoff with window $O(\sqrt{n})$.

#### Wheel-like graphs.

Our third application is motivated by the following example of Levine and
Liang: start from the $n-$cycle on $V_{n}=[n]$, and connect all sites to an
extra vertex called the _sink_. Write $K_{n}$ for the transition matrix of
random walk killed upon hitting the sink, and set $\nu=\mathcal{U}(V_{n})$ and
$\lambda_{n}\in(0,\infty)$. Then [15, Proposition 8] states that the ${\rm
ARW}(K_{n},\nu_{n},\lambda_{n})$ chain satisfies

$\displaystyle{\rm t}_{\textsc{sep}}^{(n)}$ $\displaystyle=$
$\displaystyle\Omega\left(\frac{n\log n}{\log\log n}\right).$

Now, observe that the life-time of a $(K,\nu)-$walk is here a geometric
variable with mean $3$, hence $\mathcal{L}^{(n)}\geq n/3$. Moreover,
$\mathcal{R}^{(n)}=n$ because $\nu_{n}$ is uniform. Thus, our general results
imply that in fact, ${\rm t}_{\textsc{sep}}^{(n)}=\Theta(n\log n)$ and ${\rm
t}_{\textsc{rel}}^{(n)}=\Theta(n)$, and that there is a separation cutoff with
window $O(n\sqrt{\log n})$. Moreover, the same argument applies to any
bounded-degree graph instead of the cycle.

######  Corollary 3 (Cutoff on wheel-like graphs).

Fix $d\in\mathbb{N}$. For each $n\geq 1$, let $G_{n}$ be a graph on $n+1$
vertices with one vertex of degree $n$ (the “sink”) and all others of degree
at most $d$. Let $V_{n}$ be the set obtained by removing the sink, and set
$K_{n}=P_{G_{n}}[V_{n}]$, $\nu_{n}=\mathcal{U}(V_{n})$ and
$\lambda_{n}\in(0,\infty)$. Then,

$\displaystyle{\rm t}_{\textsc{rel}}^{(n)}\ =\ \Theta(n),$ $\displaystyle{\rm
t}_{\textsc{sep}}^{(n)}\ =\ \Theta(n\log n),$

and there is a separation cutoff with window $O(n\sqrt{\log n})$.

#### Discrete Euclidean balls.

Finally, let us revisit the important case of discrete Euclidean balls
analyzed by Levine and Liang in [15]. Consider the setup of Example 1 where
the ambient graph $\mathbb{G}$ is the $d-$dimensional Euclidean lattice
$\mathbb{Z}^{d}$, and where the finite domain $V$ is the ball

$\displaystyle V_{n}$ $\displaystyle:=$
$\displaystyle\left\\{x\in\mathbb{Z}^{d}\colon x_{1}^{2}+\cdots+x_{d}^{2}\leq
n\right\\}.$

Choose $\nu_{n}:=\mathcal{U}(V_{n})$ and note that the reversibility condition
in Remark 1 holds. Consequently, classical Green’s function estimates show
that $\min_{x\in V_{n}}p(x)\geq\frac{c_{d}}{g_{d}(n)}$, where $c_{d}>0$ is a
constant and

$\displaystyle g_{d}(n)$ $\displaystyle:=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\textrm{if }d=1;\\\ n\log
n&\textrm{if }d=2;\\\ n^{d-1}&\textrm{if }d\geq 3.\end{array}\right.$

Thus, the ${\rm ARW}(V_{n},\lambda_{n},\nu_{n})$ chain satisfies ${\rm
t}_{\textsc{rel}}^{(n)}=O\left(g_{d}(n)\right)$. Keeping in mind that
$|V_{n}|=\Theta(n^{d})$, we deduce that ${\rm
t}_{\textsc{rel}}^{(n)}=o\left(\frac{|V_{n}|}{\log(V_{n})}\right)$ in all
dimensions, hence the following result.

######  Corollary 4 (Cutoff on Euclidean balls).

The ${\rm ARW}(V_{n},\lambda_{n},\nu_{n})$ chain described above satisfies

$\displaystyle{\rm t}_{\textsc{rel}}^{(n)}\ =\ O\left(g_{d}(n)\right),$
$\displaystyle{\rm t}_{\textsc{sep}}^{(n)}=|V_{n}|+o(|V_{n}|),$

and there is a separation cutoff with window $O(\sqrt{n^{d}g_{d}(n)}).$

###  1.5 Implications for total-variation distance

Let us finally discuss what our results imply for the more standard _total-
variation mixing time_ :

$\displaystyle{\rm t}_{\textsc{mix}}(\varepsilon)\ :=\
\min\left\\{t\in\mathbb{N}\colon{\rm
d}_{\textsc{tv}}(t)\leq\varepsilon\right\\},$ where $\displaystyle{\rm
d}_{\textsc{tv}}(t)\ :=\
\max_{\eta\in\mathcal{X},A\subseteq\mathcal{X}}\left|P^{t}(\eta,A)-\pi(A)\right|.$

We first note that the asymptotic behavior (3) remains valid in total
variation, so that Theorem 1 also characterizes the asymptotic behavior of the
function $t\mapsto{\rm d}_{\textsc{tv}}(t)$. Moreover, we always have ${\rm
d}_{\textsc{tv}}(t)\leq{\rm d}_{{\textsc{sep}}}(t)$ (see, e.g., [14, Lemma
6.16]), so the upper bound in Theorem 3 also applies to ${\rm
t}_{\textsc{mix}}$. Although the converse relation fails for non-reversible
chains, the lower bound ${\rm t}_{\textsc{mix}}\geq{\rm t}_{\textsc{rel}}$
remains valid, as it follows from the sub-multiplicativity of $t\mapsto 2{\rm
d}_{{\textsc{sep}}}(t)$. Let us sum this up.

######  Corollary 5 (Total-variation mixing time).

For ARWchains we always have

$\displaystyle{\rm t}_{\textsc{rel}}\ \leq$ $\displaystyle{\rm
t}_{\textsc{mix}}$ $\displaystyle\leq\ \left(\sqrt{\mathcal{R}}+3\sqrt{{\rm
t}_{\textsc{rel}}\log|V|}\right)^{2}.$

Regarding total-variation cutoff, we recall that the latter implies ${\rm
t}_{\textsc{rel}}^{(n)}=o({\rm t}_{\textsc{mix}}^{(n)})$, which in turns
implies ${\rm t}_{\textsc{rel}}^{(n)}=o({\rm t}_{\textsc{sep}}^{(n)})$ and
hence separation cutoff, by our Theorem 2. This result is non-trivial, in the
sense that it does not hold for general chains [11]. We thus record it here.

######  Corollary 6 (Total-variation cutoff implies separation cutoff).

If a sequence of ${\rm ARW}$ chains exhibits total-variation cutoff, then it
also exhibits separation cutoff.

Finally, we note that that the total-variation and separation distances become
equivalent if the sleeping rate is large enough. Indeed, it is not hard to see
that

$\displaystyle\sup_{t\in\mathbb{N}}\left|1-\frac{{\rm
d}_{\textsc{tv}}(t)}{{\rm d}_{{\textsc{sep}}}(t)}\right|$ $\displaystyle\leq$
$\displaystyle\frac{|V|}{1+\lambda}.$

######  Corollary 7 (Deep-sleep regime).

In the regime $\lambda_{n}\gg|V_{n}|$, the various examples of separation
cutoffs presented above extend to total-variation cutoffs, with the same
locations and windows.

Of course, establishing total-variation cutoff for a fixed sleeping rate
$\lambda\in(0,\infty)$ in any of the examples presented above remains a
challenging open problem, and we once again refer the interested reader to the
fascinating predictions formulated in [15, 16].

##  2 Proofs

The remainder of the paper is organized as follows. In Section 2.1, we build
on the work of Levine and Liang [15] to reduce the study of Activated Random
Walks to that of Internal Diffusion Limited Aggregation. In Section 2.2, we
construct a Markovian grand coupling of the latter with two crucial
properties: monotonicity, and a kind of concavity. Finally we use those
properties to establish Theorems 1, 2 and 3 in Section 2.3, 2.4 and 2.5
respectively.

###  2.1 Reduction to IDLA

The starting point of our analysis is a beautiful connection, recently
uncovered by Levine and Liang [15], between the mixing properties of the ${\rm
ARW}(K,\lambda,\nu)$ chain and the filling time of a classical growth model
known as _Internal Diffusion Limited Aggregation_ (IDLA) [5]. The latter may
be thought of as the $\lambda\to\infty$ limit of the ${\rm ARW}$ chain, where
active particles instantaneously fall asleep when alone on a site. More
formally, the ${\rm IDLA}(K,\nu)$ process is the discrete-time Markov chain
$(\mathcal{S}_{t})_{t\geq 0}$ on subsets of $V$ constructed as follows: let
$W_{1},W_{2},\ldots$ be a sequence of i.i.d. $(K,\nu)-$walks, and let
$\mathcal{S}_{0}\subseteq\mathcal{S}_{1}\subseteq\mathcal{S}_{2}\ldots$ be
defined inductively by $\mathcal{S}_{0}:=\emptyset$ and
$\mathcal{S}_{t}:=f\left(\mathcal{S}_{t-1},W_{t}\right)$, where

$\displaystyle f\left(S,(x_{0},\ldots,x_{r})\right)$ $\displaystyle:=$
$\displaystyle\left\\{\begin{array}[]{ll}S\cup\\{x_{k}\\}&\textrm{if
}k=\min\\{i\leq r\colon x_{i}\notin S\\}\textrm{ exists;}\\\
S&\textrm{otherwise.}\end{array}\right.$ (12)

In words, particles enter the system one after the other and, upon arrival,
each performs a $(K,\nu)-$walk until it dies or hits a previously unoccupied
site, where it settles forever. The main quantity of interest for us will be
the so-called _filling time_

$\displaystyle T$ $\displaystyle:=$
$\displaystyle\min\\{t\in\mathbb{N}\colon\mathcal{S}_{t}=V\\},$

which is almost-surely finite by our running assumptions on $(K,\nu)$. It
turns out that the tail of $T$ controls the distance to equilibrium of the ARW
chain. More precisely, Levine and Liang [15] observed that under a natural
coupling due to Shellef [23], the filling time of ${\rm IDLA}(K,\nu)$ is
actually a _strong stationary time_ for the ${\rm ARW}(K,\lambda,\nu)$ chain,
implying (see [14, Chapter 6]) the bound

$\displaystyle\forall t\in\mathbb{N},\qquad{\rm d}_{{\textsc{sep}}}(t)$
$\displaystyle\leq$ $\displaystyle{\mathbb{P}}\left(T>t\right).$

Our only contribution in this section is the observation that the strong
stationary time $T$ is in fact _optimal_ , in the sense that the above
inequality is an equality.

######  Proposition 1 (ARW vs IDLA).

For any choice of the parameters $(K,\lambda,\nu)$, we have

$\displaystyle\forall t\in\mathbb{N},\qquad{\rm d}_{{\textsc{sep}}}(t)$
$\displaystyle=$ $\displaystyle{\mathbb{P}}\left(T>t\right).$

###### Proof.

We only briefly revisit the coupling argument used by Levine and Lieng, and
refer to [15] for more details. We will denote by $\bf 0$ (resp. $\bf 1$,
resp. $\rm\bf s$) the configuration in which all entries are equal to $0$
(resp. $1$, resp. ${\rm{s}}$). An elementary but crucial property of ARW
stabilization is that it can be performed sequentially, by selecting an
arbitrary active particle at each step and letting it execute a random
transition (moving, dying, or falling sleep) with the appropriate
distribution, until no active particle remains. The key point is that the rule
used for selecting active particles is irrelevant: this is the so-called
_Abelian property_ (see [20, 4, 15] for details). In particular, in order to
stabilize a configuration $\eta\in\\{0,1,{\rm{s}},2,3,\ldots\\}^{V}$, we may
proceed in two stages as follows:

  1. (i)

Only select particles which are not alone on their sites, until some
$\zeta\in\\{0,{\rm{s}},1\\}^{V}$ is reached.

  2. (ii)

Stabilize $\zeta$ to produce the desired stable configuration
$\xi\in\\{0,{\rm{s}}\\}^{V}$.

Note that Stage (i) preserves the coordinate-wise order on configurations
induced by the natural single-site ordering $0\preceq{\rm{s}}\preceq 1\preceq
2\preceq\ldots$. More precisely, under an obvious coupling, we have

$\displaystyle\eta\preceq\eta^{\prime}$ $\displaystyle\Longrightarrow$
$\displaystyle\zeta\preceq\zeta^{\prime}.$ (13)

In particular, on the event $\\{\zeta={\bf 1}\\}$, we must also have
$\zeta^{\prime}={\bf 1}$ and hence $\xi^{\prime}=\xi$. This insensitivity to
the initial condition easily implies (see the proof of [15, Theorem 1] for
details) that

$\displaystyle\emph{{the conditional distribution of $\xi$ given $\\{\zeta=\bf
1\\}$ is exactly the stationary law $\pi$}}.$ (14)

Now, fix $t\in\mathbb{N}$ and an initial stable configuration
$\eta\in\\{0,{\rm{s}}\\}^{V}$. Thanks to the Abelian property, we may generate
a random configuration $\xi_{t}$ with law $P^{t}(\eta,\cdot)$ as follows: we
first make $\eta$ unstable by independently inserting $t$ active particles
according to $\nu$, and we then run the two-stage stabilization process
described above to produce $\zeta_{t}\in\\{0,{\rm{s}},1\\}^{V}$ and
$\xi_{t}\in\\{0,{\rm{s}}\\}^{V}$. Writing ${\mathbb{P}}_{\eta}$ to explicitate
the dependency in the initial condition $\eta$, we then have for any
$\eta^{\prime}\in\\{0,{\rm{s}}\\}^{V}$,

$\displaystyle P^{t}(\eta,\eta^{\prime})$ $\displaystyle=$
$\displaystyle{\mathbb{P}}_{\eta}\left(\xi_{t}=\eta^{\prime}\right)$
$\displaystyle\geq$ $\displaystyle{\mathbb{P}}_{\eta}\left(\zeta_{t}={\bf
1},\xi_{t}=\eta^{\prime}\right)$ $\displaystyle=$
$\displaystyle{\mathbb{P}}_{\eta}\left(\zeta_{t}={\bf
1}\right)\pi(\eta^{\prime})$ $\displaystyle\geq$
$\displaystyle{\mathbb{P}}_{\bf 0}\left(\zeta_{t}={\bf
1}\right)\pi(\eta^{\prime})$

where we have used (14) and then (13). Moreover, the first inequality is an
equality in the special case $(\eta,\eta^{\prime})=(\bf 0,{\rm\bf s})$,
because no particle can fall asleep during Stage (i) and the number of
particles can not increase during Stage (ii). Also, the second inequality is
trivially an equality when $\eta=\bf 0$. Recalling the definition of ${\rm
d}_{{\textsc{sep}}}(t)$, we have thus shown that

$\displaystyle{\rm d}_{{\textsc{sep}}}(t)$ $\displaystyle=$ $\displaystyle
1-\frac{{P^{t}(\bf 0},{\rm\bf s})}{\pi({\rm\bf s})}\ =\ {\mathbb{P}}_{\bf
0}\left(\zeta_{t}\neq{\bf 1}\right).$

This is the desired identity, because under the initial condition $\eta=\bf
0$, the random configuration $\zeta_{t}$ is distributed exactly as ${\bf
1}_{\mathcal{S}_{t}}$. To see this, simply recall the $\lambda\to\infty$
interpretation of ${\rm IDLA}(K,\nu)$, and observe that sending
$\lambda\to\infty$ in the two-stage stabilization process does not affect
$\zeta_{t}$ (no particle can fall asleep during Stage (i)) but reduces
$\xi_{t}$ to the unique stable configuration with the same support as
$\zeta_{t}$ (no particle has time to move or die during Stage (ii)). ∎

###  2.2 Monotonicity and concavity

In view of Proposition 1, we may now completely forget our ${\rm
ARW}(K,\nu,\lambda)$ chain, and focus on a new problem of independent
interest: understanding the distribution of the filling time of the ${\rm
IDLA}(K,\nu)$ process. To this end, it will be convenient to consider multiple
IDLA chains starting from all possible initial conditions and coupled by using
the same sequence $W_{1},W_{2},\ldots$ of i.i.d. $(K,\nu)$-walks. More
precisely, for each $A\subseteq V$, we define $(\mathcal{S}^{A}_{t})_{t\geq
0}$ inductively by

$\displaystyle\mathcal{S}_{0}^{A}$ $\displaystyle:=$ $\displaystyle A$
$\displaystyle\mathcal{S}_{t}^{A}$ $\displaystyle:=$ $\displaystyle
f\left(\mathcal{S}_{t-1}^{A},W_{t}\right)\textrm{ for }t\geq 1,$

where $f$ is the update function defined at (12). We then consider the
associated filling time:

$\displaystyle T^{A}$ $\displaystyle:=$ $\displaystyle\inf\\{t\geq
0\colon\mathcal{S}_{t}^{A}=V\\}.$

In particular, $T^{V}=0$ and for any $x\in V$, the random variable
$T^{V\setminus\\{x\\}}$ is just the number of independent $(K,\nu)$-walks that
one needs to sample in order to hit $x$, i.e.

$\displaystyle T^{V\setminus\\{x\\}}$ $\displaystyle\sim$
$\displaystyle\textrm{Geometric}(p(x)).$ (15)

To be consistent with our previous notation, we will simply write
$\mathcal{S}_{t}^{\emptyset}=\mathcal{S}_{t}$ and $T^{\emptyset}=T$. The
interest of this Markovian grand coupling is revealed in the following lemma.
While the monotonicity property (i) is a well-known feature of IDLA, the
subtler concavity property (ii) seems to be new, and will play a crucial role
in our proof of Theorem 2.

######  Lemma 1 (Monotonicity and concavity).

For every $t\in\mathbb{N}$ and every $A\subseteq B\subseteq V$, we have

  1. (i)

$\mathcal{S}_{t}^{A}\subseteq\mathcal{S}_{t}^{B}$

  2. (ii)

$|\mathcal{S}_{t+1}^{B}|-|\mathcal{S}_{t+1}^{A}|\leq|\mathcal{S}_{t}^{B}|-|\mathcal{S}_{t}^{A}|$.

###### Proof.

Fix $A\subseteq B\subseteq V$ and a finite sequence of sites $w$, and let us
compare $A^{\prime}:=f(A,w)$ with $B^{\prime}:=f(B,w)$. In view of the
definition of $f$, there are four possible cases:

  1. 1.

If $w$ does not visit $A^{c}$, then $(A^{\prime},B^{\prime})=(A,B)$.

  2. 2.

If $w$ visits $A^{c}$ but not $B^{c}$, then
$(A^{\prime},B^{\prime})=(A\cup\\{x\\},B)$ for some $x\in B\setminus A$.

  3. 3.

If $w$ visits $B^{c}$ before $B\setminus A$, then
$(A^{\prime},B^{\prime})=(A\cup\\{x\\},B\cup\\{x\\})$ for some $x\in B^{c}$.

  4. 4.

If $w$ visits $B^{c}$ after $B\setminus A$, then
$(A^{\prime},B^{\prime})=(A\cup\\{x\\},B\cup\\{y\\})$ for some $x\in
B\setminus A$ and $y\in B^{c}$.

In all cases, we have $A^{\prime}\subseteq B^{\prime}$ and
$|B^{\prime}|-|A^{\prime}|\leq|B|-|A|$, so (iii) and (iv) follow by induction.
∎

As a first application, let us establish the promised sub-multiplicativity of
${\rm d}_{{\textsc{sep}}}$.

######  Lemma 2 (Sub-multiplicativity of ${\rm d}_{{\textsc{sep}}}$).

For all $s,t\in\mathbb{N}$, we have

$\displaystyle{\rm d}_{{\textsc{sep}}}(s+t)$ $\displaystyle\leq$
$\displaystyle{\rm d}_{{\textsc{sep}}}(s){\rm d}_{{\textsc{sep}}}(t).$

###### Proof.

Fix $s,t\in\mathbb{N}$. Property (i) guarantees that the function $g_{t}\colon
2^{V}\to[0,\infty)$ defined by

$\displaystyle g_{t}(A)$ $\displaystyle:=$
$\displaystyle{\mathbb{P}}\left(T^{A}>t\right)$

is non-increasing. Now, by the Markov property at time $s$, we have

$\displaystyle{\mathbb{P}}(T>s+t)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}\left[g_{t}(\mathcal{S}_{s}){\bf 1}_{(T>s)}\right]$
$\displaystyle\leq$ $\displaystyle{\mathbb{E}}\left[g_{t}(\emptyset){\bf
1}_{(T>s)}\right]$ $\displaystyle=$
$\displaystyle{\mathbb{P}}(T>t){\mathbb{P}}(T>s).$

In view of Proposition 1, this concludes the proof. ∎

A useful consequence of this is that the mean filling time ${\mathbb{E}}[T]$
is a $2-$approximation of ${\rm t}_{\textsc{sep}}$.

######  Lemma 3 (First-moment estimate).

We have

$\displaystyle\frac{{\mathbb{E}}[T]}{2}\ \leq$ $\displaystyle{\rm
t}_{\textsc{sep}}$ $\displaystyle\leq\ 2{\mathbb{E}}[T].$

###### Proof.

Using the definition of ${\rm t}_{\textsc{sep}}={\rm t}_{\textsc{sep}}(1/2)$
and Proposition 1, we have

$\displaystyle\frac{1}{2}$ $\displaystyle<$ $\displaystyle{\rm
d}_{{\textsc{sep}}}({\rm t}_{\textsc{sep}}-1)\ =\ {\mathbb{P}}(T\geq{\rm
t}_{\textsc{sep}})\ \leq\ \frac{{\mathbb{E}}[T]}{{\rm t}_{\textsc{sep}}},$

which yields the upper bound. The lower bound uses the sub-multiplicativity of
$t\mapsto{\mathbb{P}}(T>t)$ to relate the mean and median of $T$: we have
${\mathbb{P}}(T>q{\rm t}_{\textsc{sep}})\leq 2^{-q}$ for all $q\in\mathbb{N}$,
hence

$\displaystyle{\mathbb{E}}[T]$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}{\mathbb{P}}(T>k)$ $\displaystyle=$
$\displaystyle\sum_{q=0}^{\infty}\sum_{r=0}^{{\rm
t}_{\textsc{sep}}-1}{\mathbb{P}}(T>q{\rm t}_{\textsc{sep}}+r)$
$\displaystyle\leq$ $\displaystyle\sum_{q=0}^{\infty}\sum_{r=0}^{{\rm
t}_{\textsc{sep}}-1}2^{-q}$ $\displaystyle=$ $\displaystyle 2{\rm
t}_{\textsc{sep}}.$

∎

###  2.3 Proof of Theorem 1

Let us prove Theorem 1. Write $p_{\star}:=\min_{x}p(x)$. In view of (3), our
goal is to prove that

$\displaystyle\lim_{t\to\infty}\left({\mathbb{P}}(T>t)\right)^{\frac{1}{t}}$
$\displaystyle=$ $\displaystyle 1-p_{\star}.$ (16)

Note that the limit on the left-hand side exists, by sub-multiplicativity.
Now, fix $x\in V$ and $t\in\mathbb{N}$. By the monotonicity of IDLA (Property
(i) in Lemma 1) and (15), we have

$\displaystyle{\mathbb{P}}(T>t)$ $\displaystyle\geq$
$\displaystyle{\mathbb{P}}(T^{V\setminus\\{x\\}}>t)\ =\ (1-p(x))^{t}.$ (17)

Optimizing over $x\in V$ already yields the lower bound in (16). Conversely,
let us decompose $T$ as

$\displaystyle T$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{n-1}(T_{k+1}-T_{k}),$

where $T_{k}:=\inf\left\\{t\geq 0\colon|\mathcal{S}_{t}|=k\right\\}$ denotes
the first time at which $k$ distinct vertices have been covered. Note that the
latter is a stopping time for the natural filtration $(\mathcal{F}_{t})_{t\geq
0}$ of our Markovian grand coupling. Now fix $0\leq k<n$ and observe that
conditionally on $\mathcal{F}_{T_{k}}$, the random variable $T_{k+1}-T_{k}$
has a geometric distribution with success probability
$p(\mathcal{S}_{T_{k}}^{c})$, where we have extended the definition of hitting
probabilities (4) from sites to subsets $A\subseteq V$ in the natural way,
i.e.,

$\displaystyle p(A)$ $\displaystyle:=$
$\displaystyle{\mathbf{P}}_{\nu}\left(\tau_{A}<\tau_{\dagger}\right).$ (18)

Since the function $p\colon 2^{V}\to[0,1]$ is non-decreasing, we have
$p(A)\geq p_{\star}$ for any non-empty set $A$, hence for
$A=\mathcal{S}_{T_{k}}^{c}$. It follows that $T$ is stochastically dominated
by the sum of $n$ independent geometric random variables with success
parameter $p_{\star}$. In particular,

$\displaystyle{\mathbb{E}}\left[z^{-T}\right]$ $\displaystyle<$
$\displaystyle\infty,$

for any $z\in(1-p_{\star},1)$, and since ${\mathbb{P}}(T>t)\leq
z^{t}{\mathbb{E}}\left[z^{-T}\right],$ the upper bound in (16) follows.

###  2.4 Proof of Theorem 2

In this section, we estimate the width of the mixing window. We start by
observing that the representation ${\rm
d}_{{\textsc{sep}}}(t)={\mathbb{P}}(T>t)$ provided by Proposition 1 reduces
our task to a variance estimate.

######  Lemma 4 (Width of the mixing window).

For any $\varepsilon\in(0,1)$, we have

$\displaystyle{\rm t}_{\textsc{sep}}(\varepsilon)-{\rm
t}_{\textsc{sep}}(1-\varepsilon)$ $\displaystyle\leq$ $\displaystyle
2\sqrt{\frac{\mathrm{Var}(T)}{\varepsilon}}.$

###### Proof.

Fix $\varepsilon\in(0,1)$ and let us introduce the integers

$\displaystyle t^{-}\ :=\
\left\lceil{\mathbb{E}}[T]-\sqrt{\frac{\mathrm{Var}(T)}{\varepsilon}}\right\rceil\
$ and $\displaystyle t^{+}\ :=\
\left\lfloor{\mathbb{E}}[T]+\sqrt{\frac{\mathrm{Var}(T)}{\varepsilon}}\right\rfloor.$

Using Chebychev’s inequality, and the fact that $T,t^{\pm}$ are integers, we
have

$\displaystyle{\mathbb{P}}(T>t^{+})\ <\ \varepsilon$ and
$\displaystyle{\mathbb{P}}(T\geq t^{-})\ >\ 1-\varepsilon.$

In view of Proposition 1, this gives ${\rm t}_{\textsc{sep}}(\varepsilon)\leq
t^{+}$ and ${\rm t}_{\textsc{sep}}(1-\varepsilon)\geq t^{-}$, and we conclude
that ${\rm t}_{\textsc{sep}}(\varepsilon)-{\rm
t}_{\textsc{sep}}(1-\varepsilon)\leq t^{+}-t^{-}$. ∎

We now recall a beautiful variance estimate for hitting times of increasing
Markov processes due to Aldous [2, Lemma 1.1]. Surprisingly, the latter does
not seem to have found many applications.

######  Lemma 5 (Variance estimate for hitting times, Aldous [2]).

Let $T$ be the hitting time of some fixed state by a Markov chain on some
finite state space. Write $h(A):={\mathbb{E}}_{A}[T]$ for its expectation when
starting from the initial state $A$, and suppose that for any allowed
transition $A\to B$, we have

$\displaystyle 0\ \leq$ $\displaystyle h(A)-h(B)$ $\displaystyle\leq\ \kappa,$

where $\kappa$ is a constant. Then,
$\textrm{Var}_{A}(T)\leq\kappa\,{\mathbb{E}}_{A}[T]$ for any initial state
$A$.

We will of course apply this lemma to the IDLA process, and we thus set

$\displaystyle h(A)$ $\displaystyle:=$
$\displaystyle{\mathbb{E}}\left[T^{A}\right].$

Our next step consists in showing that the assumption of the above lemma holds
with $\kappa={\rm t}_{\textsc{rel}}$.

######  Lemma 6 (Control on increments).

For any $x\in V$ and any $A\subseteq V$, we have

$\displaystyle 0$ $\displaystyle\leq\ h(A)-h(A\cup\\{x\\})\ \leq$
$\displaystyle{\rm t}_{\textsc{rel}}.$

###### Proof.

Fix $A\subseteq V$ and $x\in V$. The monotonicity of IDLA (Property (i) in
Lemma 1) ensures that

$\displaystyle T^{A\cup\\{x\\}}$ $\displaystyle\leq$ $\displaystyle T^{A},$

which readily yields the lower bound. We now turn to the upper bound. By the
strong Markov property at the stopping time $\tau=T^{A\cup\\{x\\}}$, we have

$\displaystyle{\mathbb{E}}\left[T^{A}\right]$ $\displaystyle=$
$\displaystyle{\mathbb{E}}\left[T^{A\cup\\{x\\}}\right]+{\mathbb{E}}\left[h\left(\mathcal{S}^{A}_{\tau}\right)\right].$
(19)

Now, the concavity of IDLA (Property (ii) in Lemma 1) implies

$\displaystyle\forall
t\in\mathbb{N},\quad\big{|}\mathcal{S}^{A\cup\\{x\\}}_{t}\big{|}\leq\left|\mathcal{S}^{A}_{t}\right|+1,$

and choosing $t=T^{A\cup\\{x\\}}$ shows that the random set
$\mathcal{S}_{\tau}^{A}$ appearing in (19) satisfies

$\displaystyle|\mathcal{S}_{\tau}^{A}|$ $\displaystyle\geq$
$\displaystyle|V|-1.$

To conclude the proof, we note that this last condition deterministically
implies $h(\mathcal{S}_{\tau}^{A})\leq{\rm t}_{\textsc{rel}}$. Indeed, we have
$h(V)=0$ and $h(V\setminus\\{x\\})=\frac{1}{p(x)}$ for every $x\in V$, by
(15). ∎

We now have all we need to establish Theorem 2.

###### Proof of Theorem 2.

Combining Lemmas 5 and 6, we have

$\displaystyle\mathrm{Var}(T)$ $\displaystyle\leq$
$\displaystyle{\mathbb{E}}[T]{\rm t}_{\textsc{rel}}$ $\displaystyle\leq$
$\displaystyle 2{\rm t}_{\textsc{rel}}{\rm t}_{\textsc{sep}},$

where the second line uses Lemma 3. In view of Lemma 4, this concludes the
proof. ∎

###  2.5 Proof of Theorem 3

In this final section, we estimate ${\mathbb{E}}[T]$ from above and below to
prove Theorem 3. We write $n=|V|$.

######  Lemma 7 (A general lower bound).

We have

$\displaystyle{\mathbb{E}}[T]$ $\displaystyle\geq$ $\displaystyle\frac{n(\log
n-\log\log n-1)}{\sum_{x\in V}p(x)}.$

###### Proof.

Fix an initial condition $A\subsetneq V$. As in the proof of Theorem 1, we may
decompose $T^{A}$ as

$\displaystyle T^{A}$ $\displaystyle=$
$\displaystyle\sum_{k=|A|}^{n-1}(T_{k+1}^{A}-T_{k}^{A}),$

where $T_{k}^{A}:=\inf\left\\{t\geq 0\colon|\mathcal{S}_{t}^{A}|=k\right\\}.$
Now, fix $k\in\\{|A|,\ldots,n-1\\}$ and observe that conditionally on
$\mathcal{F}_{T_{k}^{A}}$, the random variable $T_{k+1}^{A}-T_{k}^{A}$ has a
geometric distribution with success probability
$p\left(V\setminus\mathcal{S}_{T_{k}^{A}}^{A}\right)$, where $p\colon
2^{V}\to[0,1]$ was defined at (18). In particular, we have

$\displaystyle{\mathbb{E}}\left[T^{A}\right]$ $\displaystyle=$
$\displaystyle\sum_{k=|A|}^{n-1}{\mathbb{E}}\left[\frac{1}{p\left(V\setminus\mathcal{S}_{{T_{k}^{A}}}^{A}\right)}\right].$

Now, it readily follows from its definition that the function $p$ is sub-
additive:

$\displaystyle\forall B\subseteq V,\qquad p(B)$ $\displaystyle\leq$
$\displaystyle\sum_{x\in B}p(x).$

Note also that the right-hand side can be further bounded by $|B|\max_{x\in
B}p(x)$. Applying this to the random subset
$B=V\setminus\mathcal{S}_{{T_{k}^{A}}}^{A}$ appearing in the previous
identity, we obtain

$\displaystyle{\mathbb{E}}\left[T^{A}\right]$ $\displaystyle\geq$
$\displaystyle\frac{1}{\max_{x\in A^{c}}p(x)}\sum_{k=|A|}^{n-1}\frac{1}{n-k}$
$\displaystyle\geq$ $\displaystyle\frac{\log(1+|A^{c}|)}{\max_{x\in
A^{c}}p(x)}.$

Finally, recall that ${\mathbb{E}}[T]\geq{\mathbb{E}}[T^{A}]$ by the
monotonicity of IDLA (Property (i) in Lemma 1). Since $A$ was arbitrary, we
may finally replace it with its complement to get the nicer-looking bound:

$\displaystyle{\mathbb{E}}[T]$ $\displaystyle\geq$
$\displaystyle\frac{\log(1+|A|)}{\max_{x\in A}p(x)}.$

It remains to optimize over the choice of the subset $A$. To do so, let us
relabel the sites so that $V=[n]=\\{1,\ldots,n\\}$ and $p(1)\leq\ldots\leq
p(n)$. Choosing $A=[k]$ for some $1\leq k\leq n$, we then have

$\displaystyle\max_{x\in A}p(x)$ $\displaystyle=$ $\displaystyle p(k)\ \leq\
\frac{p(k)+\cdots+p(n)}{n+1-k}\ \leq\ \frac{p(1)+\cdots+p(n)}{n+1-k}.$

Thus, we arrive at

$\displaystyle{\mathbb{E}}[T]$ $\displaystyle\geq$
$\displaystyle\frac{(n+1-k)\log(1+k)}{p(1)+\cdots+p(n)},$

and we may finally choose $k=\lceil\frac{n}{\log n}\rceil$ to optimize this
bound and conclude the proof. ∎

######  Lemma 8 (A general upper bound).

We have

$\displaystyle{\rm t}_{\textsc{sep}}$ $\displaystyle\leq$
$\displaystyle\left(\sqrt{\mathcal{R}}+3\sqrt{{{\rm t}_{\textsc{rel}}\log
n}}\right)^{2}.$

###### Proof.

We refine an argument first used in [13] in the case where $\nu$ is a Dirac
mass, and then adapted in [15] to the case where $\nu$ is the uniform
distribution. Fix a site $x\in V$, and let

$\displaystyle T_{x}$ $\displaystyle:=$ $\displaystyle\inf\\{t\geq 0\colon
x\in\mathcal{S}_{t}\\},$

be the first time that $x$ is occupied by ${\rm IDLA}$. By construction, the
walk $W_{T_{x}}$ must hit $x$, and we let $Z_{x}$ denote its trajectory after
the first visit to $x$. Note that this part of the trajectory is completely
ignored in our construction of $(\mathcal{S}_{t})_{t\geq 0}$. Moreover, by the
Markov property, $Z_{x}$ is just a $K-$walk starting at $x$, and the walks
$(Z_{x}\colon x\in V)$ are independent. Now, fix $z\in V$ and let

$\displaystyle\mathcal{N}_{\star}(z)$ $\displaystyle:=$
$\displaystyle\sum_{x\in V\setminus\\{z\\}}{\bf
1}_{\left\\{\tau_{z}(Z_{x})<\tau_{\dagger}(Z_{x})\right\\}},$

count the number of ignored walks that visit $z$. For $t\in\mathbb{N}$, let
also

$\displaystyle\mathcal{N}_{t}(z)$ $\displaystyle:=$
$\displaystyle\sum_{k=1}^{t}{\bf
1}_{\left\\{\tau_{z}(W_{k})<\tau_{\dagger}(W_{k})\right\\}},$

count those walks $W_{1},\ldots,W_{t}$ that hit $z$. Note that any visit to
$z$ by a walk $W_{k}$ will result in
$\mathcal{S}_{k}=\mathcal{S}_{k-1}\cup\\{z\\}$, unless it occurs in the
ignored part of $W_{k}$. Consequently,

$\displaystyle{\mathbb{P}}\left(z\notin\mathcal{S}_{t}\right)$
$\displaystyle\leq$
$\displaystyle{\mathbb{P}}\left(\mathcal{N}_{t}(z)\leq\mathcal{N}_{\star}(z)\right).$

But $\mathcal{N}_{\star}(z)$ and $\mathcal{N}_{t}(z)$ are sums of independent
Bernoulli variables, with

$\displaystyle{\mathbb{E}}[\mathcal{N}_{t}(z)]$ $\displaystyle=$
$\displaystyle tp(z)$ $\displaystyle{\mathbb{E}}[\mathcal{N}_{\star}(z)]$
$\displaystyle=$ $\displaystyle\sum_{x\in
V\setminus\\{z\\}}{\mathbf{P}}_{x}(\tau_{z}<\tau_{\dagger})\ \leq\
\mathcal{R}p(z).$

For $t\geq\mathcal{R}$, we have
$\sqrt{{\mathbb{E}}[\mathcal{N}_{t}(z)]}-\sqrt{{\mathbb{E}}[\mathcal{N}_{\star}(z)]}\geq\sqrt{p(z)}\left(\sqrt{t}-\sqrt{\mathcal{R}}\right)$,
and Lemma 9 below gives

$\displaystyle{\mathbb{P}}(\mathcal{N}_{t}(z)\leq\mathcal{N}_{\star}(z))$
$\displaystyle\leq$ $\displaystyle
2e^{-\frac{p(z)}{1+\sqrt{2}}\left(\sqrt{t}-\sqrt{\mathcal{R}}\right)^{2}}.$

Taking a union bound over $z\in V$, we conclude that

$\displaystyle{\mathbb{P}}(T>t)$ $\displaystyle\leq$ $\displaystyle
2\sum_{z\in
V}e^{-\frac{p(z)}{1+\sqrt{2}}\left(\sqrt{t}-\sqrt{\mathcal{R}}\right)^{2}}$
$\displaystyle\leq$ $\displaystyle
2ne^{-\frac{\left(\sqrt{t}-\sqrt{\mathcal{R}}\right)^{2}}{(1+\sqrt{2}){\rm
t}_{\textsc{rel}}}},$

where the second line uses Theorem 1. This shows that

$\displaystyle{\rm t}_{\textsc{sep}}$ $\displaystyle\leq$ $\displaystyle
1+\left(\sqrt{{\mathcal{R}}}+\sqrt{2(1+\sqrt{2}){\rm t}_{\textsc{rel}}\log
n}\right)^{2}$ $\displaystyle\leq$
$\displaystyle\left(\sqrt{{\mathcal{R}}}+3\sqrt{{\rm t}_{\textsc{rel}}\log
n}\right)^{2},$

as desired. ∎

######  Lemma 9 (Probability of an unexpected win).

Let $U$ and $V$ be jointly defined random variables, each distributed as a sum
of independent Bernoulli variables, and such that
${\mathbb{E}}[U]\leq{\mathbb{E}}[V]$. Then,

$\displaystyle{\mathbb{P}}\left(V\leq U\right)$ $\displaystyle\leq$
$\displaystyle
2\exp\left\\{-\frac{\left(\sqrt{{\mathbb{E}}[V]}-\sqrt{{\mathbb{E}}[U]}\right)^{2}}{1+\sqrt{2}}\right\\}.$

###### Proof.

Set $u={\mathbb{E}}[U]$, $v={\mathbb{E}}[V]$ and
$w:=\left(\frac{\sqrt{v}-\sqrt{u}}{2+\sqrt{2}}\right)^{2}$. Suppose we are
given $a,b\geq 0$ satisfying

$\displaystyle u+a$ $\displaystyle\leq$ $\displaystyle v-b.$ (20)

This guarantees the inclusion $\\{V\leq U\\}\subseteq\\{U\geq
u+b\\}\cup\\{V\leq v-a\\}$ and therefore

$\displaystyle{\mathbb{P}}\left(U\geq V\right)$ $\displaystyle\leq$
$\displaystyle{\mathbb{P}}\left(U\geq u+a\right)+{\mathbb{P}}\left(V\leq
v-b\right)$ $\displaystyle\leq$ $\displaystyle
e^{-\frac{a^{2}}{2u+a}}+e^{-\frac{b^{2}}{2v}},$

where the second line uses Chernov bounds. To obtain the desired conclusion,
we would like to set each of the two terms on the second line to $e^{-2w}$. In
other words, we take

$\displaystyle a$ $\displaystyle:=$ $\displaystyle w+\sqrt{w^{2}+4uw}$
$\displaystyle b$ $\displaystyle:=$ $\displaystyle 2\sqrt{vw}.$

It only remains to prove that this choice satisfies (20). Using
$\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$, we can write

$\displaystyle u-v+a+b$ $\displaystyle=$ $\displaystyle
u-v+2\sqrt{vw}+w+\sqrt{w^{2}+4uw}$ $\displaystyle\leq$ $\displaystyle
u-v+2\sqrt{vw}+2w+2\sqrt{uw}$ $\displaystyle=$
$\displaystyle\left(\sqrt{u}+\sqrt{v}\right)^{2}+2w-\left(\sqrt{v}-\sqrt{w}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\left(\sqrt{u}+\sqrt{w}+\sqrt{2w}\right)^{2}-\left(\sqrt{v}-\sqrt{w}\right)^{2}$
$\displaystyle=$ $\displaystyle 0,$

thanks to our careful choice of $w$. ∎

###### Proof of Theorem 3.

The inequalities $\mathcal{L}\leq{\rm t}_{\textsc{rel}}\leq\mathcal{R}$
readily follow from Theorem 1 and the definitions of
$\mathcal{L},\mathcal{R}$. The upper bound on ${\rm t}_{\textsc{sep}}$ is
exactly Lemma 8. The lower bound ${\rm t}_{\textsc{sep}}\geq n$ follows from
the observation that ${\mathbb{P}}(T\geq n)=1$, because IDLA grows by at most
one site at each step. For the bound ${\rm t}_{\textsc{sep}}\geq{\rm
t}_{\textsc{rel}}$, we take $t={\rm t}_{\textsc{sep}}$ in the following
argument, valid for all $t\in\mathbb{N}$:

$\displaystyle 1-\frac{t}{{\rm t}_{\textsc{rel}}}$ $\displaystyle\leq$
$\displaystyle\left(1-\frac{1}{{\rm t}_{\textsc{rel}}}\right)^{t}\ =\
\left(1-p_{\star}\right)^{t}\ \leq\ {\rm d}_{{\textsc{sep}}}(t),$

where the last inequality is (17). Finally, the bound ${\rm
t}_{\textsc{sep}}\geq\frac{\mathcal{L}\log n}{5}$ follows from Lemmas 3 and 7
when $n\geq 100$, because we then have

$\displaystyle\log n-\log\log n-1$ $\displaystyle\geq$
$\displaystyle\frac{2\log n}{5}.$

For the case $n<100$, we instead simply use ${\rm t}_{\textsc{sep}}\geq
n\geq\frac{n\log n}{5}\geq\frac{\mathcal{L}\log n}{5}$. ∎

## References

  * [1] David Aldous.  Hitting times for random walks on vertex-transitive graphs.  Math. Proc. Cambridge Philos. Soc., 106(1):179–191, 1989.
  * [2] David J. Aldous.  Weak concentration for first passage percolation times on graphs and general increasing set-valued processes.  ALEA Lat. Am. J. Probab. Math. Stat., 13(2):925–940, 2016.
  * [3] Riddhipratim Basu, Shirshendu Ganguly, Christopher Hoffman, and Jacob Richey.  Activated random walk on a cycle.  Ann. Inst. Henri Poincaré Probab. Stat., 55(3):1258–1277, 2019\.
  * [4] Benjamin Bond and Lionel Levine.  Abelian networks I. Foundations and examples.  SIAM J. Discrete Math., 30(2):856–874, 2016.
  * [5] P. Diaconis and W. Fulton.  A growth model, a game, an algebra, Lagrange inversion, and characteristic classes.  volume 49, pages 95–119 (1993). 1991.  Commutative algebra and algebraic geometry, II (Italian) (Turin, 1990).
  * [6] Persi Diaconis.  The cutoff phenomenon in finite Markov chains.  Proc. Nat. Acad. Sci. U.S.A., 93(4):1659–1664, 1996.
  * [7] Persi Diaconis and Laurent Saloff-Coste.  Separation cut-offs for birth and death chains.  Ann. Appl. Probab., 16(4):2098–2122, 2006.
  * [8] Ronald Dickman.  Nonequilibrium phase transitions in epidemics and sandpiles.  volume 306, pages 90–97. 2002.  STATPHYS 21 (Cancun, 2001).
  * [9] Ronald Dickman, Miguel A Munoz, Alessandro Vespignani, and Stefano Zapperi.  Paths to self-organized criticality.  Brazilian Journal of Physics, 30(1):27–41, 2000.
  * [10] Nicolas Forien and Alexandre Gaudillière.  Active phase for activated random walks on the lattice in all dimensions, 2022.
  * [11] Jonathan Hermon, Hubert Lacoin, and Yuval Peres.  Total variation and separation cutoffs are not equivalent and neither one implies the other.  Electron. J. Probab., 21:Paper No. 44, 36, 2016.
  * [12] Christopher Hoffman, Jacob Richey, and Leonardo T. Rolla.  Active phase for activated random walk on z, 2020.
  * [13] Gregory F. Lawler, Maury Bramson, and David Griffeath.  Internal diffusion limited aggregation.  Ann. Probab., 20(4):2117–2140, 1992.
  * [14] David A. Levin and Yuval Peres.  Markov chains and mixing times.  American Mathematical Society, Providence, RI, 2017.  Second edition of [ MR2466937], With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.
  * [15] Lionel Levine and Feng Liang.  Exact sampling and fast mixing of activated random walk, 2021.
  * [16] Lionel Levine and Vittoria Silvestri.  Universality conjectures for activated random walk, 2022.
  * [17] S S Manna.  Two-state model of self-organized criticality.  Journal of Physics A: Mathematical and General, 24(7):L363–L369, apr 1991.
  * [18] S.S. Manna.  Large-scale simulation of avalanche cluster distribution in sand pile model.  J. Stat. Phys., 59:509–521, 1990.
  * [19] Leonardo T. Rolla.  Activated random walks on $\mathbb{Z}^{d}$.  Probab. Surv., 17:478–544, 2020.
  * [20] Leonardo T. Rolla and Vladas Sidoravicius.  Absorbing-state phase transition for driven-dissipative stochastic dynamics on ${\mathbb{Z}}$.  Invent. Math., 188(1):127–150, 2012.
  * [21] Leonardo T. Rolla, Vladas Sidoravicius, and Olivier Zindy.  Universality and sharpness in activated random walks.  Ann. Henri Poincaré, 20(6):1823–1835, 2019.
  * [22] Justin Salez.  Universality of cutoff for exclusion with reservoirs, 2022.
  * [23] Eric Shellef.  Nonfixation for activated random walks.  ALEA Lat. Am. J. Probab. Math. Stat., 7:137–149, 2010.
  * [24] Alexandre Stauffer and Lorenzo Taggi.  Critical density of activated random walks on transitive graphs.  Ann. Probab., 46(4):2190–2220, 2018.
  * [25] Lorenzo Taggi.  Active phase for activated random walks on $\mathbb{Z}^{d}$, $d\geq 3$, with density less than one and arbitrary sleeping rate.  Ann. Inst. Henri Poincaré Probab. Stat., 55(3):1751–1764, 2019\.
  * [26] Wolfgang Woess.  Random walks on infinite graphs and groups, volume 138 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2000.