# The contact process on dynamic regular graphs: monotonicity and subcritical
phase

Bruno Schapira111Aix-Marseille Université<EMAIL_ADDRESS>Daniel
Valesin222University of Warwick<EMAIL_ADDRESS>
###### Abstract

We study the contact process on a dynamic random $d$-regular graph with an
edge-switching mechanism, as well as an interacting particle system that
arises from the local description of this process, called the herds process.
Both these processes were introduced in [dSOV21]; there it was shown that the
herds process has a phase transition with respect to the infectivity parameter
$\lambda$, depending on the parameter $\mathsf{v}$ that governs the edge
dynamics. Improving on a result of [dSOV21], we prove that the critical value
of $\lambda$ is strictly decreasing with $\mathsf{v}$. We also prove that in
the subcritical regime, the extinction time of the herds process started from
a single individual has an exponential tail. Finally, we apply these results
to study the subcritical regime of the contact process on the dynamic
$d$-regular graph. We show that, starting from all vertices infected, the
infection goes extinct in a time that is logarithmic in the number of vertices
of the graph, with high probability.

Keywords: contact process, dynamic graphs

##  1 Introduction

This paper is a follow-up to [dSOV21], which studied the contact process on a
dynamic random $d$-regular graph with an edge-flip mechanism introduced in
[CDG07]. The work [dSOV21] mainly focused on proving the existence of a
supercritical regime, where the extinction time of the process grows
exponentially with the number of vertices of the graph. Here, we show that
there is a phase transition between two regimes, where the order of magnitude
of the extinction time switches abruptly from logarithmic to exponential, as
the infection parameter crosses a critical value. The highlight of our
analysis is that it allows us to establish that this critical value of the
infection parameter is a strictly monotone function of the rate of the edge-
flip mechanism.

###  1.1 Contact process on static finite graphs

The contact process on a graph $G$ is an interacting particle system in which
the vertices of the graph can be either healthy or infected. Healthy vertices
get infected at rate $\lambda$ times the number of infected neighbors, where
$\lambda>0$ is a fixed parameter of the model, while infected vertices become
healthy at rate $1$, independently of each other. When the graph $G$ is
infinite, a quantity of interest is the critical rate $\lambda_{c}(G)$,
defined as the supremum of the values of $\lambda$ for which the process
started from any finite infected set dies out (reaches the all-healthy
configuration) almost surely.

In the case when $G$ is finite, the all-healthy configuration is always
reached almost surely (regardless of $\lambda$). The extinction time
$\tau_{G}$ is the hitting time of the all-healthy configuration, for the
process started from all infected. It has been observed in several cases that
when $(G_{n})_{n\geqslant 1}$ is a sequence of finite graphs which converges
locally to some (rooted) infinite graph $G_{\infty}$, typically the extinction
time $\tau_{G_{n}}$ grows logarithmically with $n$ when $\lambda$ is smaller
than $\lambda_{c}(G_{\infty})$ and grows exponentially with $n$ when $\lambda$
is larger than $\lambda_{c}(G_{\infty})$. For instance, this has been shown
when $G_{n}$ is a $d$-dimensional cube $\\{0,\dots,n\\}^{d}$ [CGOV84, DL88,
DS88, Mou93, Sch85], a $d$-regular tree up to height $n$ [CMMV14, Sta01], or
in the case which interests us more here, when $G_{n}$ is a random $d$-regular
graph with $n$ vertices [LS17, MV16], in which cases $G_{\infty}$ is
respectively $\mathbb{Z}^{d}$, the canopy tree, and the $d$-regular tree
$\mathbb{T}^{d}$.

###  1.2 Contact process on a dynamical random $d$-regular graph

We present now the dynamical version of the random $d$-regular graph first
introduced and studied in [CDG07]. Throughout the paper, we fix the degree
$d\geqslant 3$, and whenever we talk about a $d$-regular graph with $n$
vertices, we assume that $nd$ is even. We allow our graphs to contain loops
(edges involving the same vertex twice) and parallel edges (multiple edges
between the same two vertices), but we will keep writing ‘graph’ instead of
some other terminology such as ‘multi-graph’.

Let $G$ be a $d$-regular graph with $n$ vertices, and $e,e^{\prime}$ be two of
its edges; let $u,v$ be the vertices of $e$ and $u^{\prime},v^{\prime}$ the
vertices of $e^{\prime}$. We can define two possible switches of these edges
by replacing them with either (1) edges with vertices $\\{u,u^{\prime}\\}$ and
$\\{v,v^{\prime}\\}$, or (2) edges with vertices $\\{u,v^{\prime}\\}$ and
$\\{v,u^{\prime}\\}$. We then define a continuous-time Markov chain
$(G_{t})_{t\geqslant 0}$ on the space of $d$-regular graphs on a fixed set of
$n$ vertices as follows. The initial graph $G_{0}$ is distributed according to
the uniform distribution on the set of $d$-regular graphs. Then, given the
state $G_{t}$ at time $t$, we prescribe that any of the $2\cdot{|E|\choose 2}$
possible edge switches occurs on this graph with rate $\frac{\mathsf{v}}{nd}$,
where $\mathsf{v}>0$ is a positive parameter. It is readily seen that the
uniform distribution on random $d$-regular graphs is stationary with respect
to this dynamics, and moreover, that any fixed edge is involved in a switch at
a rate which converges to $\mathsf{v}$, as $n\to\infty$.

We next consider the process $(G_{t},\xi_{t})_{t\geqslant 0}$ where
$(G_{t})_{t\geqslant 0}$ is as above, and $(\xi_{t})_{t\geqslant 0}$ is a
contact process evolving on the dynamic graph. As previously mentioned, the
process starts from the configuration where all vertices are infected, and our
main interest is in the time $\tau_{(G_{t})}$ when the process reaches the
all-healthy configuration. The following result was proved in [dSOV21]. In
both this theorem and in Theorem 1.2 below, the probability measure
$\mathbb{P}$ includes the randomness of both the random dynamic graph and the
contact process.

######  Theorem 1.1 ([dSOV21]).

For each $\mathsf{v}>0$, there exists
$\bar{\lambda}(\mathsf{v})\in(0,\lambda_{c}(\mathbb{T}_{d}))$, such that the
following holds. For any $\lambda>\bar{\lambda}(\mathsf{v})$, there exists
$c>0$ such that

$\mathbb{P}\big{(}\tau_{(G_{t})}>\exp\\{cn\\}\big{)}\xrightarrow{n\to\infty}1.$

Note in particular the interesting feature that $\bar{\lambda}(\mathsf{v})$ is
strictly smaller than $\lambda_{c}(\mathbb{T}_{d})$, which means that the
dynamics of the graph helps the contact process to survive for a longer time
than in the static model.

###  1.3 Main results

In this paper, we complete the picture by proving the following result.

######  Theorem 1.2.

For each $\mathsf{v}>0$, there exists
$\bar{\lambda}(\mathsf{v})\in(0,\lambda_{c}(\mathbb{T}_{d}))$ such that the
following holds.

  * (i)

For any $\lambda>\bar{\lambda}(\mathsf{v})$, there exists $c>0$ such that

$\mathbb{P}\big{(}\tau_{(G_{t})}>\exp\\{cn\\}\big{)}\xrightarrow{n\to\infty}1.$

  * (ii)

For any $\lambda<\bar{\lambda}(\mathsf{v})$, there exists $C>0$ such that

$\mathbb{P}\big{(}\tau_{(G_{t})}>C\log n\big{)}\xrightarrow{n\to\infty}0.$

As in the static case, the value $\bar{\lambda}(\mathsf{v})$ corresponds to
the critical value for the contact process on a limiting model, which in our
case is called the herds process. This was introduced and analyzed in
[dSOV21], where in particular a phase transition delimited by a positive and
finite parameter $\bar{\lambda}(\mathsf{v})$ was established. Here we improve
upon this result by showing that the herds process exhibits a form of sharp
threshold phenomenon, namely that the tail distribution of the extinction time
decays exponentially fast in the whole subcritical regime (see Lemma 3.1
below). An informal description of the herds process is given in the next
subsection, and a precise definition is given in Section 2.

Our second result answers a question of [dSOV21] concerning the monotonicity
of $\bar{\lambda}(\mathsf{v})$.

######  Theorem 1.3.

The mapping $\mathsf{v}\mapsto\bar{\lambda}(\mathsf{v})$ is strictly
decreasing.

###  1.4 Methods of proof and organization of the paper

As in [dSOV21], the proof of Theorem 1.2 relies on a detailed analysis of the
herds process. Informally, this process evolves as a contact process on a
family of $d$-regular trees, where the number of trees also evolves with time.
On each tree, the process obeys the same rules as the usual contact process,
regarding infection and recovery (though we adopt a slight change of
terminology: the vertex states ‘healthy’ and ‘infected’ here are called
‘empty’ and ‘occupied by a particle’, respectively). In addition, each edge in
any of the existing tree splits the tree into two pieces at a constant rate
$\mathsf{v}$. When this happens, the two disjoint pieces of the tree are
completed to form two new copies of a $d$-regular tree.

The value $\bar{\lambda}(\mathsf{v})$ is defined as the threshold for the
infection parameter $\lambda$ above which the process has a positive
probability of surviving forever, when starting from a single tree with a
single particle. The heart of the proof is to show that when $\lambda$ is
smaller than this threshold, the probability to survive for a time larger than
$t$ decays exponentially fast with $t$. This is obtained using some coupling
argument with a two-type herds process, which allows to show that the expected
number of infected particles at time $t$, denoted (in this section only)
$F(\lambda,\mathsf{v},t)$, is a sub-multiplicative sequence (as a function of
the time parameter), see Section 2.2. Using this, we can define the rate of
exponential decay of this function, $\varphi(\lambda,\mathsf{v})$, and then
the proof boils down to showing that it is strictly increasing with respect to
both parameters. This is obtained via a kind of Russo’s formula, see
Proposition 3.5, which in our setting is quite involved, compared to the
original formula from percolation theory. Moreover, the strict monotonicity of
$\varphi(\lambda,\mathsf{v})$ also proves Theorem 1.3.

Another important ingredient is to control the higher moments of the number of
infected particles, which requires some serious additional technical work, due
to the non-linearity of these functionals, see Section 3.3. Bounding higher
moments is needed to control the total number of particle births (or in the
usual contact process terminology, infections) up to the extinction time,
which in turn allows one to couple the contact process on a large dynamic
$d$-regular graph with the herds process, up to this extinction time. This
coupling argument is explained in Section 4, where we complete the proof of
Theorem 1.2.

###  1.5 Related works

The study of the phase transition for long vs. short time extinction for the
contact process on finite graphs, and the closely related question of
metastability in the supercritical regime, has been studied intensively over
the past years. In particular as we already mentioned on finite boxes of
$\mathbb{Z}^{d}$ [CGOV84, DL88, DS88, DST89, Mou93, Sch85], finite $d$-regular
trees [CMMV14, Sta01], and random $d$-regular graphs [LS17, MV16], but also in
a number of other examples, such as the configuration model with power law
degree distribution [CS15, CD09, MVY13], or with general degree-distribution
[BNNS21, HD20], preferential attachment graphs [BBCS05, Can17], Erdős-Rényi
random graphs [BNNS21], inhomogeneous random graphs [Can19], or hyperbolic
random graphs [LMSV21]. There are also results concerning some general classes
of finite graph sequences [MMVY16, SV17].

On the other hand, the study of the contact process on dynamical graphs
started more recently, see e.g. [dSOV21, DJ23, HUVV22, JLM19, JLM22, JM17,
LR20, Rem08, SS22].

##  2 Preliminaries on the herds process

In this section, we give a formal definition of the herds process and
introduce notation. We also present some tools that will be employed in the
analysis of this process in later sections, namely, stochastic domination by a
pure-birth process and a submultiplicativity inequality for the expectation of
the number of particles.

###  2.1 Definition and construction

Throughout this paper, we fix $d\geqslant 3$ and let $\mathbb{T}^{d}$ denote
the infinite $d$-regular rooted tree. The root is denoted by $o$, and we write
$u\sim v$ when two vertices $u$ and $v$ are neighbors.

######  Definition 2.1.

Let

$P_{\mathsf{f}}(\mathbb{T}^{d}):=\\{A\subseteq\mathbb{T}^{d}:\;A\text{ is
finite and non-empty}\\}.$

We call each $A\in P_{\mathsf{f}}(\mathbb{T}^{d})$ a herd shape, and each
$x\in A$ a particle of $A$. Given a herd shape $A$ and an edge $e=\\{u,v\\}$
of $\mathbb{T}^{d}$ with $u$ closer to the root than $v$, in the graph
distance of $\mathbb{T}^{d}$, define

$A_{e,1}:=\\{w\in A:\;w\text{ is closer to $u$ than to $v$}\\},\quad
A_{e,2}:=A\backslash A_{e,1}.$

We say that $e$ is an active edge of $A$ if $A_{e,1}\neq\varnothing$ and
$A_{e,2}\neq\varnothing$.

######  Definition 2.2.

Define the set of herd configurations

$\mathcal{S}:=\\{\xi:P_{\mathsf{f}}(\mathbb{T}^{d})\to\mathbb{N}_{0}\text{
with }\textstyle{\sum_{A}}\xi(A)<\infty\\}.$

In a herd configuration $\xi\in\mathcal{S}$, $\xi(A)$ is interpreted as the
number of herds with shape $A$. Given $A\in P_{\mathsf{f}}(\mathbb{T}^{d})$,
we let $\delta_{A}$ denote the herd configuration such that $\delta_{A}(B)=1$
if $B=A$, and $\delta_{A}(B)=0$ otherwise. An enumeration of
$\xi\in\mathcal{S}$ is a sequence $A_{1},\ldots,A_{m}\in
P_{\mathsf{f}}(\mathbb{T}^{d})$ such that $\xi=\sum_{i=1}^{m}\delta_{A_{i}}$.

We will generally denote deterministic elements of $\mathcal{S}$ by the letter
$\xi$, and random elements of $\mathcal{S}$ by $\Xi$.

######  Definition 2.3.

The herds process $(\Xi_{t})_{t\geqslant 0}$ with birth rate $\lambda>0$ and
splitting rate $\mathsf{v}>0$ is a continuous-time Markov chain on
$\mathcal{S}$ whose dynamics is given by the following description of possible
jumps and corresponding rates:

  * (a)

_death in herds with more than one particle:_ for each $A$ with $|A|>1$ such
that $\xi(A)>0$, and for each $x\in A$, with rate $\xi(A)$, the process jumps
from $\xi$ to $\xi-\delta_{A}+\delta_{A\backslash\\{x\\}}$;

  * (b)

_death in herds with one particle:_ for each $A$ with $|A|=1$ such that
$\xi(A)>0$, with rate $\xi(A)$, the process jumps from $\xi$ to
$\xi-\delta_{A}$;

  * (c)

_birth:_ for each $A$ such that $\xi(A)>0$, and for each $y\in\mathbb{T}^{d}$
with $y\notin A$, with rate $\lambda\cdot|\\{x\in A:x\sim y\\}|\cdot\xi(A)$,
the process jumps from $\xi$ to $\xi-\delta_{A}+\delta_{A\cup\\{y\\}}$;

  * (d)

_split:_ for each $A$ such that $\xi(A)>0$, and for each active edge $e$ of
$A$, with rate $\mathsf{v}\cdot\xi(A)$, the process jumps from $\xi$ to
$\xi-\delta_{A}+\delta_{A_{e,1}}+\delta_{A_{e,2}}$.

######  Remark 2.1.

A priori, it could be the case that the above description gave rise to an
explosive chain, that is, a chain that jumps infinitely many times in a
bounded time interval. So, strictly speaking, the process is only defined up
to the explosion time (the infimum of times $t>0$ such that infinitely many
jumps happen in $(0,t)$). However, we will show shortly (see Corollary 2.2
below) that the chain is in fact not explosive.

######  Remark 2.2.

Our choice for the state space $\mathcal{S}$ of the herds process makes it so
that, in case there are multiple herds with the same shape $A$ (meaning that
$\xi(A)\geqslant 2$), then these herds are indistinguishable. An alternative
choice was made in [dSOV21]: there, a state of the process was an index set
$\mathcal{J}$ and a mapping from $\mathcal{J}$ to
$P_{\mathsf{f}}(\mathbb{T}^{d})$, so that each $i\in\mathcal{J}$ represented a
different herd. This alternative choice requires heavier notation, but has
some advantages; for instance, when a particle is born in a herd, it makes
sense to consider the herd before and after the birth (since it keeps the same
index). Although here we will adopt the leaner description of Definition 2.3,
we will sometimes pretend that a richer description is available. For
instance, in one of our arguments (see Lemma 3.2) we fix a particle in a herd
at time $0$, and consider the evolution of the cardinality of the herd
containing that particle for times $t\geqslant 0$.

We let $\mathbb{P}$ be a probability measure under which the herds process is
defined, and $\mathbb{E}$ the associated expectation. When we want to be
explicit about the parameters, we will write $\mathbb{P}_{\lambda,\mathsf{v}}$
and $\mathbb{E}_{\lambda,\mathsf{v}}$. _When no explicit mention regarding the
initial configuration is made, we assume it to consist of a single herd with a
single particle placed at the root vertex_. We may write
$\mathbb{P}_{\lambda,\mathsf{v}}(\cdot\mid\Xi_{0}=\xi)$ (and similarly
$\mathbb{E}_{\lambda,\mathsf{v}}[\cdot\mid\Xi_{0}=\xi]$) to specify some other
initial configuration $\xi\in\mathcal{S}$.

######  Definition 2.4.

Given $\xi\in\mathcal{S}$, we let

$X(\xi):=\sum_{A\in P_{\mathsf{f}}(\mathbb{T}^{d})}|A|\cdot\xi(A),$ (1)

where $|\cdot|$ denotes cardinality; that is, $X(\xi)$ is the total number of
particles among all herds in $\xi$. We also let

$\mathscr{E}(\xi):=\sum_{A\in P_{\mathsf{f}}(\mathbb{T}^{d})}|\\{\text{active
edges of $A$}\\}|\cdot\xi(A),$ (2)

the total number of active edges among all herds of $\xi$. For the herds
process $(\Xi_{t})_{t\geqslant 0}$ (started from an arbitrary configuration),
we write

$X_{t}:=X(\Xi_{t}),\qquad\mathscr{E}_{t}:=\mathscr{E}(\Xi_{t}),$ (3)

with $X$ and $\mathscr{E}$ as in (1) and (2), respectively.

We now state a useful stochastic domination result. The proof involves a quick
inspection of transition rates, and we omit it.

######  Lemma 2.1 (Domination by pure-birth chain).

For the herds process $(\Xi_{t})_{t\geqslant 0}$ with parameters $\lambda$,
$\mathsf{v}$ and some initial configuration $\xi\in\mathcal{S}$, let $N_{t}$
denote the number of birth events until time $t$. Let $(Z_{t})_{t\geqslant 0}$
be the continuous-time Markov chain on $\mathbb{N}$ with $Z_{0}=X(\xi)$ and
jump rates

$q(i,i+1)=d\lambda i,\qquad q(i,j)=0\text{ for }j\neq i+1.$ (4)

Then, $(N_{t})_{t\geqslant 0}$ is stochastically dominated by
$(Z_{t}-Z_{0})_{t\geqslant 0}$. In particular,
$\mathbb{P}(N_{t}<\infty)\geqslant\mathbb{P}(Z_{t}<\infty)=1$ for any $t$.

######  Corollary 2.2.

The herds process is non-explosive.

###### Proof.

When there are finitely many birth events in $[0,t]$, there are also finitely
many death events and split events in $[0,t]$, so the herds process performs
finitely many jumps of any kind in $[0,t]$. ∎

We also have the following important consequence concerning the processes
$(X_{t})$ and $(\mathscr{E}_{t})$ defined in (3).

######  Corollary 2.3.

For any $\lambda>0$, $\mathsf{v}>0$, $T>0$ and $k\geqslant 1$, there exists
$c>0$ such that the herds process $(\Xi_{t})_{t\geqslant 0}$ with parameters
$\lambda,\leavevmode\nobreak\ \mathsf{v}$ and arbitrary (deterministic)
initial configuration $\xi$ satisfies

$\mathbb{E}\left[\left.\max_{0\leqslant t\leqslant
T}(X_{t})^{k}\;\right|\;\Xi_{0}=\xi\right]\leqslant cX(\xi)^{k}$

and

$\mathbb{E}\left[\left.\max_{0\leqslant t\leqslant
T}(\mathscr{E}_{t})^{k}\;\right|\;\Xi_{0}=\xi\right]\leqslant
c(X(\xi)+\mathscr{E}(\xi))^{k}.$

###### Proof.

Again let $N_{t}$ denote the number of births in the herds process until time
$t$. Note that

$\max_{0\leqslant t\leqslant T}X_{t}\leqslant
X_{0}+N_{T}\qquad\text{and}\quad\max_{0\leqslant t\leqslant
T}\mathscr{E}_{t}\leqslant\mathscr{E}_{0}+N_{T};$ (5)

to justify the latter, we observe that deaths and splits can only decrease
$\mathscr{E}_{t}$, while a birth can increase $\mathscr{E}_{t}$ by at most
one.

Let $(Z_{t})_{t\geqslant 0}$ be the pure-birth chain of Lemma 2.1, started
with $Z_{0}=X_{0}$. By that lemma, $(Z_{t}-Z_{0})_{t\geqslant 0}$
stochastically dominates $(N_{t})_{t\geqslant 0}$. Then,

$\mathbb{E}\left[\left.\max_{0\leqslant t\leqslant
T}(X_{t})^{k}\;\right|\;\Xi_{0}=\xi\right]\leqslant\mathbb{E}\left[\left.(X_{0}+N_{T})^{k}\;\right|\;\Xi_{0}=\xi\right]\leqslant\mathbb{E}[(X_{0}+Z_{T}-Z_{0}))^{k}],$

where the last expectation is with respect to the probability measure under
which $(Z_{t})$ is defined (note that $X_{0}$ is fixed and deterministic).
Next, the law of $Z_{T}-Z_{0}$ is equal to the law of
$\sum_{i=1}^{Z_{0}}\zeta^{(i)}_{T}$, where
$(\zeta^{(1)}_{t}),\ldots,(\zeta^{(Z_{0})}_{t})$ are independent pure-birth
processes with rates as in (4), each started with a population of one. Using
Minkowski’s inequality,

$\displaystyle\mathbb{E}[(X_{0}+Z_{T}-Z_{0})^{k}]^{1/k}\leqslant
X_{0}+\sum_{i=1}^{Z_{0}}\mathbb{E}[(\zeta^{(i)}_{T})^{k}]^{1/k}=cX_{0},$

where $c:=\mathbb{E}[(\zeta^{(i)}_{T})^{k}]^{1/k}+1$, which by [AN04,
Corollary 1 p.111] is finite and only depends on $\lambda$, $k$ and $T$. This
completes the proof of the first bound. For the second one, we start using the
second bound in (5):

$\displaystyle\mathbb{E}\left[\left.\max_{0\leqslant t\leqslant
T}(\mathscr{E}_{t})^{k}\;\right|\;\Xi_{0}=\xi\right]$
$\displaystyle\leqslant\mathbb{E}\left[\left.(\mathscr{E}_{0}+N_{T})^{k}\;\right|\;\Xi_{0}=\xi\right]$
$\displaystyle=\mathbb{E}\left[\left.(X_{0}+\mathscr{E}_{0}+N_{T}-X_{0})^{k}\;\right|\;\Xi_{0}=\xi\right],$

and then complete the proof as in the previous case. ∎

We now present three properties of the herds process (in Lemmas 2.4, 2.5 and
2.6 below). In all three cases, the proof is elementary and omitted.

######  Lemma 2.4 (Invariance under tree automorphisms).

Let $\psi:\mathbb{T}^{d}\to\mathbb{T}^{d}$ be a graph automorphism. Fix $A\in
P_{\mathsf{f}}(\mathbb{T}^{d})$ and let $(\Xi_{t})_{t\geqslant 0}$ and
$(\Xi_{t}^{\prime})_{t\geqslant 0}$ be herds processes started from
$\delta_{A}$ and $\delta_{\psi(A)}$, respectively. Then, the process

$\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\Xi_{t}(A)\cdot\delta_{\psi(A)},\quad
t\geqslant 0$

has the same distribution as $(\Xi_{t}^{\prime})_{t\geqslant 0}$. In
particular, the processes $(X(\Xi_{t}))_{t\geqslant 0}$ and
$(X(\Xi^{\prime}_{t}))_{t\geqslant 0}$ have the same distribution.

######  Lemma 2.5 (Decomposition into independent processes).

Let $\xi\in\mathcal{S}$ with enumeration $\xi=\sum_{i=1}^{n}\delta_{A_{i}}$,
where $A_{1},\ldots,A_{n}\in P_{\mathsf{f}}(\mathbb{T}^{d})$. Then, the herds
process started from $\xi$ has the same distribution as
$(\Xi^{(1)}_{t}+\cdots+\Xi^{(n)}_{t})_{t\geqslant 0}$, where
$(\Xi^{(1)}_{t})_{t\geqslant 0}$, $\ldots$, $(\Xi^{(n)}_{t})_{t\geqslant 0}$
are independent herds processes, started from $\delta_{A_{1}}$, $\ldots$,
$\delta_{A_{n}}$, respectively.

Before stating the third property, we define a partial order on $\mathcal{S}$.

######  Definition 2.5.

Given two herd configurations $\xi$ and $\xi^{\prime}$, we write
$\xi\preceq\xi^{\prime}$ if there exist enumerations

$\xi=\sum_{i=1}^{m}\delta_{A_{i}},\qquad\xi^{\prime}=\sum_{j=1}^{n}\delta_{A_{j}^{\prime}}$

such that $m\leqslant n$ and $A_{i}\subseteq A_{i}^{\prime}$ for
$i=1,\ldots,m$.

######  Lemma 2.6 (Attractiveness).

If $\xi\preceq\xi^{\prime}$, then $(\Xi_{t})_{t\geqslant 0}$ started from
$\xi$ is stochastically dominated (with respect to $\preceq$) by
$(\Xi^{\prime}_{t})_{t\geqslant 0}$ started from $\xi^{\prime}$.

We now give a definition pertaining to extinction vs. survival of the herds
process, and introduce the value $\bar{\lambda}(\mathsf{v})$ that appears in
the statements of our main theorems.

######  Definition 2.6.

We say that the herds process survives if the event
$\\{\sum_{A}\Xi_{t}(A)>0\;\forall t\\}$ occurs, that is, the process always
has particles; otherwise we say that the process dies out. For any
$\mathsf{v}>0$, we define $\bar{\lambda}(\mathsf{v})$ as the supremum of the
values of $\lambda$ for which the process with parameters $\lambda$ and
$\mathsf{v}$ dies out with probability 1.

It is easy to see that $\bar{\lambda}(\mathsf{v})\geqslant 1/d$. Indeed, when
$\lambda<1/d$, the rate at which existing particles die always exceeds the
rate at which new particles are born, so the process eventually reaches the
empty configuration. A moment’s thought, using for instance a comparison with
a branching process, shows that $\bar{\lambda}(\mathsf{v})<\infty$.

###  2.2 Sub-multiplicativity of number of particles

The goal of this section is to prove the following inequality. Recall that
$X_{t}$ denotes the number of particles in the herds process at time $t$. Also
recall that, whenever the initial condition of the herds process is omitted
(say, as in the expectation in the right-hand side of (6) below), it is equal
to $\delta_{\\{o\\}}$.

######  Proposition 2.7.

For any $t\geqslant 0$ and $\xi\in\mathcal{S}$ we have

$\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\xi]\leqslant
X(\xi)^{p}\cdot\mathbb{E}[X_{t}^{p}].$ (6)

Consequently, for any $t,s\geqslant 0$, $p\geqslant 1$ and
$\xi\in\mathcal{S}$, we have

$\mathbb{E}[X_{t+s}^{p}\mid\Xi_{0}=\xi]\leqslant\mathbb{E}[X_{s}^{p}\mid\Xi_{0}=\xi]\cdot\mathbb{E}[X_{t}^{p}].$
(7)

This proposition will be a consequence of the following lemma.

######  Lemma 2.8.

Let $A,B\in P_{\mathsf{f}}(\mathbb{T}^{d})$ be disjoint and $p\geqslant 1$.
Then,

$\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A\cup
B}]^{1/p}\leqslant\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A}]^{1/p}+\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{B}]^{1/p}.$

We postpone the proof of this lemma, and for now show how it implies the
proposition:

###### Proof of Proposition 2.7.

We claim that for any $p\geqslant 1$, $A\in P_{\mathsf{f}}(\mathbb{T}^{d})$,
and $t\geqslant 0$,

$\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A}]^{1/p}\leqslant|A|\cdot\mathbb{E}[X_{t}^{p}]^{1/p}.$
(8)

We prove this by induction on $|A|$. For $|A|=1$ the above holds with an
equality, by Lemma 2.4. For the induction step, we assume that $|A|\geqslant
2$, take $u\in A$ and bound, using Lemma 2.8, Lemma 2.4 and the induction
hypothesis:

$\displaystyle\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A}]^{1/p}$
$\displaystyle\leqslant\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A\backslash\\{u\\}}]^{1/p}+\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{\\{u\\}}]^{1/p}$
$\displaystyle\leqslant(|A\backslash\\{u\\}|)\cdot\mathbb{E}[X_{t}^{p}]^{1/p}+\mathbb{E}[X_{t}^{p}]^{1/p}$
$\displaystyle=|A|\cdot\mathbb{E}[X_{t}^{p}]^{1/p}.$

Now take $\xi\in\mathcal{S}$ with enumeration
$\xi=\sum_{i=1}^{m}\delta_{A_{i}}$. Let
$(\Xi^{(1)}_{t}),\ldots,(\Xi^{(m)}_{t})$ be independent herds processes,
started from $\delta_{A_{1}},\ldots,\delta_{A_{m}}$, respectively. By Lemma
2.5, we have

$\displaystyle\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\xi]^{1/p}$
$\displaystyle=\mathbb{E}\left[\left(\sum_{i=1}^{m}X(\Xi^{(i)}_{t})\right)^{p}\right]^{1/p}.$

Minkowski’s inequality gives

$\mathbb{E}\left[\left(\sum_{i=1}^{m}X(\Xi^{(i)}_{t})\right)^{p}\right]^{1/p}\leqslant\sum_{i=1}^{m}\mathbb{E}\left[X(\Xi^{(i)}_{t})^{p}\right]^{1/p}.$
(9)

By (8), the right-hand side is smaller than

$\displaystyle\sum_{i=1}^{m}|A_{i}|\cdot\mathbb{E}\left[X_{t}^{p}\right]^{1/p}=X(\xi)\cdot\mathbb{E}\left[X_{t}^{p}\right]^{1/p}.$

We have thus proved (6). To prove (7), we use the Markov property. Let
$s,t\geqslant 0$ and $\xi\in\mathcal{S}$; we have:

$\displaystyle\mathbb{E}[X_{t+s}^{p}\mid\Xi_{0}=\xi]$
$\displaystyle=\sum_{\xi^{\prime}\in\mathcal{S}}\mathbb{E}[X_{t+s}^{p}\mid\Xi_{s}=\xi^{\prime}]\cdot\mathbb{P}(\Xi_{s}=\xi^{\prime}\mid\Xi_{0}=\xi)$
$\displaystyle\leqslant\sum_{\xi^{\prime}\in\mathcal{S}}X(\xi^{\prime})^{p}\cdot\mathbb{E}[X_{t}^{p}]\cdot\mathbb{P}(\Xi_{s}=\xi^{\prime}\mid\Xi_{0}=\xi)$
$\displaystyle=\mathbb{E}[X_{s}^{p}\mid\Xi_{0}=\xi]\cdot\mathbb{E}[X_{t}^{p}].$

∎

To prove Lemma 2.8, we will define an auxiliary process, which informally
describes two herds processes that evolve almost independently, except that
they share the same splitting events. We start by defining the state space of
this process.

######  Definition 2.7.

Let

$P_{\mathsf{f},2}(\mathbb{T}^{d}):=\\{(A,B):\;A,B\subseteq\mathbb{T}^{d},\;A\cup
B\text{ finite and non-empty}\\}$

and

$\mathcal{S}_{2}:=\\{\widetilde{\xi}:P_{\mathsf{f},2}(\mathbb{T}^{d})\to\mathbb{N}_{0}\text{
with }\textstyle{\sum_{(A,B)}}\widetilde{\xi}(A,B)<\infty\\}.$

We interpret an element $(A,B)\in P_{\mathsf{f},2}(\mathbb{T}^{d})$ as a two-
type herd, that is, there are two species of particles, one of which occupies
$A$ and the other $B$. We emphasize that $A$ and $B$ need not be disjoint, and
one of them, but not both, can be empty. We will also need some projection
functions from ${\mathcal{S}}_{2}$ to $\mathcal{S}$.

######  Definition 2.8.

We define $\pi,\pi_{1},\pi_{2}:{\mathcal{S}}_{2}\to\mathcal{S}$ by setting,
for $\xi^{\prime}=\sum_{i=1}^{m}\delta_{(A_{i},B_{i})}$:

$\pi(\widetilde{\xi})=\sum_{i=1}^{m}\delta_{A_{i}\cup
B_{i}},\quad\pi_{1}(\widetilde{\xi})=\sum_{i:A_{i}\neq\varnothing}\delta_{A_{i}},\quad\pi_{2}(\widetilde{\xi})=\sum_{i:B_{i}\neq\varnothing}\delta_{B_{i}}.$

This definition is illustrated in Figure 1.

Figure 1:  A two-type herds configuration $\widetilde{\xi}$ is depicted on
top, with the two types represented in blue and red (it is assumed that in the
four herds of this configuration, no particle is present other than the ones
depicted). The projections $\pi(\widetilde{\xi})$, $\pi_{1}(\widetilde{\xi})$
and $\pi_{2}(\widetilde{\xi})$ are shown in the second, third and fourth rows,
respectively.

######  Definition 2.9.

The two-type herds process $(\widetilde{\Xi}_{t})_{t\geqslant 0}$ (with rates
$\lambda$ and $\mathsf{v}$) is a continuous-time Markov chain on
${\mathcal{S}}_{2}$ with transitions described as follows. At any time
$t\geqslant 0$, and for any $(A,B)$ with $\widetilde{\Xi}_{t}(A,B)\geqslant
1$, both $A$ and $B$ are subject, independently of each other, to death and
birth mechanisms as in the original herds process (in particular, if either of
them is empty, it stays empty). However, they are subject together to the same
splitting events: an edge $e$ is said to be active if $(A\cup
B)_{e,1}\neq\varnothing$ and $(A\cup B)_{e,2}\neq\varnothing$. Then, a split
occurs at any active edge $e$ with rate $\mathsf{v}$, and when this happens,
$(A,B)$ is split into the two pairs $(A_{e,1},B_{e,1})$ and
$(A_{e,2},B_{e,2})$. (In case $A=\varnothing$, we let
$A_{e,1}=A_{e,2}=\varnothing$, and similarly for $B$).

We record two observations about the two-type herds process in the following
lemma. The proof is done by comparing jump rates, and we omit it.

######  Lemma 2.9.

Let $(A,B)\in P_{\mathsf{f}}(\mathbb{T}^{d})\times
P_{\mathsf{f}}(\mathbb{T}^{d})$, and let $(\widetilde{\Xi})_{t\geqslant 0}$ be
the two-type herds process started from $\delta_{(A,B)}$.

  * (a)

The processes $(\pi_{1}(\widetilde{\Xi}_{t}))_{t\geqslant 0}$ and
$(\pi_{2}(\widetilde{\Xi}_{t}))_{t\geqslant 0}$ are herds processes started
from $\delta_{A}$ and $\delta_{B}$, respectively.

  * (b)

The herds process started from $\delta_{A\cup B}$ is stochastically dominated
(in the sense of the partial order $\preceq$) by
$(\pi(\widetilde{\Xi}_{t}))_{t\geqslant 0}$.

###### Proof of Lemma 2.8.

Fix $p\geqslant 1$ and disjoint sets $A,B\in P_{\mathsf{f}}(\mathbb{T}^{d})$.
Let $(\widetilde{\Xi}_{t})_{t\geqslant 0}$ denote a two-type herds process
started from $\delta_{(A,B)}$, defined under a probability measure
$\widetilde{\mathbb{P}}$ (with expectation operator $\widetilde{\mathbb{E}}$).
By Lemma 2.9(b), and the fact that $X(\cdot)$ is monotone with respect to the
partial order $\preceq$, we have

$\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A\cup
B}]\leqslant\widetilde{\mathbb{E}}[X(\pi(\widetilde{\Xi}_{t}))^{p}].$

Next, noting that $X(\pi(\widetilde{\Xi}_{t}))\leqslant
X(\pi_{1}(\widetilde{\Xi}_{t}))+X(\pi_{2}(\widetilde{\Xi}_{t}))$, we have

$\widetilde{\mathbb{E}}[X(\pi(\widetilde{\Xi}_{t}))^{p}]\leqslant\widetilde{\mathbb{E}}[(X(\pi_{1}(\widetilde{\Xi}_{t}))+X(\pi_{2}(\widetilde{\Xi}_{t}))^{p}].$

Putting these inequalities together (raised to the power $1/p$) and using
Minkowski’s inequality, we obtain

$\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A\cup
B}]^{1/p}\leqslant\widetilde{\mathbb{E}}[X(\pi_{1}(\widetilde{\Xi}_{t}))^{p}]^{1/p}+\widetilde{\mathbb{E}}[X(\pi_{2}(\widetilde{\Xi}_{t}))^{p}]^{1/p}.$

By Lemma 2.9(a), the right-hand side equals

$\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{A}]^{1/p}+\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\delta_{B}]^{1/p}.$

This completes the proof. ∎

######  Remark 2.3.

It is worth mentioning a curious fact here, which is the main reason for
introducing the two-type herds process. Let $A,B\in
P_{\mathsf{f}}(\mathbb{T}^{d})$ be disjoint. Then, a natural guess would be
that the number of particles in the herds process starting from
$\delta_{A}+\delta_{B}$ should stochastically dominate the number of particles
in the process starting from $\delta_{A\cup B}$, since in the former case
there is a priori more space for the particles to spread. However, there seems
to be no simple proof of this fact, and it is not even clear whether it should
be true or not. In a natural choice of coupling, one would try to map
particles of the process started from $\delta_{A\cup B}$ injectively into
particles of the process started from $\delta_{A}+\delta_{B}$, and make it so
that when a particle of the former process dies or gives birth, its image
under the injective mapping does the same. However, this does not work. For
instance, when starting from $\delta_{A\cup B}$, it could be that at a later
time, a single split would separate more particles than in the process
starting from $\delta_{A}+\delta_{B}$, which in turn could after another birth
event give rise to a larger number of particles in the process starting from
$\delta_{A\cup B}$.

######  Remark 2.4.

The notion of two-type herds process can of course be generalized to a multi-
type herds process. Given any integer $k\geqslant 1$, the $k$-type herds
process is the continuous-time Markov chain on

$\mathcal{S}_{k}:=\\{\xi:P_{\mathsf{f},k}(\mathbb{T}^{d})\to\mathbb{N}_{0},\text{
with }\textstyle{\sum_{(A_{1},\dots,A_{k})}}\xi(A_{1},\dots,A_{k})<\infty\\},$

where

$P_{\mathsf{f},k}(\mathbb{T}^{d}):=\\{(A_{1},\ldots,A_{k}):A_{1},\ldots,A_{k}\subseteq\mathbb{T}^{d},\;\cup_{j=1}^{k}A_{j}\neq\varnothing\\}$

and where, like in the two-type herds process, every type obeys birth and
death mechanisms as in the original herds process, ignoring the other types,
but they all share the same splitting events. Naturally, an analogue of Lemma
2.9 holds as well in this general setting. This remark will be used in the
proof of Lemma 3.15 below.

##  3 Analysis of the herds process through a growth index

###  3.1 Definition and properties of growth index

For any $p\geqslant 1$, define the growth index of order $p$ as

$\varphi_{p}=\varphi_{p}(\lambda,\mathsf{v}):=\inf_{t\geqslant
0}\;\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}^{p}]^{1/t}.$ (10)

In case $p=1$, we omit the subscript, so that

$\varphi:=\varphi_{1}.$

Note that we have

$\varphi_{p}^{t}\leqslant\mathbb{E}[X_{t}^{p}],\qquad t\geqslant
0,\;p\geqslant 1.$ (11)

Moreover, (7) implies that

$\mathbb{E}[X_{t+s}^{p}]\leqslant\mathbb{E}[X_{t}^{p}]\cdot\mathbb{E}[X_{s}^{p}],\qquad
t,s\geqslant 0,\;p\geqslant 1,$ (12)

and Fekete’s lemma then ensures that

$\lim_{t\to\infty}\mathbb{E}[X_{t}^{p}]^{1/t}=\varphi_{p},\qquad p\geqslant
1.$ (13)

It will also be useful to observe that

$[1,\infty)\ni p\mapsto\varphi_{p}^{1/p}\text{ is non-decreasing.}$ (14)

To see this, let $p\geqslant q\geqslant 1$. We bound, for any $t\geqslant 0$:

$\mathbb{E}[X_{t}^{p}]=\mathbb{E}[(X_{t}^{q})^{p/q}]\geqslant\mathbb{E}[X_{t}^{q}]^{p/q},$

by Jensen’s inequality. Hence,

$(\mathbb{E}[X_{t}^{p}]^{1/t})^{1/p}\geqslant(\mathbb{E}[X_{t}^{q}]^{1/t})^{1/q}.$

By taking $t\to\infty$ and using (13), we obtain
$\varphi_{p}^{1/p}\geqslant\varphi_{q}^{1/q}$, as desired.

For the rest of this section, we focus on the growth index with $p=1$. We will
analyse higher values of $p$ in Section 3.4.

We state a lemma with an upper bound that, apart from a constant prefactor,
matches (11) in the case $p=1$:

######  Lemma 3.1.

There is a constant $C=C(\lambda,\mathsf{v})$, such that for any $t\geqslant
0$,

$\mathbb{E}[X_{t}]\leqslant C\cdot\varphi^{t}.$ (15)

Before proving this, we state and prove an auxiliary result, concerning the
expected number of herds containing a single particle, after one time unit of
the dynamics has elapsed.

######  Lemma 3.2.

There is a constant $\rho=\rho(\lambda,\mathsf{v})$ such that for any
$\xi\in\mathcal{S}$, we have

$\mathbb{E}\left[\left.\sum_{A:|A|=1}\Xi_{1}(A)\;\right|\;\Xi_{0}=\xi\right]\geqslant\rho\cdot
X(\xi).$ (16)

###### Proof.

By Lemma 2.5 and the linearity of expectation, it suffices to show that there
exists $\rho>0$ such that for any $A\in P_{\mathsf{f}}(\mathbb{T}^{d})$,

$\mathbb{E}\left[\left.\sum_{A^{\prime}:|A^{\prime}|=1}\Xi_{1}(A^{\prime})\;\right|\;\Xi_{0}=\delta_{A}\right]\geqslant\rho\cdot|A|.$

To prove this, fix $A\in P_{\mathsf{f}}(\mathbb{T}^{d})$, and note that the
left-hand side above is larger than

$\sum_{u\in
A}\mathbb{E}[\Xi_{1}(\\{u\\})\mid\Xi_{0}=\delta_{A}]\geqslant\sum_{u\in
A}\mathbb{P}(\Xi_{1}(\\{u\\})>0\mid\Xi_{0}=\delta_{A}).$

It is easy to see that there is a constant $\rho>0$, depending only on
$\lambda$ and $\mathsf{v}$, such that the probability in the sum in the right-
hand side is larger than $\rho$ (for any $A$ and $u$). This is achieved by
prescribing that the particle present at $u$ at time $0$ does not die or give
birth until time $1$, and moreover this particle becomes separated, through
successive splits in the edges that are incident to $u$, of any other particle
in its herd. This shows that the right-hand side above is larger than
$\rho|A|$, completing the proof. ∎

###### Proof of Lemma 3.1.

For any $s,t\geqslant 0$ we have

$\mathbb{E}[X_{t+s}\mid\mathcal{F}_{s}]=\sum_{A}\Xi_{s}(A)\cdot\mathbb{E}[X_{t}\mid\Xi_{0}=\delta_{A}]\geqslant\sum_{A:|A|=1}\Xi_{s}(A)\cdot\mathbb{E}[X_{t}],$

where the equality follows from Lemma 2.5 and the Markov property, and the
inequality from Lemma 2.4. Then, by taking expectations and using Lemma 3.2,
we obtain that

$\mathbb{E}[X_{t+s}]\geqslant\mathbb{E}\left[\sum_{A:|A|=1}\Xi_{s}(A)\right]\cdot\mathbb{E}[X_{t}].$

In case $s\geqslant 1$, by Lemma 3.2 and the Markov property, the right-hand
side is larger than

$\rho\cdot\mathbb{E}[X_{s-1}]\cdot\mathbb{E}[X_{t}].$

Further, by Proposition 2.7, letting $\kappa:=1/\mathbb{E}[X_{1}]$, the above
is larger than

$\kappa\rho\cdot\mathbb{E}[X_{s}]\cdot\mathbb{E}[X_{t}].$

Using this recursively, we obtain, for any $t>0$ and $n\in\mathbb{N}$,

$\mathbb{E}[X_{nt}]\geqslant(\kappa\rho)^{n-1}\cdot\mathbb{E}[X_{t}]^{n},$

so that

$\mathbb{E}[X_{t}]\leqslant(\kappa\rho)^{-\frac{n-1}{n}}\cdot\mathbb{E}[X_{nt}]^{\frac{1}{n}}=(\kappa\rho)^{-\frac{n-1}{n}}\cdot(\mathbb{E}[X_{nt}]^{\frac{1}{nt}})^{t}.$

Using (13), we obtain

$\mathbb{E}[X_{t}]\leqslant\liminf_{n\to\infty}\left((\kappa\rho)^{-\frac{n-1}{n}}\cdot(\mathbb{E}[X_{nt}]^{\frac{1}{nt}})^{t}\right)=C\cdot\varphi^{t},$

with $C=\tfrac{1}{\kappa\rho}$, proving the lemma. ∎

Together with the fact that
$(\lambda,\mathsf{v})\mapsto\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}]$ is
continuous, we deduce that
$(\lambda,\mathsf{v})\mapsto\varphi(\lambda,\mathsf{v})$ is both upper- and
lower-semicontinuous, hence it is continuous. Moreover, we have the following
simple characterization of the supercritical regime. Recall the definition of
$\bar{\lambda}(\mathsf{v})$ from Definition 2.6.

######  Lemma 3.3.

For any $\lambda>0$ and $\mathsf{v}>0$, the following are equivalent:

  * (a)

the herds process survives with positive probability;

  * (b)

$\varphi>1$;

  * (c)

$\mathbb{E}[X_{t}]\xrightarrow{t\to\infty}\infty$.

Consequently, for any $\mathsf{v}>0$,

$\varphi(\bar{\lambda}(\mathsf{v}),\mathsf{v})=1.$ (17)

###### Proof.

The fact that (b) and (c) are equivalent follows from the fact that for any
$t\geqslant 0$, $\varphi^{t}\leqslant\mathbb{E}[X_{t}]\leqslant C\varphi^{t}$.

Now, if (a) holds, then we must also have
$X_{t}\xrightarrow{t\to\infty}\infty$ with positive probability, as otherwise
using the conditional Borel-Cantelli Lemma and a standard argument, we would
get a contradiction. Then (c) follows from Fatou’s Lemma.

Conversely, assume that (c) holds. Let $Z_{t}:=\sum_{A:|A|=1}\Xi_{t}(A)$
denote the number of herds in $\Xi_{t}$ with a single particle in them. By
Lemma 3.2, we have $\mathbb{E}[Z_{t+1}]\geqslant\rho\cdot\mathbb{E}[X_{t}]$.
It follows that there exists some $T>0$ such that $\mathbb{E}[Z_{T}]\geqslant
2$. Since different herds evolve independently of each other, we deduce that
$(Z_{nT})_{n\geqslant 0}$ dominates a supercritical branching process, and
therefore survives forever with positive probability. Since it is dominated by
$(X_{nT})_{n\geqslant 0}$, we get that (a) is satisfied.

Having established the equivalence between (a) and (b), the equality (17)
follows from the continuity of $\varphi$. ∎

###  3.2 Strict monotonicity of growth index

Our goal in this section is to prove the following result.

######  Proposition 3.4.

The map $(\lambda,\mathsf{v})\mapsto\varphi(\lambda,\mathsf{v})$ is strictly
increasing in both arguments.

Before discussing the proof of this, let us see how it allows us to prove
Theorem 1.3:

###### Proof of Theorem 1.3.

Let $\mathsf{v}^{\prime}>\mathsf{v}>0$. We have

$\varphi(\bar{\lambda}(\mathsf{v}^{\prime}),\mathsf{v}^{\prime})=1=\varphi(\bar{\lambda}(\mathsf{v}),\mathsf{v})<\varphi(\bar{\lambda}(\mathsf{v}),\mathsf{v}^{\prime}),$

where the two equalities are given by (17) and the inequality by the strict
monotonicity of $\varphi$. Again using the strict monotonicity of $\varphi$,
we conclude from
$\varphi(\bar{\lambda}(\mathsf{v}^{\prime}),\mathsf{v}^{\prime})<\varphi(\bar{\lambda}(\mathsf{v}),\mathsf{v}^{\prime})$
that $\bar{\lambda}(\mathsf{v}^{\prime})<\bar{\lambda}(\mathsf{v}).$ ∎

The proof of Proposition 3.4 will require several steps. We start with a
definition.

######  Definition 3.1.

Fix the parameters $\mathsf{v}$ and $\lambda$ of the herds process. Given
$\xi\in\mathcal{S}$ and $t>0$, we let

$g_{\mathsf{v}}(\xi,t):=\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\xi(A)\sum_{\begin{subarray}{c}e\text{
active}\\\ \text{edge of
}A\end{subarray}}(\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\delta_{A_{e,1}}+\delta_{A_{e,2}}]-\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\delta_{A}]),$
(18)

and

$h_{\lambda}(\xi,t):=\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\xi(A)\sum_{\begin{subarray}{c}x\in A,\;y\notin
A,\\\ x\sim
y\end{subarray}}(\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\delta_{A\cup\\{y\\}}]-\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\delta_{A}])$
(19)

(we omit $\lambda$ from the notation for $g_{\mathsf{v}}$ and we omit
$\mathsf{v}$ from the notation for $h_{\lambda}$).

The functions $g_{\mathsf{v}}$ and $h_{\lambda}$ give a measure of the total
impact on the number of particles at time $t$ of splitting the herds of $\xi$
at time zero and having a birth at time zero, respectively.

######  Proposition 3.5.

For any $T>0$ we have

$\frac{\partial}{\partial\mathsf{v}}\mathbb{E}_{\lambda,\mathsf{v}}[X_{T}]=\int_{0}^{T}\mathbb{E}_{\lambda,\mathsf{v}}[g_{\mathsf{v}}(\Xi_{t},T-t)]\;\mathrm{d}t,$
(20)

and

$\frac{\partial}{\partial\lambda}\mathbb{E}_{\mathsf{v},\lambda}[X_{T}]=\int_{0}^{T}\mathbb{E}_{\mathsf{v},\lambda}[h_{\lambda}(\Xi_{t},T-t)]\;\mathrm{d}t.$
(21)

The proof is postponed to Section 3.3, and we now prove another intermediate
result.

######  Lemma 3.6.

Let $\xi^{\prime}$ consist of a single herd with exactly two particles, which
are neighbors, and $\xi^{\prime\prime}$ consist of two herds, each containing
a single particle. Then, there exists $\gamma>0$ (depending continuously on
$\lambda$ and $\mathsf{v}$) such that for any $t\geqslant 1$,

$\mathbb{E}[X_{t}\mid\Xi_{0}=\xi^{\prime\prime}]\geqslant\mathbb{E}[X_{t}\mid\Xi_{0}=\xi^{\prime}]+\gamma\cdot\mathbb{E}[X_{t}\mid
X_{0}=\delta_{\\{o\\}}].$

###### Proof.

Fix $v\sim o$. Without loss of generality, we assume that $\xi^{\prime}$
consists of the herd $\\{o,v\\}$ and $\xi^{\prime\prime}$ consists of the
herds $\\{o\\}$ and $\\{v\\}$. We define a coupling of the two herds processes
$(\Xi^{\prime}_{s})$ and $(\Xi^{\prime\prime}_{s})$ starting respectively from
$\xi^{\prime}$ and $\xi^{\prime\prime}$: first we take independent random
variables, as follows:

  * •

$\tau_{o}$ and $\tau_{v}$, both $\sim\mathrm{Exp}(1)$;

  * •

for each $u\sim o$, $\tau_{o,u}\sim\mathrm{Exp}(\lambda)$;

  * •

for each $u\sim v$, $\tau_{v,u}\sim\mathrm{Exp}(\lambda)$;

  * •

$\tau_{\mathrm{split}}\sim\mathrm{Exp}(\mathsf{v})$.

Additionally, let $\tau^{\prime}$ denote the minimum of all these random
variables, and $\tau:=\min(1,\tau^{\prime})$. Now, the coupling is defined as
follows. In all cases, we let
$(\Xi^{\prime}_{s},\Xi_{s}^{\prime\prime})=(\xi^{\prime},\xi^{\prime\prime})$
for $s\in[0,\tau)$; the definition of
$(\Xi^{\prime}_{\tau},\Xi_{\tau}^{\prime\prime})$ will be split into several
cases, but after time $\tau$, we let $\Xi_{\tau}^{\prime}$ and
$\Xi_{\tau}^{\prime\prime}$ continue evolving independently as two herds
processes with split rate $\mathsf{v}$. The definition of
$(\Xi_{\tau}^{\prime},\Xi_{\tau}^{\prime\prime})$ is as follows: if
$\tau=1<\tau^{\prime}$, then
$(\Xi_{\tau}^{\prime},\Xi_{\tau}^{\prime\prime})=(\xi^{\prime},\xi^{\prime\prime})$.
Otherwise:

  * •

if $\tau=\tau_{o}$, then
$\Xi_{\tau}^{\prime}=\Xi^{\prime\prime}_{\tau}=\delta_{\\{v\\}}$; similarly if
$\tau=\tau_{v}$, then
$\Xi_{\tau}^{\prime}=\Xi^{\prime\prime}_{\tau}=\delta_{\\{o\\}}$;

  * •

if for some $u\sim o$, $\tau=\tau_{o,u}$, then
$\Xi_{\tau}^{\prime}=\delta_{\\{o,u,v\\}}$ and
$\Xi^{\prime\prime}_{\tau}=\delta_{\\{o,u\\}}+\delta_{\\{v\\}}$;

  * •

if for some $u\sim v$, $\tau=\tau_{v,u}$, then
$\Xi_{\tau}^{\prime}=\delta_{\\{o,u,v\\}}$ and
$\Xi^{\prime\prime}_{\tau}=\delta_{\\{o\\}}+\delta_{\\{u,v\\}}$;

  * •

if $\tau=\tau_{\mathrm{split}}$, then
$\Xi_{\tau}^{\prime}=\Xi_{\tau}^{\prime\prime}=\delta_{\\{o\\}}+\delta_{\\{v\\}}$.

We let $\widehat{\mathbb{P}}$ denote a probability measure under which this
coupling is defined, and $\widehat{\mathbb{E}}$ be the associated expectation
operator. Also let $(\mathcal{F}_{t})_{t\geqslant 0}$ denote the natural
filtration of $(\Xi_{t}^{\prime},\Xi_{t}^{\prime\prime})_{t\geqslant 0}$.

Fix $t\geqslant 1$. Using Lemma 2.8 and inspecting all cases concerning
$\tau$, it is easy to check that

$\widehat{\mathbb{E}}[X(\Xi_{t}^{\prime\prime})\mid\mathcal{F}_{\tau}]\geqslant\widehat{\mathbb{E}}[X(\Xi_{t}^{\prime})\mid\mathcal{F}_{\tau}].$
(22)

Define the good event $E:=\\{\tau=\tau_{o,v}\\}\cup\\{\tau=\tau_{v,o}\\}$, and
note that on this event, $\Xi^{\prime\prime}_{\tau}$ contains
$\Xi_{\tau}^{\prime}$ plus an additional herd with a single particle in it.
Hence,

$\widehat{\mathbb{E}}[X(\Xi_{t}^{\prime\prime})\mid\mathcal{F}_{\tau}]\cdot\mathds{1}_{E}=\left(\widehat{\mathbb{E}}[X(\Xi_{t}^{\prime})\mid\mathcal{F}_{\tau}]+F(t-\tau)\right)\cdot\mathds{1}_{E},$
(23)

where $F(s):=\mathbb{E}[X_{s}\mid\Xi_{0}=\delta_{\\{o\\}}]$.

We now write

$\displaystyle\mathbb{E}[X_{t}\mid\Xi_{0}=\xi^{\prime\prime}]$
$\displaystyle=\widehat{\mathbb{E}}[X(\Xi^{\prime\prime}_{t})]=\widehat{\mathbb{E}}[\widehat{\mathbb{E}}[X(\Xi^{\prime\prime}_{t})\mid\mathcal{F}_{\tau}]\cdot\mathds{1}_{E}+\widehat{\mathbb{E}}[X(\Xi^{\prime\prime}_{t})\mid\mathcal{F}_{\tau}]\cdot\mathds{1}_{E^{c}}]$

and using (22) and (23), we bound the right-hand side from below by

$\displaystyle\widehat{\mathbb{E}}[(\widehat{\mathbb{E}}[X(\Xi^{\prime}_{t})\mid\mathcal{F}_{\tau}]+F(t-\tau))\cdot\mathds{1}_{E}+\widehat{\mathbb{E}}[X(\Xi^{\prime}_{t})\mid\mathcal{F}_{\tau}]\cdot\mathds{1}_{E^{c}}]$
$\displaystyle\geqslant\widehat{\mathbb{E}}[X(\Xi^{\prime}_{t})]+\widehat{\mathbb{E}}[F(t-\tau)\cdot\mathds{1}_{E}]$
$\displaystyle\geqslant\mathbb{E}[X_{t}\mid\Xi_{0}=\xi^{\prime}]+\widehat{\mathbb{P}}(E)\cdot\min_{t-1\leqslant
s\leqslant t}F(s).$

Using (7) we have that $F(s)\cdot F(t-s)\geqslant F(t)$ for any $s\in[t-1,t]$,
which gives

$\min_{t-1\leqslant s\leqslant t}F(s)\geqslant F(t)\cdot\left(\min_{0\leqslant
r\leqslant 1}F(r)\right)^{-1}.$

The lemma is thus proved with
$\gamma:=\widehat{\mathbb{P}}(E)\cdot(\min_{0\leqslant t\leqslant
1}F(r))^{-1}$. ∎

###### Proof of Proposition 3.4.

We only prove the strict monotonicity in $\mathsf{v}$, the argument for the
strict monotonicity in $\lambda$ is entirely similar. We start with some basic
observations. Let $X_{t}^{\prime}$ denote the number of herds in the herds
process at time $t$ which contain exactly two particles, these particles being
neighbors. We claim that

$\mathbb{E}[X_{t}^{\prime}]\geqslant c\cdot\mathbb{E}[X_{t-1}]\quad\text{for
any }t\geqslant 1,$ (24)

with $c$ some positive constant depending continuously on $\mathsf{v}$. To see
this, recall that if we denote by $Z_{t}$ the number of herds of $\Xi_{t}$
that contain a single particle, then (as in the proof of Lemma 3.1) one has
$\mathbb{E}[Z_{t-1/2}]\geqslant c_{1}\cdot\mathbb{E}[X_{t-1}]$, for some
constant $c_{1}>0$, depending continuously on $\mathsf{v}$. Since in any half
unit of time, a herd with a single particle can be transformed in a herd with
two neighboring particles, at a constant price (depending continuously on
$\mathsf{v}$), this gives the claim (24).

Recalling the definition of $g_{\mathsf{v}}$ in Definition 3.1, by Lemma 3.6
we have

$g_{\mathsf{v}}(\Xi_{s},t-s)\geqslant\gamma\cdot
X^{\prime}_{s}\cdot\mathbb{E}[X_{t-s}].$

Together with Proposition 3.5 and (24), this gives for any $\mathsf{v}>0$, and
any $t\geqslant 1$, with $F(\mathsf{v},t)=\mathbb{E}_{\mathsf{v}}[X_{t}]$,

$\frac{\partial F}{\partial\mathsf{v}}(\mathsf{v},t)\geqslant
c\gamma\cdot\int_{0}^{t}\mathbb{E}[X_{s-1}]\cdot\mathbb{E}[X_{t-s}]\,ds.$

Applying then Proposition 2.7, gives

$\frac{\partial F}{\partial\mathsf{v}}(\mathsf{v},t)\geqslant c^{\prime}\cdot
t\cdot F(\mathsf{v},t),$

where $c^{\prime}>0$ depends continuously on $\mathsf{v}$. This implies that,
for any fixed $0<\mathsf{v}_{1}<\mathsf{v}_{2}$,

$\log\frac{F(\mathsf{v}_{2},t)}{F(\mathsf{v}_{1},t)}\geqslant\rho\cdot
t\cdot(\mathsf{v}_{2}-\mathsf{v}_{1}),$

for some $\rho>0$. Thus, by taking the limit as $t\to\infty$ and using (13),
we get

$\varphi(\mathsf{v}_{1},\lambda)\leqslant
e^{-\rho(\mathsf{v}_{2}-\mathsf{v}_{1})}\cdot\varphi(\mathsf{v}_{2},\lambda).$

∎

###  3.3 Proof of derivative formulas

We now turn to establishing (20) and (21). The proofs are entirely analogous,
so we only do the former. A few of the more technical points of the proof are
done in the appendix.

Recall the definition of the function $g_{\mathsf{v}}(\xi,t)$ in (18). We now
define the closely related function:

$\begin{split}g_{\mathsf{v},\varepsilon}(\xi,t):=\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\xi(A)\sum_{\begin{subarray}{c}e\text{
active}\\\ \text{edge of
}A\end{subarray}}&(\mathbb{E}_{\lambda,\mathsf{v}+\varepsilon}[X_{t}\mid\Xi_{0}=\delta_{A_{e,1}}+\delta_{A_{e,2}}]\\\\[-19.91684pt]
&\hskip
56.9055pt-\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\delta_{A}]),\end{split}$
(25)

where $\mathsf{v}>0$ and $\varepsilon>0$. Note that the expression for
$g_{\mathsf{v},\varepsilon}$ only differs from that for $g_{\mathsf{v}}$ in
that in the former, the first expectation that appears in the right-hand side
is under parameters $\lambda$, $\mathsf{v}+\varepsilon$ rather than $\lambda$,
$\mathsf{v}$.

The following integrability result will be useful. The proof is done in the
appendix.

######  Lemma 3.7.

For any $T>0$ and $k\geqslant 1$, we have

$\mathbb{E}_{\lambda,\mathsf{v}}\left[\max_{0\leqslant t\leqslant
T}|g_{\mathsf{v}}(\Xi_{t},T-t)|^{k}\right]<\infty\quad\text{and}\quad\mathbb{E}_{\lambda,\mathsf{v}}\left[\max_{0\leqslant
t\leqslant T}|g_{\mathsf{v},\varepsilon}(\Xi_{t},T-t)|^{k}\right]<\infty.$

The following definition will give an alternative expression for
$g_{\mathsf{v}}$ and $g_{\mathsf{v},\varepsilon}$, in (26) and (27) below.

######  Definition 3.2.

Given $\xi\in\mathcal{S}$, let $\mathcal{G}(\xi)$ denote the set of all herd
configurations $\xi^{\prime}$ that can be obtained by performing a single
split on $\xi$. Given $\xi^{\prime}\in\mathcal{G}(\xi)$, let $A$ be the
(unique) herd shape that is split into two to obtain $\xi^{\prime}$ from
$\xi$; let $\mathsf{m}(\xi,\xi^{\prime}):=\xi(A)$.

To further clarify this definition, fix an enumeration
$\xi=\sum_{i=1}^{m}\delta_{A_{i}}$ of $\xi$. Then, $\mathcal{G}(\xi)$ is the
set of $\xi^{\prime}\in\mathcal{S}$ with

$\xi^{\prime}=\sum_{i\neq
j}\delta_{A_{i}}+\delta_{(A_{j})_{e,1}}+\delta_{(A_{j})_{e,2}},$

where $j\in\\{1,\ldots,m\\}$ and $e$ is an active edge of $A_{j}$. For
$\xi^{\prime}$ as in the above display, we have
$\mathsf{m}(\xi,\xi^{\prime})=\xi(A_{j})$.

We now observe that, using Lemma 2.5, we can rewrite

$g_{\mathsf{v}}(\xi,t)=\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\mathsf{m}(\xi,\xi^{\prime})\cdot(\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\xi^{\prime}]-\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\xi])$
(26)

and

$g_{\mathsf{v},\varepsilon}(\xi,t)=\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\mathsf{m}(\xi,\xi^{\prime})\cdot(\mathbb{E}_{\lambda,\mathsf{v}+\varepsilon}[X_{t}\mid\Xi_{0}=\xi^{\prime}]-\mathbb{E}_{\lambda,\mathsf{v}}[X_{t}\mid\Xi_{0}=\xi]).$
(27)

Fix $\mathsf{v}>0$, $\lambda>0$ and $\varepsilon>0$. We will now construct a
coupling $(\mathcal{V}_{t},\mathcal{W}_{t})_{t\geqslant 0}$ under a
probability measure $\widehat{\mathbb{P}}$ (with dependence on
$\mathsf{v},\lambda,\varepsilon$ omitted) so that $(\mathcal{V}_{t})$ is a
herds process with parameters $\lambda$, $\mathsf{v}$, and $(\mathcal{W}_{t})$
is a herds process with parameters $\lambda$, $\mathsf{v}+\varepsilon$; both
these processes are started from a single herd with a single particle (at the
root of $\mathbb{T}^{d}$).

######  Definition 3.3 (Coupling $(\mathcal{V}_{t},\mathcal{W}_{t})$).

Take a probability space with probability measure $\widehat{\mathbb{P}}$ under
which a herds process $(\mathcal{V}_{t})_{t\geqslant 0}$ with parameters
$\lambda$, $\mathsf{v}$ is defined, started from $\delta_{\\{o\\}}$. Assume
that the split jumps of $(\mathcal{V}_{t})$ are given as follows: splitting
instructions arise with rate $\mathsf{v}+\varepsilon$ (rather than
$\mathsf{v}$), but they are rejected with probability
$\frac{\varepsilon}{\mathsf{v}+\varepsilon}$. Let

$\tau_{\mathrm{sep}}:=\inf\\{t\geqslant 0:\;\text{a splitting instruction is
rejected at time $t$}\\}.$

We define $(\mathcal{W}_{t})_{t\geqslant 0}$ as follows. For $0\leqslant
t<\tau_{\mathrm{sep}}$, we set $\mathcal{W}_{t}=\mathcal{V}_{t}$. At time
$\tau_{\mathrm{sep}}$, this process obeys the splitting instruction that was
rejected by $(\mathcal{V}_{t})$. We then let
$(\mathcal{W}_{t})_{t\geqslant\tau_{\mathrm{sep}}}$ continue evolving from
$\mathcal{W}_{\tau_{\mathrm{sep}}}$ as a herds process with parameters
$\lambda$, $\mathsf{v}+\varepsilon$, independent of
$(\mathcal{V}_{t})_{t\geqslant\tau_{\mathrm{sep}}}$. Finally, we let

$\mathcal{X}_{t}=X(\mathcal{V}_{t}),\qquad\mathcal{Y}_{t}=X(\mathcal{W}_{t}),\qquad
t\geqslant 0.$

For the rest of this section, we fix $T>0$.

######  Definition 3.4.

We define the process $(\mathcal{A}_{t})_{0\leqslant t\leqslant T}$ as

$\mathcal{A}_{t}:=\mathds{1}\\{\tau_{\mathrm{sep}}\leqslant
t\\}\cdot\widehat{\mathbb{E}}[\mathcal{Y}_{T}-\mathcal{X}_{T}\mid\mathcal{F}_{\tau_{\mathrm{sep}}}],\quad
0\leqslant t\leqslant T.$

That is, in the event $\\{\tau_{\mathrm{sep}}>T\\}$ we have
$\mathcal{A}_{t}\equiv 0$, whereas in $\\{\tau_{\mathrm{sep}}\leqslant T\\}$,
this process takes just two values: $\mathcal{A}_{t}=0$ for
$t\in[0,\tau_{\mathrm{sep}})$ and
$\mathcal{A}_{t}=\widehat{\mathbb{E}}[\mathcal{Y}_{T}-\mathcal{X}_{T}\mid\mathcal{F}_{\tau_{\mathrm{sep}}}]$
for $t\in[\tau_{\mathrm{sep}},T]$. Our interest in this process stems from the
fact that

$\begin{split}\mathbb{E}_{\lambda,\mathsf{v}+\varepsilon}[X_{T}]-\mathbb{E}_{\lambda,\mathsf{v}}[X_{T}]&=\widehat{\mathbb{E}}[\mathcal{Y}_{T}-\mathcal{X}_{T}]\\\
&=\widehat{\mathbb{E}}[(\mathcal{Y}_{T}-\mathcal{X}_{T})\cdot\mathds{1}\\{\tau_{\mathrm{sep}}\leqslant
T\\}]\\\
&=\widehat{\mathbb{E}}[\widehat{\mathbb{E}}[(\mathcal{Y}_{T}-\mathcal{X}_{T})\mid\mathcal{F}_{\tau_{\mathrm{sep}}}]\cdot\mathds{1}\\{\tau_{\mathrm{sep}}\leqslant
T\\}]=\widehat{\mathbb{E}}[\mathcal{A}_{T}].\end{split}$ (28)

We now compute the right derivative with respect to time of the conditional
expectation of $\mathcal{A}_{t}$. This lemma is where the function
$g_{\mathsf{v},\varepsilon}$ enters the picture.

######  Lemma 3.8.

For any $t\in[0,T)$, on the event $\\{\tau_{\mathrm{sep}}>t\\}$ we have

$\left.\frac{\mathrm{d}}{\mathrm{d}s}\widehat{\mathbb{E}}[\mathcal{A}_{t+s}\mid\mathcal{F}_{t}]\right|_{s=0+}=\varepsilon\cdot
g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t).$ (29)

###### Proof.

We abbreviate (27) by writing

$g_{\mathsf{v},\varepsilon}(\xi,s)=\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\mathsf{m}(\xi,\xi^{\prime})\cdot\beta(\xi,\xi^{\prime},s),$

where

$\beta(\xi,\xi^{\prime},s):=\mathbb{E}_{\lambda,\mathsf{v}+\varepsilon}[X_{s}\mid\Xi_{0}=\xi^{\prime}]-\mathbb{E}_{\lambda,\mathsf{v}}[X_{s}\mid\Xi_{0}=\xi],\quad\xi\in\mathcal{S},\;\xi^{\prime}\in\mathcal{G}(\xi),\;s>0.$

Fix $s>0$ so that $t+s\leqslant T$, and fix $\xi\in\mathcal{S}$. For each
$\xi^{\prime}\in\mathcal{G}(\xi)$, let $E(\xi^{\prime})$ be the event that:

  * •

$\tau_{\mathrm{sep}}\in(t,t+s]$,

  * •

the first jump of $(\mathcal{V}_{r},\mathcal{W}_{r})_{t\leqslant r\leqslant
t+s}$ is the one that occurs at time $\tau_{\mathrm{sep}}$, and

  * •

$\mathcal{W}_{\tau_{\mathrm{sep}}}=\xi^{\prime}$.

On the event $\\{\tau_{\mathrm{sep}}>t,\;\Xi_{t}=\xi\\}$, we have

$\displaystyle\widehat{\mathbb{E}}[\mathcal{A}_{t+s}\mid\mathcal{F}_{t}]-\widehat{\mathbb{E}}[\mathcal{A}_{t}\mid\mathcal{F}_{t}]$
$\displaystyle=\widehat{\mathbb{E}}[\mathcal{A}_{t+s}\mid\mathcal{F}_{t}]$
$\displaystyle=\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\widehat{\mathbb{E}}[\mathds{1}_{E(\xi^{\prime})}\cdot\beta(\xi,\xi^{\prime},T-\tau_{\mathrm{sep}})\mid\mathcal{F}_{t}]+o(s),$

where the $o(s)$ term (which of course refers to when $s\to 0$) comes from
events where there are multiple jumps in $(t,t+s]$. The above sum equals

$\begin{split}&\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\beta(\xi,\xi^{\prime},T-t)\cdot\widehat{\mathbb{P}}(E(\xi^{\prime})\mid\mathcal{F}_{t})\\\
&+\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\widehat{\mathbb{E}}[\mathds{1}_{E(\xi^{\prime})}\cdot(\beta(\xi,\xi^{\prime},T-\tau_{\mathrm{sep}})-\beta(\xi,\xi^{\prime},T-t))\mid\mathcal{F}_{t}].\end{split}$
(30)

We will treat the two sums separately. The absolute value of the second sum is
bounded by

$\left(\sup_{\xi^{\prime}\in\mathcal{G}(\xi),\;u\in(t,t+s]}|\beta(\xi,\xi^{\prime},T-u)-\beta(\xi,\xi^{\prime},T-t)|\right)\cdot\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\widehat{\mathbb{P}}(E(\xi^{\prime})\mid\mathcal{F}_{t}).$

As $s\to 0$, the supremum tends to zero and the sum is bounded by 1, so the
whole expression is $o(s)$.

We now turn to the first sum in (30). As $s\to 0$ we have

$\widehat{\mathbb{P}}(E(\xi^{\prime})\mid\mathcal{F}_{t})=(\mathsf{v}+\varepsilon)\cdot\frac{\varepsilon}{\mathsf{v}+\varepsilon}\cdot\mathsf{m}(\xi,\xi^{\prime})\cdot
s+o(s)=\varepsilon s\cdot\mathsf{m}(\xi,\xi^{\prime})+o(s),$

so the sum equals

$\varepsilon
s\sum_{\xi^{\prime}\in\mathcal{G}(\xi)}\mathsf{m}(\xi,\xi^{\prime})\cdot\beta(\xi,\xi^{\prime},T-t)+o(s)=\varepsilon
s\cdot g_{\mathsf{v},\varepsilon}(\xi,T-t)+o(s).$

We have thus proved that

$\mathds{1}\\{\tau_{\mathrm{sep}}>t\\}\cdot(\widehat{\mathbb{E}}[\mathcal{A}_{t+s}\mid\mathcal{F}_{t}]-\widehat{\mathbb{E}}[\mathcal{A}_{t}\mid\mathcal{F}_{t}])=\mathds{1}\\{\tau_{\mathrm{sep}}>t\\}\cdot(\varepsilon
s\cdot g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)+o(s)),$

so (29) follows. ∎

Next, we obtain the expression for the derivative with respect to time of the
(non-conditional) expectation of $\mathcal{A}_{t}$.

######  Lemma 3.9.

For $t\in[0,T)$, we have

$\frac{\mathrm{d}}{\mathrm{d}t}\widehat{\mathbb{E}}[\mathcal{A}_{t}]=\varepsilon\cdot\widehat{\mathbb{E}}[\mathds{1}\\{\tau_{\mathrm{sep}}>t\\}\cdot
g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)].$ (31)

The first step in establishing this lemma is noting that, for $0\leqslant
t<t+s\leqslant T$,

$\frac{\widehat{\mathbb{E}}[\mathcal{A}_{t+s}]-\widehat{\mathbb{E}}[\mathcal{A}_{t}]}{s}=\widehat{\mathbb{E}}\left[\mathds{1}\\{\tau_{\mathrm{sep}}>t\\}\cdot\frac{\widehat{\mathbb{E}}[\mathcal{A}_{t+s}\mid\mathcal{F}_{t}]}{s}\right],$

since $\mathcal{A}_{t+s}=\mathcal{A}_{t}$ on $\\{\tau_{\mathrm{sep}}\leqslant
t\\}$, and $\mathcal{A}_{t}=0$ on $\\{\tau_{\mathrm{sep}}>t\\}$. We would now
like to take $s$ to zero (from the right only, at least at first) and use
Lemma 3.8, but we need to exchange the limit and the expectation; formally:

$\lim_{s\to
0+}\widehat{\mathbb{E}}\left[\mathds{1}\\{\tau_{\mathrm{sep}}>t\\}\cdot\frac{\widehat{\mathbb{E}}[\mathcal{A}_{t+s}\mid\mathcal{F}_{t}]}{s}\right]=\widehat{\mathbb{E}}\left[\mathds{1}\\{\tau_{\mathrm{sep}}>t\\}\cdot\lim_{s\to
0+}\frac{\widehat{\mathbb{E}}[\mathcal{A}_{t+s}\mid\mathcal{F}_{t}]}{s}\right].$
(32)

The justification of this exchange is done with a standard dominated
convergence argument, but an additional bound is required, so we postpone the
full proof of Lemma 3.9 to the Appendix.

###### Proof of (20).

Fix $\varepsilon>0$. Using (28) and Lemma 3.9, we have

$\frac{\mathbb{E}_{\lambda,\mathsf{v}+\varepsilon}[X_{T}]-\mathbb{E}_{\lambda,\mathsf{v}}[X_{T}]}{\varepsilon}=\int_{0}^{T}\widehat{\mathbb{E}}[\mathds{1}\\{\tau_{\mathrm{sep}}>t\\}\cdot
g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)]\;\mathrm{d}t.$

By Fubini’s theorem (which we can use since we have the integrability
condition given in Lemma 3.7), the right-hand side above equals

$\widehat{\mathbb{E}}\left[\int_{0}^{\tau_{\mathrm{sep}}\wedge
T}g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)\;\mathrm{d}t\right].$

We write this as

$\begin{split}&\widehat{\mathbb{E}}\left[\int_{0}^{T}g_{\mathsf{v}}(\mathcal{V}_{t},T-t)\;\mathrm{d}t\right]\\\
&+\widehat{\mathbb{E}}\left[\int_{0}^{T}(g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)-g_{\mathsf{v}}(\mathcal{V}_{t},T-t))\;\mathrm{d}t\right]-\widehat{\mathbb{E}}\left[\int_{\tau_{\mathrm{sep}}}^{T}g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)\;\mathrm{d}t\right].\end{split}$
(33)

Note that, since the law of $(\mathcal{V}_{t})$ under $\widehat{\mathbb{P}}$
equals the law of $(\Xi_{t})$ under $\mathbb{P}_{\lambda,\mathsf{v}}$, we have

$\widehat{\mathbb{E}}\left[\int_{0}^{T}g_{\mathsf{v}}(\mathcal{V}_{t},T-t)\;\mathrm{d}t\right]=\mathbb{E}_{\lambda,\mathsf{v}}\left[\int_{0}^{T}g_{\mathsf{v}}(\Xi_{t},T-t)\;\mathrm{d}t\right].$

Hence, the proof will be completed once we prove that the second and third
expectations in (33) tend to zero as $\varepsilon\to 0$.

It is straightforward to show that, for any $\xi\in\mathcal{S}$ and any
$t\in[0,T]$,

$g_{\mathsf{v},\varepsilon}(\xi,t)\xrightarrow{\varepsilon\to
0}g_{\mathsf{v}}(\xi,t).$

Combining this with the dominated convergence theorem (using Lemma 3.7), we
obtain

$\widehat{\mathbb{E}}\left[\int_{0}^{T}(g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)-g_{\mathsf{v}}(\mathcal{V}_{t},T-t))\;\mathrm{d}t\right]\xrightarrow{\varepsilon\to
0}0.$

Next, using the Cauchy-Schwarz inequality, we bound

$\displaystyle\left|\widehat{\mathbb{E}}\left[\int_{\tau_{\mathrm{sep}}}^{T}g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)\;\mathrm{d}t\right]\right|$
$\displaystyle\leqslant T\cdot\widehat{\mathbb{E}}\left[\left(\max_{0\leqslant
t\leqslant
T}|g_{\mathsf{v},\varepsilon}(\mathcal{V}_{t},T-t)|^{2}\right)\right]^{1/2}\cdot\widehat{\mathbb{P}}(\tau_{\mathrm{sep}}\leqslant
T)^{1/2}.$

The expectation on the right-hand side is finite by Lemma 3.7, and it is
straightforward to check that
$\widehat{\mathbb{P}}(\tau_{\mathrm{sep}}\leqslant
T)\xrightarrow{\varepsilon\to 0}0$. This completes the proof. ∎

###  3.4 Analysis of higher moments

Throughout this section, we fix $\lambda$ and $\mathsf{v}$ with
$\lambda<\bar{\lambda}(\mathsf{v})$ (recalling the definition of
$\bar{\lambda}(\mathsf{v})$ in Definition 2.6).

We now analyse the growth index $\varphi_{p}$ for $p$ possibly larger than 1.
Our main goal is to prove the following.

######  Proposition 3.10.

If $\lambda<\bar{\lambda}(\mathsf{v})$, then for every $p\geqslant 1$ we have

$\varphi_{p}<1$ (34)

and

$\sup_{t\geqslant 0}\mathbb{E}[X_{t}^{p}]<\infty.$ (35)

Note that the case $p=1$ has already been proved: the fact that $\varphi<1$
when $\lambda<\bar{\lambda}(\mathsf{v})$ is given by (17) and Proposition 3.4,
and then (35) follows from $\varphi<1$ and (15).

In order to prove Proposition 3.10, we shall need an intermediate result,
which we now state.

######  Lemma 3.11.

Let $p\geqslant 2$. There exists $\mathfrak{C}_{p}>0$ (depending on $\lambda$,
$\mathsf{v}$ and $p$) such that for any $s\geqslant 12p\log(2d)/\mathsf{v}$,

$\mathbb{E}\left[\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\Xi_{s}(A)\cdot|A|^{p}\right]\leqslant\mathfrak{C}_{p}\cdot\big{(}\mathbb{E}[X_{s}^{3/2}]+\varphi^{s}\big{)}.$

The proof of this lemma is quite involved, and we postpone it to the next
section. We now show how to obtain Proposition 3.10 from it.

###### Proof of Proposition 3.10.

Fix $\lambda<\bar{\lambda}(\mathsf{v})$. Note that (35) follows readily from
(34) and (13), so we only need to prove (34).

By (14), it suffices to prove that $\varphi_{p}<1$ for all $p\in\mathbb{N}$,
and the case $p=1$ is already done. We proceed by induction, fixing
$p\in\\{2,3,\ldots\\}$ and assuming that $\varphi_{q}<1$ for all
$q\in\\{1,\ldots,p-1\\}$.

We first claim that there exist $C,c>0$ such that, for all $t\geqslant 0$ and
$\xi\in\mathcal{S}$,

$\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\xi]\leqslant\left(\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\xi(A)\cdot|A|^{p}\right)\cdot\mathbb{E}[X_{t}^{p}]+X(\xi)^{p}\cdot
C\mathrm{e}^{-ct}.$ (36)

This bound is a refinement of Proposition 2.7. While in the proof of that
proposition we used Minkowski’s inequality, here we expand the $p$-th power of
a sum in full and bound the various terms that appear.

To prove (36), let $t\geqslant 0$ and $\xi\in\mathcal{S}$ with enumeration
$\xi=\sum_{i=1}^{m}\delta_{A_{i}}$. By Lemma 2.5, $(\Xi_{t})_{t\geqslant 0}$
started from $\Xi_{0}=\xi$ has the same distribution as
$(\Xi^{(1)}_{t}+\cdots+\Xi^{(m)}_{t})_{t\geqslant 0}$, where
$(\Xi^{(1)}_{t})_{t\geqslant 0}$, $\ldots$, $(\Xi^{(m)}_{t})_{t\geqslant 0}$
are independent herds processes, with $\Xi^{(i)}_{0}=\delta_{A_{i}}$ for each
$i$. In particular,

$\displaystyle\mathbb{E}[X_{t}^{p}\mid\Xi_{0}=\xi]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{i=1}^{m}X(\Xi^{(i)}_{t})\right)^{p}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}(a_{1},\ldots,a_{m}):\\\
a_{1}+\cdots+a_{m}=p\end{subarray}}\frac{p!}{a_{1}!\cdots
a_{m}!}\cdot\prod_{\begin{subarray}{c}i\in\\{1,\ldots,m\\}:\\\
a_{i}>0\end{subarray}}\mathbb{E}[X(\Xi_{t}^{(i)})^{a_{i}}].$

By the fact that $\Xi^{(i)}_{0}=\delta_{A_{i}}$ and Proposition 2.7, the
right-hand side is smaller than

$\sum_{\begin{subarray}{c}(a_{1},\ldots,a_{m}):\\\
a_{1}+\cdots+a_{m}=p\end{subarray}}\frac{p!}{a_{1}!\cdots
a_{m}!}\cdot\prod_{\begin{subarray}{c}i\in\\{1,\ldots,m\\}:\\\
a_{i}>0\end{subarray}}|A_{i}|^{a_{i}}\cdot\mathbb{E}[X_{t}^{a_{i}}].$ (37)

We break this sum as

$\mathbb{E}[X_{t}^{p}]\cdot\sum_{i=1}^{m}|A_{i}|^{p}+\sum_{\begin{subarray}{c}(a_{1},\ldots,a_{m}):\\\
a_{1}+\cdots+a_{m}=p,\\\
a_{1},\ldots,a_{m}<p\end{subarray}}\frac{p!}{a_{1}!\cdots
a_{m}!}\cdot\prod_{\begin{subarray}{c}i\in\\{1,\ldots,m\\}:\\\
a_{i}>0\end{subarray}}|A_{i}|^{a_{i}}\cdot\mathbb{E}[X_{t}^{a_{i}}].$ (38)

Note that the first sum can be written as

$\mathbb{E}[X_{t}^{p}]\cdot\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\xi(A)\cdot|A|^{p}.$

Next, the induction hypothesis that $\varphi_{a}<1$ for all
$a\in\\{1,\ldots,p-1\\}$ together with (13) imply that there exist $C,c>0$
(not depending on $t$) such that $\mathbb{E}[X_{t}^{a}]\leqslant Ce^{-ct}$ for
any $a\in\\{1,\ldots,p-1\\}$. Hence, the second sum in (38) is smaller than

$\displaystyle\sum_{\begin{subarray}{c}a_{1},\ldots,a_{m}\in\mathbb{N}_{0}:\\\
a_{1}+\cdots+a_{m}=p,\\\
a_{1},\ldots,a_{m}<p\end{subarray}}\frac{p!}{a_{1}!\cdots
a_{m}!}\cdot\prod_{\begin{subarray}{c}i\in\\{1,\ldots,m\\}:\\\
a_{i}>0\end{subarray}}|A_{i}|^{a_{i}}\cdot C\mathrm{e}^{-ct}.$

By forgetting the last condition in the summation and increasing the value of
$C$ if necessary, this is smaller than

$\displaystyle
C\mathrm{e}^{-ct}\cdot\sum_{\begin{subarray}{c}a_{1},\ldots,a_{m}\in\mathbb{N}_{0}:\\\
a_{1}+\cdots+a_{m}=p\end{subarray}}\frac{p!}{a_{1}!\cdots
a_{m}!}\cdot\prod_{\begin{subarray}{c}i\in\\{1,\ldots,m\\}:\\\
a_{i}>0\end{subarray}}|A_{i}|^{a_{i}}=C\mathrm{e}^{-ct}\cdot X(\xi)^{p}.$

We have thus proved (36).

Now, (36) and the Markov property imply that, for any $s,t\geqslant 0$,

$\mathbb{E}[X_{t+s}^{p}]\leqslant\mathbb{E}\Big{[}\sum_{A}\Xi_{s}(A)\cdot|A|^{p}\Big{]}\cdot\mathbb{E}[X_{t}^{p}]+\mathbb{E}[X_{s}^{p}]\cdot
C\mathrm{e}^{-ct}.$ (39)

Using the bound of Lemma 3.11, increasing the constant $C$ if necessary, for
any $s,t$ large enough we then have

$\mathbb{E}[X_{t+s}^{p}]\leqslant
C\left\\{\mathbb{E}[X_{s}^{3/2}]\cdot\mathbb{E}[X_{t}^{p}]+\varphi^{s}\cdot\mathbb{E}[X_{t}^{p}]+\mathbb{E}[X_{s}^{p}]\cdot\mathrm{e}^{-ct}\right\\}.$
(40)

We also bound

$\displaystyle\mathbb{E}[X_{s}^{3/2}]$
$\displaystyle=\mathbb{E}[X_{s}^{3/2}\cdot\mathds{1}\\{X_{s}>0\\}]$
$\displaystyle\leqslant\mathbb{E}[(X_{s}^{3/2})^{4/3}]^{3/4}\cdot\mathbb{P}(X_{s}>0)^{1/4}$
$\displaystyle\leqslant\mathbb{E}[X_{s}^{2}]^{3/4}\cdot\mathbb{P}(X_{s}\neq
0)^{1/4}\leqslant\mathbb{E}[X_{s}^{2}]^{3/4}\cdot\mathbb{E}[X_{s}]^{1/4}\leqslant
C\mathbb{E}[X_{s}^{p}]^{3/4}\cdot\varphi^{s/4},$

where the first inequality is Hölder’s, the second inequality follows from
$\mathds{1}\\{X_{s}\neq 0\\}\leqslant X_{s}$ and the third inequality follows
from $X_{s}^{2}\leqslant X_{s}^{p}$ and (15). We use this bound in (40),
together with the fact that $\varphi<1$, to obtain

$\mathbb{E}[X_{t+s}^{p}]\leqslant
C\left\\{\mathbb{E}[X_{s}^{p}]^{3/4}\cdot\mathbb{E}[X_{t}^{p}]\cdot\mathrm{e}^{-cs}+\mathbb{E}[X_{t}^{p}]\cdot\mathrm{e}^{-cs}+\mathbb{E}[X_{s}^{p}]\cdot\mathrm{e}^{-ct}\right\\}$
(41)

for suitable choices of $c,C$.

Now, assume for a contradiction that $\varphi_{p}\geqslant 1$. In that case,
by (11) we have $\mathbb{E}[X_{r}^{p}]\geqslant 1$ for all $r\geqslant 0$, and
from (41) we obtain, for large enough $s,t$ with $s\leqslant t$:

$\mathbb{E}[X_{t+s}^{p}]\leqslant
C\mathbb{E}[X_{s}^{p}]\cdot\mathbb{E}[X_{t}^{p}]\cdot\mathrm{e}^{-cs}.$

Using this recursively, we have that for all sufficiently large $s$ and all
$n\in\mathbb{N}$,

$\mathbb{E}[X_{ns}^{p}]\leqslant
C^{n}\cdot\mathbb{E}[X_{s}^{p}]^{n}\cdot\mathrm{e}^{-cns}.$

Taking both sides to the power $\frac{1}{ns}$ and letting $n\to\infty$ (using
(13)) gives

$\varphi_{p}\leqslant
C^{1/s}\cdot\mathbb{E}[X_{s}^{p}]^{1/s}\cdot\mathrm{e}^{-c}.$

Now letting $s\to\infty$ and again using (13) yields
$\varphi_{p}\leqslant\varphi_{p}\cdot\mathrm{e}^{-c}$, a contradiction. ∎

Before we turn to the proof of Lemma 3.11, we want to give a consequence of
Proposition 2.7, namely Corollary 3.13 below, which will be useful in dealing
with the contact process on dynamic graphs. For $t\geqslant 0$, we denote by
$N_{t}$ the number of birth events in the herds process up to time $t$, as in
Lemma 2.1. Also let $N_{\infty}:=\lim_{n\to\infty}N_{t}$.

######  Lemma 3.12.

Let $p\geqslant 1$. For any $t\in[0,\infty]$ and $\xi\in\mathcal{S}$, we have

$\mathbb{E}[N_{t}^{p}\mid\Xi_{0}=\xi]\leqslant
X(\xi)^{p}\cdot\mathbb{E}[N_{t}^{p}].$

Consequently, for any $s\in[0,\infty)$ and $t\in[0,\infty]$,

$\mathbb{E}[(N_{s+t}-N_{s})^{p}]\leqslant\mathbb{E}[X_{s}^{p}]\cdot\mathbb{E}[N_{t}^{p}].$
(42)

###### Proof.

First, recall Remark 2.4, which in particular shows that one can dominate the
number of particles in a herds process starting from $\xi$ by the total number
of particles in a multi-type herds process with $\ell:=X(\xi)$ types, starting
from the configuration $\xi^{\prime}$ where each particle in $\xi$ represents
a distinct type. For this auxiliary process, let $N_{t}^{(i)}$ denote the
number of births of particles of type $i$ by time $t$, for
$i\in\\{1,\ldots,\ell\\}$. Then,

$\mathbb{E}[N_{t}^{p}\mid\Xi_{0}=\xi]\leqslant\mathbb{E}\left[\left(\sum_{i=1}^{\ell}N_{t}^{(i)}\right)^{p}\right]\leqslant\left(\sum_{i=1}^{\ell}\mathbb{E}[(N_{t}^{(i)})^{p}]^{1/p}\right)^{p},$

where we have used Minkowski’s inequality. Now, since each type evolves a
usual herds process, we have
$\mathbb{E}[(N_{t}^{(i)})^{p}]=\mathbb{E}[N_{t}^{p}]$ for every $i$, so the
right-hand side above equals $\ell^{p}\cdot\mathbb{E}[N_{t}^{p}]$, as
required. ∎

######  Corollary 3.13.

If $\lambda<\bar{\lambda}(\mathsf{v})$, then
$\mathbb{E}[N_{\infty}^{p}]<\infty$ for all $p\geqslant 1$.

###### Proof.

Fix $p\geqslant 1$. For any $x>1$, let
$t_{x}:=\frac{p+1}{|\log\varphi|}\cdot\log x$ (note that $\varphi<1$ since
$\lambda<\bar{\lambda}(\mathsf{v})$, by Lemma 3.3). Letting $\tau$ denote the
extinction time of the herds process, we first bound

$\displaystyle\mathbb{P}(N_{\infty}>x)$
$\displaystyle\leqslant\mathbb{P}(\tau>t_{x})+\mathbb{P}(N_{t_{x}}>x).$

The first term on the right-hand side is easy to bound:

$\mathbb{P}(\tau>t_{x})\leqslant\mathbb{E}[X_{t_{x}}]\stackrel{{\scriptstyle\eqref{eq_const}}}{{\leqslant}}C\varphi^{t_{x}}=Cx^{-(p+1)}.$

Next, we bound

$\displaystyle\mathbb{P}(N_{t_{x}}>x)$
$\displaystyle\leqslant\sum_{i=0}^{\lfloor
t_{x}\rfloor-1}\mathbb{P}\left(N_{k+1}-N_{k}>\frac{x}{t_{x}}\right)$
$\displaystyle\leqslant\sum_{i=0}^{\lfloor
t_{x}\rfloor-1}\frac{\mathbb{E}[(N_{k+1}-N_{k})^{p+1}]}{(x/t_{x})^{p+1}}\leqslant
t_{x}^{p+2}\cdot x^{-(p+1)}\cdot\sup_{t\geqslant
0}\mathbb{E}[(N_{t+1}-N_{t})^{p+1}].$

Now, the supremum on the right-hand side is finite by (35) and (42). We have
thus proved that $\mathbb{P}(N_{\infty}>x)\leqslant C(\log x)^{p+2}x^{-(p+1)}$
for some $C>0$, which implies that $N_{\infty}$ has finite $p$-th moment. ∎

###  3.5 Bound on moments of herd sizes: proof of Lemma 3.11

We will need several preliminary results, starting with the following.

######  Lemma 3.14.

For any $\alpha\geqslant 1$ and $p\geqslant 1$, there exists $C_{\alpha,p}>0$
(depending on $\lambda$, $\mathsf{v}$, $\alpha$ and $p$) such that the
following holds. Fix $u\in\mathbb{T}^{d}\backslash\\{o\\}$ and let
$(\widetilde{\Xi}_{t})_{t\geqslant 0}$ be a two-type herds process with rates
$\lambda$ and $\mathsf{v}$, started from a single herd containing a type-1
particle at the root and a type-2 particle at $u$, that is,
$\widetilde{\Xi}_{0}=\delta_{\\{o\\},\\{u\\}}$. Then, letting
$t_{\alpha}:=12\log(\alpha)/\mathsf{v}$, we have

$\mathbb{E}\left[\left(\sum_{(A,B):A\neq\varnothing}\widetilde{\Xi}_{t_{\alpha}}(A,B)\cdot|B|\right)^{p}\;\right]<C_{\alpha,p}\cdot\alpha^{-\mathrm{dist}(o,u)}.$
(43)

###### Proof.

Fix $\lambda$, $\mathsf{v}$ and $\alpha$, let
$t_{\alpha}:=12\log(\alpha)/\mathsf{v}$ and fix $u$ as in the statement. For
$t\geqslant 0$, let $Y_{t}$ denote the number of herds in
$\widetilde{\Xi}_{t}$ that contain both types, that is,

$Y_{t}:=\sum_{\begin{subarray}{c}(A,B):\\\ A\neq\varnothing,\\\
B\neq\varnothing\end{subarray}}\widetilde{\Xi}_{t}(A,B).$

It will be useful to note that

$s\leqslant t\quad\Longrightarrow\quad\\{Y_{s}=0\\}\subseteq\\{Y_{t}=0\\}.$
(44)

Noting that

$\left(\sum_{(A,B):A\neq\varnothing}\widetilde{\Xi}_{t_{\alpha}}(A,B)\cdot|B|\right)^{p}=\left(\sum_{(A,B):A\neq\varnothing}\widetilde{\Xi}_{t_{\alpha}}(A,B)\cdot|B|\right)^{p}\cdot\mathds{1}\\{Y_{t_{\alpha}}>0\\}$

and using the Cauchy-Schwarz inequality, the left-hand side of (43) is smaller
than

$\displaystyle\mathbb{E}\left[\left(\sum_{(A,B):A\neq\varnothing}\widetilde{\Xi}_{t_{\alpha}}(A,B)\cdot|B|\right)^{2p}\right]^{1/2}\cdot\mathbb{P}(Y_{t_{\alpha}}\geqslant
1)^{1/2}.$

Using domination by a pure-birth process, the first term in the product above
can be bounded by a finite constant that only depends on $\lambda$, $p$ and
$\alpha$. We now show that $\mathbb{P}(Y_{t_{\alpha}}\geqslant 1)$ is smaller
than $C\alpha^{-2\mathrm{dist(o,u)}}$ for some $C>0$.

For $i\in\\{1,2\\}$ and $t\geqslant 0$, let $K^{(i)}_{t}$ denote the set of
vertices of $\mathbb{T}^{d}$ that have been occupied by a type-$i$ particle in
some herd for some time $s\leqslant t$, that is,

$\displaystyle
K^{(1)}_{t}:=\\{v\in\mathbb{T}^{d}:\;\widetilde{\Xi}_{s}(A,B)>0\text{ for some
}s\leqslant t\text{ and }(A,B)\text{ with }v\in A\\},$ $\displaystyle
K^{(2)}_{t}:=\\{v\in\mathbb{T}^{d}:\;\widetilde{\Xi}_{s}(A,B)>0\text{ for some
}s\leqslant t\text{ and }(A,B)\text{ with }v\in B\\}.$

We have that $K^{(1)}_{0}=\\{o\\}$, $K^{(2)}_{0}=\\{u\\}$ and $t\mapsto
K^{(1)}_{t}$ and $t\mapsto K^{(2)}_{t}$ are both non-decreasing (with respect
to set inclusion). Moreover, $K^{(1)}_{t}$ and $K^{(2)}_{t}$ are connected
subsets of $\mathbb{T}^{d}$, since they only grow by the inclusion of vertices
neighboring vertices that are already present. Also note that as long as these
sets stay disjoint, there can be at most one herd containing both types. In
other words, letting

$\sigma:=\inf\\{t:K^{(1)}_{t}\cap K^{(2)}_{t}\neq\varnothing\\},$

we have, for any $t\geqslant 0$,

$\\{\sigma>t\\}\subseteq\\{Y_{s}\leqslant 1\text{ for all }s\leqslant t\\}.$
(45)

Next, let

$\ell=\mathrm{dist}(o,u)$

and let $o=u_{0}\sim u_{1}\sim\ldots\sim u_{\ell}=u$ be the vertices of
$\mathbb{T}^{d}$ in the geodesic from $o$ to $u$. Let

$u^{\prime}:=u_{\lfloor\ell/3\rfloor},\quad\sigma^{(1)}:=\inf\\{t\geqslant
0:\;u^{\prime}\in K^{(1)}_{t}\\}$

and

$u^{\prime\prime}:=u_{\lfloor
2\ell/3\rfloor},\quad\sigma^{(2)}:=\inf\\{t\geqslant 0:\;u^{\prime\prime}\in
K^{(2)}_{t}\\}.$

It is easy to see that

$\min(\sigma^{(1)},\sigma^{(2)})\leqslant\sigma.$

Putting this together with (45), we obtain

$\displaystyle\\{Y_{s}\geqslant 2\text{ for some }s\leqslant
t_{\alpha}\\}\subseteq\\{\sigma\leqslant
t_{\alpha}\\}\subseteq\\{\min(\sigma^{(1)},\sigma^{(2)})\leqslant
t_{\alpha}\\},$ (46)

so we can bound

$\displaystyle\mathbb{P}(Y_{t_{\alpha}}\geqslant 1)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq_monotone_Y}}}{{=}}\mathbb{P}(Y_{s}\geqslant
1\text{ for all }0\leqslant s\leqslant t_{\alpha})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq_monotone_Y2}}}{{\leqslant}}\mathbb{P}(\sigma^{(1)}\leqslant
t_{\alpha})+\mathbb{P}(\sigma^{(2)}\leqslant t_{\alpha})$ (47)
$\displaystyle\quad+\mathbb{P}(\min(\sigma^{(1)},\sigma^{(2)})>t_{\alpha},\;Y_{s}=1\text{
for }0\leqslant s\leqslant t_{\alpha}).$ (48)

We now bound the three terms on the right-hand side separately.

Let us first consider the probability in (48). For any $t$, if
$\min(\sigma^{(1)},\sigma^{(2)})>t$ and $Y_{t}=1$, then a split in any of the
edges

$\\{u_{\lfloor\ell/3\rfloor},u_{\lfloor\ell/3\rfloor+1}\\},\;\\{u_{\lfloor\ell/3\rfloor+1},u_{\lfloor\ell/3\rfloor+2}\\},\;\ldots,\;\\{u_{\lfloor
2\ell/3\rfloor-1},\;u_{\lfloor 2\ell/3\rfloor}\\}$

separates the two types permanently, causing $Y$ to drop to zero. This
observation gives

$\displaystyle\mathbb{P}(\min(\sigma^{(1)},\sigma^{(2)})>t_{\alpha},\;Y_{s}=1\text{
for }0\leqslant s\leqslant t_{\alpha})$
$\displaystyle\leqslant\exp\\{-\mathsf{v}\cdot t_{\alpha}\cdot(\lfloor
2\ell/3\rfloor-\lfloor\ell/3\rfloor)\\}$
$\displaystyle\leqslant\alpha^{-2\ell},$

where the second inequality follows from the definition of $t_{\alpha}$.

We now turn to the two probabilities in (47). We only bound the first one; by
a symmetry argument, the same bound will then apply to the second. Let
$(W_{t})_{t\geqslant 0}$ be a growth process on
$(\mathbb{N}_{0})^{\mathbb{T}^{d}}$ defined as follows. We let $W_{0}(o)=1$
and $W_{0}(u)=0$ for $u\neq o$. We interpret $W_{t}(v)=m$ as saying that there
are $m$ particles at $v$ at time $t$. Then, we define the dynamics by
prescribing that independently, for any $v\sim w$, a particle at $v$ gives
birth at a particle at $w$ with rate $\lambda$ (and particles never die). In
particular, $(\sum_{v}W_{t}(v))_{t\geqslant 0}$ is a pure-birth process in
which the birth rate is $d\lambda$. It is easy to see that the set-valued
process $(\\{u\in\mathbb{T}^{d}:\;W_{t}(u)>0\\})_{t\geqslant 0}$
stochastically dominates $(K^{(1)}_{t})_{t\geqslant 0}$, and in particular,

$\mathbb{P}(\sigma^{(1)}\leqslant
t_{\alpha})\leqslant\mathbb{P}(W_{t_{\alpha}}(u^{\prime})>0)\leqslant\mathbb{E}[W_{t_{\alpha}}(u^{\prime})].$
(49)

We now claim that, for any $t\geqslant 0$ and $v\in\mathbb{T}^{d}$,

$\mathbb{E}[W_{t}(v)]=e^{d\lambda t}\cdot p_{t}(v),$ (50)

where $p_{t}(v):=\mathbb{P}(\mathcal{Z}_{t}=v)$, with
$(\mathcal{Z}_{t})_{t\geqslant 0}$ the continuous-time random walk on
$\mathbb{T}^{d}$ which starts at the root at time zero, and jumps from any
vertex to any neighboring vertex with rate $\lambda$. It is simple to verify
(50) using the observations that $(t,v)\mapsto\mathbb{E}[W_{t}(v)]$ is the
solution to

$\left\\{\begin{array}[]{l}\frac{\mathrm{d}}{\mathrm{d}t}g(t,v)=\lambda\sum_{w\sim
v}g(t,w),\;t\geqslant 0,\;v\in\mathbb{T}^{d},\\\\[5.69046pt]
g(0,\cdot)=\delta_{o}(\cdot),\end{array}\right.$

and that the right-hand side of (50) solves this equation, by direct
computation.

Putting together (49) and (50), we have

$\mathbb{P}(\sigma^{(1)}\leqslant t_{\alpha})\leqslant e^{d\lambda
t_{\alpha}}\cdot p_{t_{\alpha}}(u^{\prime})\leqslant e^{d\lambda
t_{\alpha}}\cdot\mathbb{P}(\mathrm{Poi}(d\lambda
t_{\alpha})>\lfloor\ell/3\rfloor),$

where $\mathrm{Poi}(d\lambda t_{\alpha})$ represents a random variable with
the Poisson distribution with parameter $d\lambda t_{\alpha}$, which is the
law of the number of jumps of $(\mathcal{Z}_{t})$ until time $t_{\alpha}$.
Since the tail of the Poisson distribution is lighter than exponential, the
right-hand side above is smaller than $C\alpha^{-2\ell}$ for some $C>0$,
uniformly in $\ell$. This concludes the proof. ∎

######  Lemma 3.15.

For any $p\geqslant 1$, there exists $C_{p}^{\prime}>0$ (depending on
$\lambda$, $\mathsf{v}$ and $p$) such that the following holds. Fix
$B_{0}\subseteq\mathbb{T}^{d}\backslash\\{o\\}$ and let
$(\widetilde{\Xi}_{t})_{t\geqslant 0}$ be a two-type herds process with rates
$\lambda$, $\mathsf{v}$ started from
$\widetilde{\Xi}_{0}=\delta_{\\{o\\},B_{0}}$. Also let
$T_{p}:=12p\log(2d)/\mathsf{v}$. Then, (uniformly over the choice of $B_{0}$),

$\mathbb{E}\left[\left(\sum_{(A,B):A\neq\varnothing}\widetilde{\Xi}_{T_{p}}(A,B)\cdot(|A|+|B|)\right)^{p}\;\right]\leqslant
C_{p}^{\prime}.$

###### Proof.

Let

${R}:=\sum_{(A,B):A\neq\varnothing}\widetilde{\Xi}_{T_{p}}(A,B)\cdot(|A|+|B|);$

note that ${R}$ is the total number of particles in $\widetilde{\Xi}_{T_{p}}$
that belong to herds that contain type-1 particles.

We enumerate $\\{o\\}\cup B_{0}=\\{u_{1},\ldots,u_{m}\\}$, with $u_{1}=o$ and
$m=|B_{0}|+1$. We now define a multi-type herds process, as described in
Remark 2.4. This new process, denoted
$({\mathchoice{\widetilde{\hbox{$\displaystyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\textstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptscriptstyle\widetilde{\Xi}$}}}}_{t})_{t\geqslant
0}$, is taken in the same probability space that we have been considering, has
rates $\lambda$, $\mathsf{v}$, and $m$ types. It starts with a single herd,
with a type-$1$ particle at $u_{1}=o$, a type-2 particle at $u_{2}$, $\ldots$,
and a type $m$ particle at $u_{m}$. In analogy with ${R}$, we let
${R}^{\prime}$ denote the total number of particles in
${\mathchoice{\widetilde{\hbox{$\displaystyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\textstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptscriptstyle\widetilde{\Xi}$}}}}_{T_{p}}$
that belong to herds that contain type-1 particles. That is, if we use an
$m$-tuple $(A_{1},\ldots,A_{m})$ to represent a multi-type herd shape, then

${R}^{\prime}:=\sum_{(A_{1},\ldots,A_{m}):A_{1}\neq\varnothing}{\mathchoice{\widetilde{\hbox{$\displaystyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\textstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptscriptstyle\widetilde{\Xi}$}}}}_{T_{p}}(A_{1},\ldots,A_{m})\cdot(|A_{1}|+\cdots+|A_{m}|).$

With similar reasoning as in the proof of Lemma 2.9, we see that ${R}$ is
stochastically dominated by ${R}^{\prime}$; in particular,

$\mathbb{E}[{R}^{p}]^{1/p}\leqslant\mathbb{E}[({R}^{\prime})^{p}]^{1/p}\leqslant\sum_{j=1}^{m}\mathbb{E}[(R^{\prime}_{j})^{p}]^{1/p},$

where

$R_{j}^{\prime}:=\sum_{(A_{1},\ldots,A_{m}):A_{1}\neq\varnothing}{\mathchoice{\widetilde{\hbox{$\displaystyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\textstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptscriptstyle\widetilde{\Xi}$}}}}_{T_{p}}(A_{1},\ldots,A_{m})\cdot|A_{j}|.$

Note that $R_{1}^{\prime}$ is just the total number of type-1 particles in
${\mathchoice{\widetilde{\hbox{$\displaystyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\textstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptscriptstyle\widetilde{\Xi}$}}}}_{T_{p}}$.
If we ignore all types except for type $1$ in
(${\mathchoice{\widetilde{\hbox{$\displaystyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\textstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptscriptstyle\widetilde{\Xi}$}}}}_{t})$,
we obtain a (one-type) herds process started from $\delta_{\\{o\\}}$; hence,
$\mathbb{E}[(R^{\prime}_{1})^{p}]=\mathbb{E}[X_{T_{p}}^{p}]<\infty$ by
Corollary 2.3. Next, for $j\neq 1$, if we ignore all types except for types
$1$ and $j$ in
$({\mathchoice{\widetilde{\hbox{$\displaystyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\textstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptstyle\widetilde{\Xi}$}}}{\widetilde{\hbox{$\scriptscriptstyle\widetilde{\Xi}$}}}}_{t})$,
we see a two-type herds process started from $\delta_{\\{o\\},\\{u_{j}\\}}$,
and Lemma 3.14 (with $\alpha=(2d)^{p}$) and the definition of $T_{p}$ imply
that $\mathbb{E}[(R_{j}^{\prime})^{p}]\leqslant
C_{p}(2d)^{-p\cdot\mathrm{dist}(o,u_{j})}$. We then have

$\sum_{j=1}^{m}\mathbb{E}[(R_{j}^{\prime})^{p}]^{1/p}\leqslant\mathbb{E}[X_{T_{p}}^{p}]^{1/p}+C_{p}^{1/p}\sum_{j=1}^{m}(2d)^{-\mathrm{dist}(o,u_{j})}.$

The second sum on the right-hand side is smaller than

$\sum_{u\in\mathbb{T}^{d}}(2d)^{-\mathrm{dist}(o,u)}\leqslant\sum_{i=1}^{\infty}d^{i}\cdot(2d)^{-i}=1.$

We have thus proved that
$\mathbb{E}[R^{p}]\leqslant(\mathbb{E}[X_{T_{p}}^{p}]^{1/p}+C_{p}^{1/p})^{p}$,
so the proof is complete. ∎

######  Lemma 3.16.

Let $p\geqslant 1$ and let
$C_{p}^{\prime\prime}:=\max(C_{p}^{\prime},\;\mathbb{E}[X_{T_{p}}^{p}])$,
where $C_{p}^{\prime}$ and $T_{p}$ are as in Lemma 3.15. Then, for any
$\xi\in\mathcal{S}$, the herds process $(\Xi_{t})_{t\geqslant 0}$ with rates
$\lambda$, $\mathsf{v}$ satisfies

$\mathbb{P}\left(\exists A:\;|A|\geqslant
x,\;\Xi_{T_{p}}(A)>0\mid\Xi_{0}=\xi\right)\leqslant
C_{p}^{\prime\prime}\cdot\frac{X(\xi)}{x^{p}},\quad x>0.$

###### Proof.

By using Lemma 2.5 and a union bound, it suffices to prove that for any
$A_{0}\in P_{\mathsf{f}}(\mathbb{T}^{d})$,

$\mathbb{P}\left(\exists A:\;|A|\geqslant
x,\;\Xi_{T_{p}}(A)>0\mid\Xi_{0}=\delta_{A_{0}}\right)\leqslant
C_{p}^{\prime\prime}\cdot\frac{|A_{0}|}{x^{p}},\quad x>0.$ (51)

We will prove this by induction on $|A_{0}|$. For the case where $|A_{0}|=1$,
we bound the left-hand side above by

$\displaystyle\mathbb{P}(X_{t}\geqslant
x\mid\Xi_{0}=\delta_{\\{o\\}})\leqslant\frac{\mathbb{E}[X_{T_{p}}^{p}]}{x^{p}},$

by Markov’s inequality.

Now assume that $|A_{0}|\geqslant 2$ and let $u\in A_{0}$. Let
$B_{0}:=A_{0}\backslash\\{u\\}$. We consider a two-type herds process
$(\widetilde{\Xi}_{t})_{t\geqslant 0}$ with rates $\lambda$, $\mathsf{v}$
started from $\delta_{\\{u\\},B_{0}}$. Using Lemma 2.9(a), the left-hand side
of (51) is smaller than

$\displaystyle\mathbb{P}\left(\exists(A,B):\;|A|+|B|\geqslant
x,\;\widetilde{\Xi}_{T_{p}}(A,B)>0\right).$

In turn, this is smaller than

$\displaystyle\mathbb{P}\left(\exists(A,B):\;A\neq\varnothing,\;|A|+|B|\geqslant
x,\;\widetilde{\Xi}_{T_{p}}(A,B)>0\right)$ (52)
$\displaystyle+\mathbb{P}\left(\exists(A,B):\;|B|\geqslant
x,\;\widetilde{\Xi}_{T_{p}}(A,B)>0\right).$ (53)

The probability in (52) is smaller than

$\mathbb{P}\left(\sum_{(A,B):A\neq\varnothing}\Xi_{T_{p}}(A,B)\cdot(|A|+|B|)\geqslant
x\right)\leqslant\frac{C_{p}^{\prime}}{x^{p}},$

by Markov’s inequality and Lemma 3.15. By Lemma 2.9(b), the probability in
(53) can be expressed using a one-type herds process; it equals

$\mathbb{P}\left(\exists B:\;|B|\geqslant
x,\;\Xi_{T_{p}}(B)>0\mid\Xi_{0}=\delta_{B_{0}}\right),$

which is smaller than $C_{p}^{\prime\prime}|B_{0}|/x^{p}$ by the induction
hypothesis (since $|B_{0}|=|A_{0}|-1$). We have then proved that

$\mathbb{P}\left(\exists A:\;|A|\geqslant
x,\;\Xi_{T_{p}}(A)>0\mid\Xi_{0}=A_{0}\right)\leqslant\frac{C_{p}^{\prime}}{x^{p}}+\frac{C_{p}^{\prime\prime}(|A_{0}|-1)}{x^{p}}\leqslant\frac{C_{p}^{\prime\prime}|A_{0}|}{x^{p}}.$

∎

###### Proof of Lemma 3.11.

Fix $s\geqslant T_{p}=12p\log(2d)/\mathsf{v}$. Let $E_{1}$ be the event that
there is some herd at time $s$ whose number of particles is larger than
$X_{s-T_{p}}^{\frac{1}{2p}}$, that is,

$E_{1}:=\left\\{\text{ there exists }A\in P_{\mathsf{f}}(\mathbb{T}^{d})\text{
with }|A|\geqslant X_{s-T_{p}}^{\frac{1}{2p}}\text{ and
}\Xi_{s}(A)>0\right\\}.$

On $E_{1}^{c}$, we bound

$\sum_{A\in P_{\mathsf{f}}(\mathbb{T}^{d})}\Xi_{s}(A)\cdot|A|^{p}\leqslant
X_{s-T_{p}}^{1/2}\cdot\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\Xi_{s}(A)\leqslant X_{s-T_{p}}^{1/2}\cdot
X_{s}.$

On $E_{1}$, we bound

$\sum_{A\in P_{\mathsf{f}}(\mathbb{T}^{d})}\Xi_{s}(A)\cdot|A|^{p}\leqslant
X_{s}^{p}.$

These bounds give

$\mathbb{E}\left[\sum_{A\in
P_{\mathsf{f}}(\mathbb{T}^{d})}\Xi_{s}(A)\cdot|A|^{p}\right]\leqslant\mathbb{E}[X_{s}\cdot
X_{s-T_{p}}^{1/2}]+\mathbb{E}[X_{s}^{p}\cdot\mathds{1}_{E_{1}}].$ (54)

We treat the two expectations on the right-hand side separately. For the first
one, we start by bounding

$\mathbb{E}[X_{s}\cdot
X_{s-T_{p}}^{1/2}]=\mathbb{E}[\mathbb{E}[X_{s}\mid\mathcal{F}_{s-T_{p}}]\cdot
X_{s-T_{p}}^{1/2}]\leqslant\mathbb{E}[X_{s-T_{p}}^{3/2}]\cdot\mathbb{E}[X_{T_{p}}],$
(55)

where the inequality follows from (6) and the Markov property. We now claim
that there exists $C>0$ (not depending on $s$) such that

$\mathbb{E}[X_{s-T_{p}}^{3/2}]\leqslant C\mathbb{E}[X_{s}^{3/2}].$ (56)

To see this, first note that each particle that is alive at time $s-T_{p}$
will stay alive until time $s$ with probability $q:=\mathrm{e}^{-T_{p}}$.
Then, defining the event

$E_{2}:=\\{X_{s}\geqslant\tfrac{q}{2}\cdot X_{s-T_{p}}\\},$

we have, for any $m\in\mathbb{N}$,

$\mathbb{P}(E_{2}\mid\mathcal{F}_{s-T_{p}})\cdot\mathds{1}\\{X_{s-T_{p}}=m\\}\geqslant\mathbb{P}(\mathrm{Bin}(m,q)\geqslant\tfrac{q}{2}m)$

(and in case $m=0$, the left-hand side is trivially equal to 1). Hence,

$\mathbb{P}(E_{2}\mid\mathcal{F}_{s-T_{p}})\geqslant\beta:=\inf_{m\geqslant
1}\mathbb{P}(\mathrm{Bin}(m,q)\geqslant\tfrac{q}{2}m)>0.$

Then,

$\displaystyle\mathbb{E}[X_{s}^{3/2}]\geqslant\mathbb{E}[X_{s}^{3/2}\cdot\mathds{1}_{E_{2}}]$
$\displaystyle\geqslant\tfrac{q}{2}\cdot\mathbb{E}[X_{s-T_{p}}^{3/2}\cdot\mathds{1}_{E^{\prime}}]$
$\displaystyle=\tfrac{q}{2}\cdot\mathbb{E}[X_{s-T_{p}}^{3/2}\cdot\mathbb{P}(E_{2}\mid\mathcal{F}_{s-T_{p}})]\geqslant\tfrac{q}{2}\cdot\beta\cdot\mathbb{E}[X_{s-T_{p}}^{3/2}],$

proving (56) with $C:=\frac{2}{\beta q}$. With (55) and (56), and putting
together all the terms that do not depend on $s$ in a sufficiently large
constant $C$, we have proved that

$\mathbb{E}[X_{s}\cdot X_{s-T_{p}}^{1/2}]\leqslant C\mathbb{E}[X_{s}^{3/2}].$

We now turn to the second term on the right-hand side of (54). We first bound
the conditional expectation given $\mathcal{F}_{s-T_{p}}$ with Cauchy-Schwarz:

$\displaystyle\mathbb{E}[X_{s}^{p}\cdot\mathds{1}_{E_{1}}\mid\mathcal{F}_{s-T_{p}}]$
$\displaystyle\leqslant\mathbb{E}[X_{s}^{2p}\mid\mathcal{F}_{s-T_{p}}]^{1/2}\cdot\mathbb{P}(E_{1}\mid\mathcal{F}_{s-T_{p}})^{1/2}.$

Using (6) and the Markov property,

$\mathbb{E}[X_{s}^{2p}\mid\mathcal{F}_{s-T_{p}}]\leqslant
X_{s-T_{p}}^{2p}\cdot\mathbb{E}[X_{T_{p}}^{2p}].$

Using Lemma 3.16 (and again the Markov property), we have

$\mathbb{P}(E_{1}\mid\mathcal{F}_{s-T_{p}})\leqslant
C_{4p^{2}}^{\prime\prime}\cdot\frac{X_{s-T_{p}}}{(X_{s-T_{p}}^{1/(2p)})^{4p^{2}}}=C_{4p^{2}}^{\prime\prime}\cdot
X_{s-T_{p}}^{1-2p}.$

Then,

$\mathbb{E}[X_{s}^{p}\cdot\mathds{1}_{E_{1}}\mid\mathcal{F}_{s-T_{p}}]\leqslant
C_{4p^{2}}^{\prime\prime}\cdot\mathbb{E}[X_{T_{p}}^{2p}]\cdot X_{s-T_{p}},$

so

$\mathbb{E}[X_{s}^{p}\cdot\mathds{1}_{E_{1}}]\leqslant
C_{4p^{2}}^{\prime\prime}\cdot\mathbb{E}[X_{T_{p}}^{2p}]\cdot\mathbb{E}[X_{s-T_{p}}]\leqslant
C_{4p^{2}}^{\prime\prime}\cdot\mathbb{E}[X_{T_{p}}^{2p}]\cdot
C\varphi^{s-T_{p}},$

where the second inequality follows from (15). Putting together all the
constants that do not depend on $s$, this gives

$\mathbb{E}[X_{s}^{p}\cdot\mathds{1}_{E_{1}}]\leqslant C\varphi^{s}.$

∎

##  4 Extinction time on a random $d$-regular graph with switching

The goal of this section is to prove Theorem 1.2. As mentioned in the
Introduction, the first part of the theorem was already proved in [dSOV21], so
we only prove the second part here.

This section is organized as follows. In Section 4.1, we give a detailed
construction of the dynamic random graph and the contact process which co-
evolves on this graph. After doing so, we argue that a version of the usual
self-duality relation of the contact process is satisfied here. Due to this
relation, in proving quick extinction, it suffices to study the process
started from a single infection. We start this study in Section 4.2, where we
introduce an exploration process, which reveals the contact process but only
reveals partial information about the graph. In Section 4.3, we prove a
general Markov chain lemma which allows us to couple this exploration process
with (a projection of) the herds process. Finally, in Section 4.4, we take
advantage of this coupling to give the proof of Theorem 4.4.

###  4.1 Preliminaries: dynamic graph, joint evolution, duality

Let us define the class of graphs in which our dynamic graph process takes
values. Fix $n\in\mathbb{N}$ and let $V_{n}:=[n]=\\{1,\ldots,n\\}$. The set
$\\{(u,a):\;u\in V_{n},\>a\in\\{1,\ldots,d\\}\\}$ is called the set of half-
edges. Given a perfect matching of the set of half-edges (that is, a bijection
$\sigma$ from this set to itself with no fixed points and equal to its own
inverse), we can obtain a (multi-)graph by setting $V_{n}$ as the set of
vertices and prescribing that each pair $\\{(u,a),(u^{\prime},a^{\prime})\\}$
with $(u^{\prime},a^{\prime})=\sigma(u,a)$ corresponds to an edge between $u$
and $u^{\prime}$. Let $\mathcal{G}_{n}$ denote the set of all multi-graphs
that can be obtained in this way. Deterministic elements of $\mathcal{G}_{n}$
will typically be denoted by $\mathsf{g}$, whereas random elements of
$\mathcal{G}_{n}$ will be denoted by $G$ or $G_{t}$ (in the case of a
process).

Fix $\mathsf{g}\in\mathcal{G}_{n}$. A switch code for $\mathsf{g}$ is a triple
$\mathsf{m}=(e_{1},e_{2},\eta)$, where $e_{1},e_{2}$ are distinct edges of
$\mathsf{g}$ and $\eta\in\\{-,+\\}$. Fix such a switch code, with
$e_{1}=\\{(u,a),(u^{\prime},a^{\prime})\\}$ and
$e_{2}=\\{(v,b),(v^{\prime},b^{\prime})\\}$ so that
$(u,a)<(u^{\prime},a^{\prime})$ and $(v,b)<(v^{\prime},b^{\prime})$ in
lexicographic order. In case $\eta=+$, we let
$\Gamma^{\mathsf{m}}(\mathsf{g})$ be the graph obtained from $\mathsf{g}$ by
replacing $e_{1}$ and $e_{2}$ by the edges $\\{(u,a),(v,b)\\}$ and
$\\{(u^{\prime},a^{\prime}),(v^{\prime},b^{\prime})\\}$ (and keeping all other
edges intact). In case $\eta=-$, we instead replace $e_{1},e_{2}$ by
$\\{(u,a),(v^{\prime},b^{\prime})\\}$ and
$\\{(u^{\prime},a^{\prime}),(v,b)\\}$.

The random graph process $(G_{t})_{t\geqslant 0}$ is the continuous-time
Markov chain on $\mathcal{G}_{n}$ which jumps from $\mathsf{g}$ to
$\mathsf{g}^{\prime}$ with rate $\upupsilon_{n}:=\frac{\mathsf{v}}{nd}$ if
$\mathsf{g}^{\prime}=\Gamma^{\mathsf{m}}(\mathsf{g})$ for some switch code
$\mathsf{m}$ of $\mathsf{g}$ (and rate 0 otherwise). This chain is reversible
with respect to the uniform measure on $\mathcal{G}_{n}$. We will always start
the graph dynamics from this distribution.

We now fix $\lambda>0$ and define the contact process $(\xi_{t})_{t\geqslant
0}$ with infection rate $\lambda$ on the dynamic graph $(G_{t})$. Although we
could do so by describing the jump rates of the joint Markov chain
$(G_{t},\xi_{t})_{t\geqslant 0}$, we will instead use a Poisson graphical
construction. We take a probability space with probability measure
$\mathbb{P}$ in which the process $(G_{t})$ is defined, and also
(independently of $(G_{t})$), the following Poisson point processes (all
independent) are defined:

  * •

for each vertex $u$, a Poisson point process $R^{u}$ on $[0,\infty)$ with
intensity 1 (recovery times);

  * •

for each half-edge $(u,a)$, a Poisson point process $R^{(u,a)}$ with intensity
$\lambda$ (transmission times).

Naturally, when $t\in R^{u}$, vertex $u$ goes to state 0 (if not already
there) at time $t$. Moreover, when $t\in R^{(u,a)}$, there is a transmission
from $u$ to the vertex $v$ that owns the half-edge to which $(u,a)$ is matched
in $G_{t}$ (so that, if $u$ was in state 1 just before $t$, then $v$ goes to
state 1, if not already there, at $t$). For each $A\subseteq V_{n}$, we let
$(\xi^{A}_{t})_{t\geqslant 0}$ be the contact process on $(G_{t})$ with
$\xi^{A}_{0}=\mathds{1}_{A}$ and obtained from this graphical construction (as
usual, the graphical construction gives us contact processes started from all
possible initial configurations, all coupled in a single probability space and
respecting the monotonicity of set inclusion).

The usual duality relation

$\mathbb{P}(\xi^{A}_{t}\cap B\neq\varnothing)=\mathbb{P}(\xi^{B}_{t}\cap
A\neq\varnothing)\quad\text{for all }t\geqslant 0,\;A,B\subseteq V_{n}$ (57)

holds in this context, but it is important to note that the above
probabilities are annealed in the graph environment. Let us briefly prove
(57). Fix $t\geqslant 0$ and $A,B\subseteq V_{n}$. Letting
$(\mathsf{g}_{s})_{0\leqslant s\leqslant t}$ be a possible realization of the
trajectory of $(G_{s})_{0\leqslant s\leqslant t}$, we have

$\displaystyle\mathbb{P}(\xi^{A}_{t}\cap
B\neq\varnothing\mid(G_{s})_{0\leqslant s\leqslant
t}=(\mathsf{g}_{s})_{0\leqslant s\leqslant t})$
$\displaystyle\quad=\mathbb{P}(\xi^{B}_{t}\cap
A\neq\varnothing\mid(G_{s})_{0\leqslant s\leqslant
t}=(\mathsf{g}_{t-s})_{0\leqslant s\leqslant t}).$

This is verified using a standard argument involving infection paths and time-
reversibility of Poisson processes. Integrating this equality over the choice
of $(\mathsf{g}_{s})_{0\leqslant s\leqslant t}$ and using the fact that
$(G_{s})_{0\leqslant s\leqslant t}$ has the same law as $(G_{t-s})_{0\leqslant
s\leqslant t}$ gives (57).

Letting $\bar{u}\in V_{n}$ be arbitrary (and deterministic) and writing
$\xi^{\bar{u}}_{t}$ instead of $\xi^{\\{\bar{u}\\}}_{t}$, we have

$\mathbb{P}(\xi^{V_{n}}_{t}\neq\varnothing)\leqslant\sum_{u\in
V_{n}}\mathbb{P}(\xi^{V_{n}}_{t}(u)=1)=n\cdot\mathbb{P}(\xi^{V_{n}}_{t}(\bar{u})=1)=n\cdot\mathbb{P}(\xi^{\bar{u}}_{t}\neq\varnothing),$
(58)

where the equalities follow from symmetry and duality, respectively. Due to
(58), the analysis of the extinction time of the contact process started from
all vertices infected can be reduced to the analysis of the extinction time of
the contact process from a single infection at the arbitrary vertex $\bar{u}$.
For the rest of this section, $\bar{u}$ remains fixed.

Next, we describe an exploration process, which only reveals partial
information about $(G_{t})_{t\geqslant 0}$, namely, only the matching of half-
edges at certain points in time on a need-to-know basis imposed by the
transmission times of the contact process.

###  4.2 Exploration process

Let

$\mathcal{P}:=\\{\\{(u,a),(u^{\prime},a^{\prime})\\}:\;u,u^{\prime}\in
V_{n},\;a,a^{\prime}\in\\{1,\ldots,d\\},\;(u,a)\neq(u^{\prime},a^{\prime})\\}$

be the set of all potential edges of our random graph. A set
$\mathcal{E}\subseteq\mathcal{P}$ is called independent if any two elements of
$\mathcal{E}$ have no half-edge in common. Let

$\mathscr{P}:=\\{\mathcal{E}\subseteq\mathcal{P}:\;\mathcal{E}\text{ is
independent}\\}.$ (59)

In the same probability space where $(G_{t})$ and the graphical construction
of the contact process are defined, we now define a process
$(\mathscr{E}_{t})_{t\geqslant 0}$ taking values in $\mathscr{P}$.
Intuitively, $\mathscr{E}_{t}$ represents a set of edges that are known to be
part of $G_{t}$, having been revealed by an exploration induced by the contact
process activity. This process will have the following features:

  * (P1)

it starts from $\mathscr{E}_{0}=\varnothing$;

  * (P1)

for any $t$, every element of $\mathscr{E}_{t}$ is an edge of $G_{t}$;

  * (P3)

the pair $(\xi^{\bar{u}}_{t},\mathscr{E}_{t})_{t\geqslant 0}$ is a Markov
chain;

  * (P4)

for any $t$, conditionally on $(\xi^{\bar{u}}_{t},\mathscr{E}_{t})$, the
distribution of the edges of $G_{t}$ apart from those in $\mathscr{E}_{t}$ is
uniform. More precisely, the pairing in $G_{t}$ of the half-edges in the set
$\\{(u,a):(u,a)\text{ not in any edge of }\mathscr{E}_{t}\\}$ is uniformly
distributed among all possibilities.

In order to define the exploration, we will need auxiliary times. Let $T_{1}$
be the first time in which there is a transmission mark at a half-edge
emanating from $\bar{u}$; let $\mathscr{E}_{t}=\varnothing$ for all
$t\in[0,T_{1})$. In case $T_{1}<\infty$, say, due to a transmission mark at
the half-edge $(\bar{u},a)$, we reveal the half-edge $(v,b)$ to which
$(\bar{u},a)$ is paired in $G_{T_{1}}$, and include the edge
$\\{(\bar{u},a),(v,b)\\}$ in $\mathscr{E}_{T_{1}}$.

Now assume that we have already defined stopping times (with respect to the
filtration of $(G_{t})$ and the graphical construction) $T_{1}\leqslant
T_{2}\leqslant\cdots\leqslant T_{k}$, and that we have defined
$\mathscr{E}_{t}$ for $0\leqslant t\leqslant T_{k}$. In case $T_{k}=\infty$,
set $T_{k+1}=\infty$; from now on, assume that $\\{T_{k}<\infty\\}$ occurs.
Let $T_{k+1}$ be the first time $t>T_{k}$ when:

  * •

either a switch occurs involving at least one edge of $\mathscr{E}_{T_{k}}$
(call this Case 1),

  * •

or “the contact process tries to use an unexplored edge”, that is, a
transmission mark appears at a half-edge emanating from some vertex of
$\xi_{t}$, and this half-edge is not part of an edge of $\mathscr{E}_{T_{k}}$
(Case 2);

We set $\mathscr{E}_{t}=\mathscr{E}_{T_{k}}$ for $t\in(T_{k},T_{k+1})$, and
$\mathscr{E}_{T_{k+1}}$ is defined as follows.

  * •

In Case 1, there are two sub-cases. First assume that the switch at time
$T_{k+1}$ involves an edge $e$ of $\mathscr{E}_{T_{k}}$ and another edge
outside $\mathscr{E}_{T_{k}}$. Then, we let
$\mathscr{E}_{T_{k+1}}=\mathscr{E}_{T_{k}}\backslash\\{e\\}$. Now assume that
the switch at time $T_{k+1}$ involves two edges $e,e^{\prime}$ of
$\mathscr{E}_{T_{k}}$, transforming them into the two new edges
$e^{\prime\prime},e^{\prime\prime\prime}$. We then set
$\mathscr{E}_{T_{k+1}}=(\mathscr{E}_{T_{k}}\backslash\\{e,e^{\prime}\\})\cup\\{e^{\prime\prime},e^{\prime\prime\prime}\\}$.

  * •

In Case 2, we reveal the half-edge that is matched at time $t$ to the half-
edge having the transmission mark at that time; letting $e$ be the edge formed
by these two half-edges, we let
$\mathscr{E}_{T_{k+1}}=\mathscr{E}_{T_{k}}\cup\\{e\\}$.

This completes the description of the exploration, and it should be clear that
properties (P1), (P2), (P3) and (P4) listed earlier are indeed satisfied.

Our next step is to use the exploration process as a tool to couple the
contact process $(\xi^{\bar{u}}_{t})$ with a herds process.

###  4.3 A Markov chain lemma and its application

We now prove a general result about coupling two continuous-time Markov
chains.

######  Lemma 4.1.

Let $\mathcal{X}_{1}$ and $\mathcal{X}_{2}$ be countable sets, and let
$r_{1}:\mathcal{X}_{1}\times\mathcal{X}_{1}\to[0,\infty)$ and
$r_{2}:\mathcal{X}_{2}\times\mathcal{X}_{2}\to[0,\infty)$ be functions
defining the jump rates for continuous-time (non-explosive) Markov chains on
$\mathcal{X}_{1}$ and $\mathcal{X}_{2}$, respectively. Assume that there is a
subset $\mathcal{X}_{1}^{\prime}\subseteq\mathcal{X}_{1}$ and functions
$\Psi:\mathcal{X}_{1}^{\prime}\to\mathcal{X}_{2}$ and
$f:\mathcal{X}_{1}^{\prime}\to[0,\infty)$ such that the following two
conditions hold:

$\sum_{y\in\mathcal{X}_{1}\backslash\mathcal{X}_{1}^{\prime}}r_{1}(x,y)\leqslant
f(x)\quad\text{for all }x\in\mathcal{X}_{1}^{\prime}$ (60)

and

$\sum_{\begin{subarray}{c}z\in\mathcal{X}_{2},\\\
z\neq\Psi(x)\end{subarray}}\left|r_{2}(\Psi(x),z)-\sum_{y\in\Psi^{-1}(z)}r_{1}(x,y)\right|\leqslant
f(x)\quad\text{for all }x\in\mathcal{X}_{1}^{\prime}.$ (61)

Fix $\bar{x}\in\mathcal{X}_{1}^{\prime}$. Then, there exists a coupling
$(\mathcal{A}_{t},\mathcal{B}_{t})_{t\geqslant 0}$ on
$\mathcal{X}_{1}\times\mathcal{X}_{2}$ with the following properties:

  * (a)

$\mathcal{A}_{0}=\bar{x}$ and $(\mathcal{A}_{t})_{t\geqslant 0}$ is a Markov
chain on $\mathcal{X}_{1}$ with jump rates $r_{1}$;

  * (b)

$\mathcal{B}_{0}=\Psi(\bar{x})$ and $(\mathcal{B}_{t})_{t\geqslant 0}$ is a
Markov chain on $\mathcal{X}_{2}$ with jump rates $r_{2}$;

  * (c)

letting

$\sigma:=\inf\\{t:\mathcal{B}_{t}\neq\Psi(\mathcal{A}_{t})\\}$

and, for any $a>0$,

$T_{a}:=\inf\\{t:f(\mathcal{A}_{t})>a\\},$

we have, for any $t>0$,

$\mathbb{P}(\sigma\leqslant t\wedge T_{a})\leqslant 2at.$

###### Proof.

We will define a continuous-time Markov chain
$(\mathcal{A}_{t},\mathcal{B}_{t},\mathcal{W}_{t})_{t\geqslant 0}$ taking
values in the set

$\\{(x,\Psi(x),1):\;x\in\mathcal{X}_{1}^{\prime}\\}\cup\\{(x,y,0):\;x\in\mathcal{X}_{1},\;y\in\mathcal{X}_{2}\\},$
(62)

starting from $(\bar{x},\Psi(\bar{x}),1)$. The pair
$(\mathcal{A}_{t},\mathcal{B}_{t})$ will satisfy the properties in the
statement. The third coordinate process $(\mathcal{W}_{t})$ will be a non-
decreasing process (it jumps at most once, from 1 to 0) with the property that
for all $t\leqslant\inf\\{s:\mathcal{W}_{s}=0\\}$, we have
$\mathcal{B}_{t}=\Psi(\mathcal{A}_{t})$. So, we interpret $\mathcal{W}_{t}$ as
the indicator of the event that “the coupling still works at time $t$”.

In order to define this chain, we need to specify the jump rates. When the
third coordinate equals zero (meaning that the coupling is already broken),
the first and second coordinates move independently, according to the chains
defined by $r_{1}$ (on $\mathcal{X}_{1}$) and $r_{2}$ (on $\mathcal{X}_{2}$),
respectively. More precisely, from any triple of the form $(x,y,0)$, the chain
jumps as follows:

  * •

for each $x^{\prime}\in\mathcal{X}_{1}$, it jumps to $(x^{\prime},y,0)$ with
rate $r_{1}(x,x^{\prime})$;

  * •

for each $y^{\prime}\in\mathcal{X}_{2}$, it jumps to $(x,y^{\prime},0)$ with
rate $r_{2}(y,y^{\prime})$.

We now need to specify the jump rates from points in the first set in the
union in (62). In order to do so, we first introduce some notation. For each
$x\in\mathcal{X}_{1}^{\prime}$, we let

$[x]:=\Psi^{-1}(\Psi(x))\subseteq\mathcal{X}_{1}^{\prime}.$

For each $x\in\mathcal{X}_{1}$ and each $S\subseteq\mathcal{X}_{1}$, we write

$r_{1}(x,S):=\sum_{y\in S}r_{1}(x,y).$

Now, fix $x\in\mathcal{X}_{1}^{\prime}$. The following list describes all the
possible jumps that the chain can take from $(x,\Psi(x),1)$ (this starting
location is kept fixed throughout the list), and their respective rates:

  * •

$\mathcal{A}$ and $\mathcal{B}$ jump together, stay coupled: for each
$y\in\mathcal{X}_{1}^{\prime}\backslash[x]$, jump to $(y,\Psi(y),1)$ with rate

$r_{1}(x,y)\cdot\frac{r_{1}(x,[y])\wedge
r_{2}(\Psi(x),\Psi(y))}{r_{1}(x,[y])};$

  * •

$\mathcal{A}$ jumps alone inside $[x]$, stay coupled: for each
$y\in[x]\backslash\\{x\\}$, jump to $(y,\Psi(y),1)=(y,\Psi(x),1)$ with rate
$r_{1}(x,y)$;

  * •

$\mathcal{A}$ jumps alone leaving $\mathcal{X}_{1}^{\prime}$, break coupling:
for each $y\in\mathcal{X}_{1}\backslash\mathcal{X}_{1}^{\prime}$, jump to
$(y,\Psi(x),0)$ with rate $r_{1}(x,y)$;

  * •

$\mathcal{A}$ jumps alone inside $\mathcal{X}_{1}^{\prime}$, break coupling:
for each $y\in\mathcal{X}_{1}^{\prime}\backslash[x]$, jump to $(y,\Psi(x),0)$
with rate

$r_{1}(x,y)\cdot\left(1-\frac{r_{1}(x,[y])\wedge
r_{2}(\Psi(x),\Psi(y))}{r_{1}(x,[y])}\right);$

  * •

$\mathcal{B}$ jumps alone, breaks coupling: for each $z\in\mathcal{X}_{2}$,
jump to $(x,z,0)$ with rate

$r_{2}(\Psi(x),z)-(r_{1}(x,\Psi^{-1}(z))\wedge r_{2}(\Psi(x),z)).$

It is straightforward to check that the marginal rates for $(\mathcal{A}_{t})$
and $(\mathcal{B}_{t})$ are correct, so that items (a) and (b) in the
statement of the lemma hold.

For each $x\in\mathcal{X}_{1}^{\prime}$, let $\mathcal{R}(x)$ denote the rate
at which $(\mathcal{A}_{t},\mathcal{B}_{t},\mathcal{W}_{t})$ jumps from
$(x,\Psi(x),1)$ to the set
$\mathcal{X}_{1}\times\mathcal{X}_{2}\times\\{0\\}$, where the coupling is
broken. From the above rates, and then using (60) and (61), it can be seen
that

$\mathcal{R}(x)=r_{1}(x,\mathcal{X}_{1}\backslash\mathcal{X}_{1}^{\prime})+\sum_{\begin{subarray}{c}z\in\mathcal{X}_{2},\\\
z\neq\Psi(x)\end{subarray}}|r_{1}(x,\Psi^{-1}(z))-r_{2}(\Psi(x),z)|\leqslant
2f(x).$ (63)

Next, let $\sigma^{\prime}:=\inf\\{t:\mathcal{W}_{t}=0\\}$, and recall that
$T_{a}:=\inf\\{t:f(\mathcal{A}_{t})>a\\}$. The process

$M_{t}:=\mathds{1}\\{\sigma^{\prime}\leqslant t\wedge
T_{a}\\}-\int_{0}^{t\wedge\sigma^{\prime}\wedge
T_{a}}\mathcal{R}(\mathcal{A}_{s})\;\mathrm{d}s,\qquad t\geqslant 0$

is easily seen to be a martingale. Then, for any $t\geqslant 0$,

$\displaystyle 0=M_{0}=\mathbb{E}[M_{t}]$
$\displaystyle=\mathbb{P}(\sigma^{\prime}\leqslant t\wedge
T_{a})-\mathbb{E}\left[\int_{0}^{t\wedge\sigma^{\prime}\wedge
T_{a}}\mathcal{R}(\mathcal{A}_{s})\;\mathrm{d}s\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq_bound_R}}}{{\geqslant}}\mathbb{P}(\sigma^{\prime}\leqslant
t\wedge T_{a})-2at.$

Now, recalling that
$\sigma:=\inf\\{t:\mathcal{B}_{t}\neq\Psi(\mathcal{A}_{t})\\}$, we have that
$\sigma^{\prime}\leqslant\sigma$, so

$\mathbb{P}(\sigma\leqslant t\wedge
T_{a})\leqslant\mathbb{P}(\sigma^{\prime}\leqslant t\wedge T_{a})\leqslant
2at.$

∎

In the application we have in mind for this lemma, the first Markov chain is
the pair $(\xi_{t},\mathscr{E}_{t})$ consisting of the contact process and the
exploration process in the random dynamic graph, as described in the previous
subsection (recall that this pair is a Markov chain). The second Markov chain
is a certain function of the herds process. We will need to give some
definitions for both, as well as for the mapping $\Psi$ between them.

####  4.3.1 First Markov chain: contact and exploration process

The process $(\xi_{t},\mathscr{E}_{t})_{t\geqslant 0}$ (contact process and
exploration process on the dynamic random graph $(G_{t})$) takes values in the
state space

$\mathcal{X}_{1}:=\\{(A,\mathcal{E}):\;A\subseteq[n],\;\mathcal{E}\in\mathscr{P}\\},$

where we recall the definition of $\mathscr{P}$ in (59). We denote by
$r_{1}(\cdot,\cdot)$ the function giving the jump rates of this chain.

Given $(A,\mathcal{E})\in\mathcal{X}_{1}$, we define the graph induced by
$(A,\mathcal{E})$, denoted by $\mathrm{Graph}(A,\mathcal{E})$, as follows.
First enumerate $\mathcal{E}=\\{e_{1},\ldots,e_{m}\\}$, with

$e_{1}=\\{(u_{1},a_{1}),(u_{1}^{\prime},a_{1}^{\prime})\\},\quad\ldots,\quad
e_{m}=\\{(u_{m},a_{m}),(u_{m}^{\prime},a_{m}^{\prime})\\}.$

Then, $\mathrm{Graph}(A,\mathcal{E})$ is the graph with vertex set
$A\cup\\{u_{1},u_{1}^{\prime},\ldots,u_{m},u_{m}^{\prime}\\}$ and edge set
$\mathcal{E}$.

####  4.3.2 Second Markov chain: herds process modulo automorphisms

Recall the definition of the set $P_{\mathsf{f}}(\mathbb{T}^{d})$ of herd
shapes from Definition 2.1. For $A\in P_{\mathsf{f}}(\mathbb{T}^{d})$, define

$[A]:=\left\\{\begin{array}[]{r}A^{\prime}\in
P_{\mathsf{f}}(\mathbb{T}^{d}):\;\text{there is a graph isomorphism
$\psi:\mathbb{T}^{d}\to\mathbb{T}^{d}$}\\\ \text{such that
}\psi(A)=A^{\prime}\end{array}\right\\}.$

This decomposes $P_{\mathsf{f}}(\mathbb{T}^{d})$ into equivalence classes.

Recall the definition of the set $\mathcal{S}$ of herd configurations
$\mathcal{S}$ from Definition 2.2. Given $\xi\in\mathcal{S}$, define
$[\xi]:\\{[A]:A\in P_{\mathsf{f}}(\mathbb{T}^{d})\\}\to\mathbb{N}_{0}$ by
setting

$[\xi]([A])=\sum_{A^{\prime}\in[A]}\xi(A^{\prime}).$

We then define

$\mathcal{X}_{2}:=\\{[\xi]:\xi\in\mathcal{S}\\},$

the set of herd configurations modulo automorphisms. Letting
$(\Xi_{t})_{t\geqslant 0}$ be the herds process, we note that, by Lemma 2.4,
the process $([\Xi_{t}])_{t\geqslant 0}$ is a Markov chain on
$\mathcal{X}_{2}$. We let $r_{2}(\cdot,\cdot)$ denote the function giving the
jump rates of this chain.

####  4.3.3 The mapping $\Psi$ and the error bound $f$

Now that we have defined the pairs $(\mathcal{X}_{1},r_{1})$ and
$(\mathcal{X}_{2},r_{2})$ that we will use in our application of Lemma 4.1, we
will also define the sets $\mathcal{X}_{1}^{\prime}$ and the functions
$\Psi:\mathcal{X}_{1}^{\prime}\to\mathcal{X}_{2}$ and
$f:\mathcal{X}_{1}^{\prime}\to[0,\infty)$ that appear in the assumptions of
that lemma.

We start with

$\mathcal{X}_{1}^{\prime}:=\\{(A,\mathcal{E})\in\mathcal{X}_{1}:\;\mathrm{Graph}(A,\mathcal{E})\text{
is a forest}\\}.$ (64)

The mapping $\Psi$ is easy to understand (Figure 2 provides an instant
explanation) but somewhat clumsy to define. Fix
$(A,\mathcal{E})\in\mathcal{X}_{1}^{\prime}$. Let
$\mathscr{C}_{1},\ldots,\mathscr{C}_{m}$ be the connected components of
$\mathrm{Graph}(A,\mathcal{E})$ that contain at least one vertex of $A$. For
$i\in\\{1,\ldots,m\\}$, let $A_{i}$ be the set of vertices of $A$ that
intersect $\mathscr{C}_{i}$. Since $\mathscr{C}_{i}$ is a tree in which all
vertices have degree at most $d$, there exists an isomorphism $\psi_{i}$
between $\mathscr{C}_{i}$ and some connected subgraph of $\mathbb{T}^{d}$ (in
fact there are infinitely many such isomorphisms, but we choose one in some
arbitrary way). Then,
$\xi(A,\mathcal{E}):=\sum_{i=1}^{m}\delta_{\psi_{i}(A_{i})}$ is a herd
configuration, and we let

$\Psi(A,\mathcal{E}):=[\xi]\in\mathcal{X}_{2}.$

Figure 2:  Illustration of the mapping $\Psi$. Above, the pair
$(A,\mathcal{E})$ is depicted (red vertices are those that belong to $A$, and
black vertices are those that belong to $\mathrm{Graph}(A,\mathcal{E})$ but
not to $A$). Below, the herd configuration modulo automorphisms
$\Psi(A,\mathcal{E})$ is shown. Note that one of the connected components of
$\mathrm{Graph}(A,\mathcal{E})$ has no counterpart in $\Psi(A,\mathcal{E})$,
because none of its vertices belongs to $A$.

It is now straightforward to verify that there exists a constant $C_{f}>0$
such that conditions (60) and (61) are satisfied with the choice

$f(A,\mathcal{E}):=C_{f}\frac{(|A|+|\mathcal{E}|)^{2}}{n}.$

We omit the details.

We now have all the ingredients to apply Lemma 4.1. Given an initial condition
$(A,\mathcal{E})\in\mathcal{X}_{1}^{\prime}$ for the exploration process
(which will often, but not always, be equal to $(\\{\bar{u}\\},\varnothing)$),
we can obtain the coupling $(\mathcal{A}_{t},\mathcal{B}_{t})_{t\geqslant 0}$
started from $((A,\mathcal{E}),\Psi(A,\mathcal{E}))$ and satisfying the
properties guaranteed by that lemma.

###  4.4 Proof of Theorem 1.2

For the rest of this section, we assume that
$\lambda<\bar{\lambda}(\mathsf{v})$. By (58), it suffices to prove that, for
$C>0$ large enough, we have

$n\cdot\mathbb{P}(\xi^{\bar{u}}_{C\log
n}\neq\varnothing)\xrightarrow{n\to\infty}0.$

Let us explain our strategy to prove this. We take advantage of the coupling
with the herds process from the previous section. The probability that the
contact process started from $\\{\bar{u}\\}$ survives until time $C\log n$
(with $C$ some large constant), and moreover the coupling remains good
(meaning that $\mathcal{B}_{t}=\Psi(\mathcal{A}_{t})$) for time
$C^{\prime}\log n$ (with $C^{\prime}<C$ but still large) is $o(1/n)$, since
this would imply survival of the herds process, which is subcritical, until
$C^{\prime}\log n$. However, the probability that the coupling turns bad
before extinction is not $o(1/n)$, so we have to deal with that event. The
most problematic case is that the coupling turns bad due to the exploration
process finding an edge that causes the explored graph to no longer be a
forest. In that case, apart from events of probability $o(1/n)$, this
problematic edge is deleted after a short amount of time due to a switch (with
no other problematic edges appearing in the meantime), and the explored region
goes back to being a forest. At this moment when a forest reappears, we can
start a brand new coupling between the exploration process (starting from its
current state $(\xi_{t},\mathscr{E}_{t})$) and a herds process (starting from
$\Psi(\xi_{t},\mathscr{E}_{t})$). Now, this second coupling also turning bad
has too low probability (when we consider this event together with the already
low probability of the breaking of the first attempt). It is also unlikely
that this second coupling stays active for a long time without turning bad,
for the same reason as for the first one.

The above explanation shows that the argument is naturally structured in three
stages (of course, not all of them necessarily occur): the first coupling
attempt, then the period until a problematic edge is removed, and then the
second coupling attempt. We encapsulate Stages 2 and 3 in two lemmas, in
reverse order: Lemma 4.2 below deals with Stage 3, and Lemma 4.3 with Stage 2.
Having these two lemmas in place, we are able to tell the full story from the
beginning of Stage 1, concluding the proof.

######  Lemma 4.2.

Let $(A,\mathcal{E})\in\mathcal{X}_{1}^{\prime}$, where
$\mathcal{X}_{1}^{\prime}$ is as in (64). Assume that
$|A|+|\mathcal{E}|\leqslant n^{1/{6}}$. Let
$(\xi_{t},\mathscr{E}_{t})_{t\geqslant 0}$ be a contact process and
exploration process started from $(\xi_{0},\mathscr{E}_{0})=(A,\mathcal{E})$.
Then, letting $\tau$ denote the extinction time of the contact process, and
$\varphi=\varphi(\lambda,\mathsf{v})$ be the growth index of the herds process
(as in (10)), for $n$ large enough we have

$\mathbb{P}\left(\tau>\frac{2}{|\log\varphi|}\log
n\right)\leqslant\frac{1}{\sqrt{n}}.$ (65)

###### Proof.

Let $(\mathcal{A}_{t},\mathcal{B}_{t})_{t\geqslant 0}$ be the coupling
obtained from Lemma 4.1, started from
$(\mathcal{A}_{0},\mathcal{B}_{0})=((A,\mathcal{E}),\Psi(A,\mathcal{E}))$.
Recalling from the statement of Lemma 4.1 that

$\sigma:=\inf\\{t:\mathcal{B}_{t}\neq\Psi(\mathcal{A}_{t})\\},\qquad
T_{a}:=\inf\\{t:f(\mathcal{A}_{t})\geqslant a\\}$

and abbreviating

$t_{*}:=\frac{2\log n}{|\log\varphi|},\qquad
a_{*}:=\frac{1}{4t_{*}\sqrt{n}}=\frac{|\log\varphi|}{8\sqrt{n}\log n},$

we bound the probability on the left-hand side of (65) by

$\displaystyle\mathbb{P}(\tau>t_{*},\;\sigma>t_{*})+\mathbb{P}(\sigma\leqslant
t_{*}\wedge T_{a_{*}})+\mathbb{P}(T_{a_{*}}<\sigma\leqslant t_{*}).$ (66)

By Lemma 4.1, we have

$\mathbb{P}(\sigma\leqslant t_{*}\wedge T_{a_{*}})\leqslant
2t_{*}a_{*}=\frac{1}{2\sqrt{n}}.$

By the definition of $\sigma$, on the event $\\{\tau>t_{*},\;\sigma>t_{*}\\}$
we have that $\mathcal{B}_{t_{*}}$ is not empty. Then,
$\mathbb{P}(\tau>t_{*},\;\sigma>t_{*})$ is smaller than the probability that a
herds process started with fewer than $n^{1/6}$ particles is still alive by
time $t_{*}$. By (6) and (15), we obtain

$\mathbb{P}(\tau>t_{*},\;\sigma>t_{*})\leqslant
Cn^{1/6}\cdot\varphi^{t_{*}}=Cn^{1/6}\cdot n^{-2}<\frac{1}{4\sqrt{n}}$ (67)

if $n$ is large enough.

It remains to bound $\mathbb{P}(T_{a_{*}}<\sigma\leqslant t_{*})$. Recalling
that $f(\mathcal{A}_{t})=C_{f}(|\xi_{t}|+|\mathscr{E}_{t}|)^{2}/n$, if
$T_{a_{*}}<\infty$ we have

$|\xi_{T_{a_{*}}}|+|\mathscr{E}_{T_{a_{*}}}|\geqslant(na_{*}/C_{f})^{1/2}.$

Since $|\xi_{0}|+|\mathscr{E}_{0}|\leqslant n^{1/6}$, we obtain that

$\text{on
}\\{T_{a_{*}}<\infty\\},\quad|\xi_{T_{a_{*}}}|+|\mathscr{E}_{T_{a_{*}}}|-(|\xi_{0}|+|\mathscr{E}_{0}|)\geqslant(na_{*}/C_{f})^{1/2}-n^{1/6}>n^{1/5}.$

Now, the process $(|\xi_{t}|+|\mathscr{E}_{t}|)$ only changes at times when
$(\mathcal{A}_{t})=(\xi_{t},\mathscr{E}_{t})$ changes. If $\mathcal{A}_{t}$
has a new infection appearing at time $t$, then $|\xi_{t}|+|\mathscr{E}_{t}|$
may increase by at most 2 at that time. If, on the other hand,
$\mathcal{A}_{t}$ performs a jump of any other kind, then
$|\xi_{t}|+|\mathscr{E}_{t}|$ stays the same or decreases. Hence, for any $t$,
we have

$|\xi_{t}|+|\mathscr{E}_{t}|-(|\xi_{0}|+|\mathscr{E}_{0}|)\leqslant
2|\\{s\leqslant t:\;\xi_{s}=\xi_{s-}+1\\}|.$

Putting these observations together, we see that

$\text{on }\\{T_{a_{*}}<\sigma\leqslant
t_{*}\\},\quad|\\{s<\sigma:\;\xi_{s}=\xi_{s-}+1\\}|\geqslant n^{1/5}/2.$

Moreover, before time $\sigma$, whenever a new infection appears in
$(\mathcal{A}_{t})$, a new particle is also born in $(\mathcal{B}_{t})$.
Letting $\mathcal{N}_{\infty}$ denote the number of particles ever born in
$(\mathcal{B}_{t})$ (even after time $\sigma$), we obtain the bound

$\mathbb{P}(T_{a_{*}}<\sigma\leqslant
t_{*})\leqslant\mathbb{P}(\mathcal{N}_{\infty}\geqslant
n^{1/5}/2)\leqslant\frac{\mathbb{E}[\mathcal{N}_{\infty}^{p}]}{(n^{1/5}/2)^{p}},$

for any $p\geqslant 1$, by Markov’s inequality. Recalling that
$\mathcal{B}_{0}$ has at most $n^{1/6}$ particles, and using Lemma 3.12 and
Corollary 3.13, the right-hand side is smaller than

$\frac{C_{p}(n^{1/6})^{p}}{(n^{1/5}/2)^{p}}=C_{p}^{\prime}\cdot n^{-p/30},$

for some constants $C_{p},C_{p}^{\prime}>0$. Taking $p>15$ and then $n$ large
enough, this is smaller than $\frac{1}{4\sqrt{n}}$, completing the proof. ∎

######  Lemma 4.3.

There exist $\varepsilon>0$ and $\delta>0$ such that the following holds. Let
$(A,\mathcal{E})\in\mathcal{X}_{1}\backslash\mathcal{X}_{1}^{\prime}$ (so that
$\mathrm{Graph}(A,\mathcal{E})$ is not a forest). Assume that
$|A|+|\mathcal{E}|\leqslant n^{\varepsilon}$. Also assume that there is an
edge $e$ in $\mathcal{E}$ such that
$(A,\mathcal{E}\backslash\\{e\\})\in\mathcal{X}_{1}^{\prime}$, that is,
$\mathrm{Graph}(A,\mathcal{E})$ would become a forest if $e$ were removed from
$\mathcal{E}$. Letting $(\xi_{t},\mathscr{E}_{t})_{t\geqslant 0}$ denote the
contact and exploration process started from $(A,\mathcal{E})$, and letting
$\tau$ denote the extinction time of $(\xi_{t})$, for $n$ large enough we have

$\mathbb{P}\left(\tau>\left(\delta+\frac{2}{|\log\varphi|}\right)\log
n\right)<n^{-4\varepsilon}.$ (68)

###### Proof.

Let $U$ denote the time when the edge $e$ disappears, due to being involved in
a switch. The rate at which this happens equals
$\upupsilon_{n}=\frac{\mathsf{v}}{nd}$ times the number of other edges in the
graph, which is $\frac{nd}{2}-1$, times 2 (switches can be positive or
negative). So this rate is $\mathsf{v}(1-\frac{\mathsf{1}}{2nd})$. Hence, $U$
has exponential distribution with parameter
$\mathsf{v}(1-\frac{\mathsf{1}}{2nd})$.

Denote by $B$ the event that:

  * •

for all $t\in[0,U)$ we have
$(\xi_{t},\mathscr{E}_{t}\backslash\\{e\\})\in\mathcal{X}_{1}^{\prime}$, that
is, it stays the case that the removal of $e$ from the set of edges turns
$\mathrm{Graph}(\xi_{t},\mathscr{E}_{t})$ into a forest;

  * •

$\mathrm{Graph}(\xi_{U},\mathscr{E}_{U})$ is a forest.

We fix $\delta>0$ and $\varepsilon>0$ for now; their values will be chosen at
the end of the proof. We define

$T:=\inf\\{t:\;|\xi_{t}|+|\mathscr{E}_{t}|>n^{1/6}\\}.$

We bound the probability in (68) by

$\displaystyle\mathbb{P}(U>\delta\log n)$ (69)
$\displaystyle+\mathbb{P}\left(U\leqslant\delta\log n,\;T\leqslant U\right)$
(70) $\displaystyle+\mathbb{P}\left(\left\\{U\leqslant\delta\log
n,\;T>U\right\\}\cap B^{c}\right)$ (71)
$\displaystyle+\mathbb{P}\left(\left\\{U\leqslant\delta\log
n,\;T>U\right\\}\cap
B\cap\left\\{\tau>\left(\delta+\frac{2}{|\log\varphi|}\right)\log
n\right\\}\right).$ (72)

We bound these four terms separately, starting with the first and last, which
are the easiest. We have

$\mathbb{P}(U>\delta\log
n)=\exp\left\\{-\mathsf{v}\left(1-\frac{1}{2nd}\right)\delta\log
n\right\\}=n^{-\mathsf{v}\left(1-\frac{1}{2nd}\right)\delta}.$

Next, letting $B^{\prime}:=\left\\{U\leqslant\delta\log n,\;T>U\right\\}\cap
B$, and letting $(\mathcal{F}_{t})_{t\geqslant 0}$ be the natural filtration
of $(\xi_{t},\mathscr{E}_{t})$, the probability in (72) is

$\displaystyle\mathbb{P}\left(B^{\prime}\cap\left\\{\tau>\left(\delta+\frac{2}{|\log\varphi|}\right)\log
n\right\\}\right)$
$\displaystyle=\mathbb{E}\left[\mathds{1}_{B^{\prime}}\cdot\mathbb{E}\left[\left.\tau>\left(\delta+\frac{2}{|\log\varphi|}\right)\log
n\;\right|\mathcal{F}_{U}\right]\right]\leqslant\mathbb{P}(B^{\prime})\cdot\frac{1}{\sqrt{n}}\leqslant\frac{1}{\sqrt{n}},$

where the first inequality follows from Lemma 4.2.

To bound (70), we note that $|\xi_{t}|+|\mathscr{E}_{t}|$ can increase by at
most two units at a given jump time, and a jump that causes such an increase
happens with rate at most $\lambda d|\xi_{t}|$. We can thus stochastically
dominate $(|\xi_{t}|+|\mathscr{E}_{t}|)_{t\geqslant 0}$ by a pure-birth
process $(Z_{t})_{t\geqslant 0}$ on $\mathbb{N}$ which starts from
$Z_{0}=\lceil n^{\varepsilon}\rceil$ and jumps from $k$ to $k+2$ with rate
$\lambda dk$ (and has no other kind of jump). Then, the probability in (70) is
smaller than

$\begin{split}&\mathbb{P}\left(\max_{0\leqslant t\leqslant\delta\log
n}(|\xi_{t}|+|\mathscr{E}_{t}|)>n^{1/6}\right)\\\
&\leqslant\mathbb{P}(Z_{\delta\log
n}>n^{1/6})\leqslant\frac{\mathbb{E}[Z_{\delta\log n}]}{n^{1/6}}=\frac{\lceil
n^{\varepsilon}\rceil\cdot\exp\\{2\lambda d\delta\log n\\}}{n^{1/6}}\leqslant
2n^{\varepsilon+2\lambda d\delta-\frac{1}{6}}.\end{split}$

We now turn to (71). For the process $(\xi_{t},\mathscr{E}_{t})_{t\geqslant
0}$, let us say that a “bad jump” is a jump time when either (a) a contact
process transmission occurs which causes the inclusion in the exploration
process of an edge between two vertices that were already present in
$\mathrm{Graph}(\xi_{t},\mathscr{E}_{t})$, or (b) a switch involving two edges
that were already in $\mathscr{E}_{t}$. The point is that, as long as there
are no bad jumps, it remains true that
$\mathrm{Graph}(\xi_{t},\mathscr{E}_{t})$ would become a forest if $e$ were
removed. In particular, letting $S$ denote the time at which the first bad
jump occurs, we have

$\mathbb{P}(\\{U\leqslant\delta\log n,\;T>U\\}\cap
B^{c})\leqslant\mathbb{P}(U\leqslant\delta\log n,\;T>U,\;S\leqslant U).$

Now let $\mathcal{R}_{t}$ denote the rate at which a bad jump occurs from the
present state $(\xi_{t},\mathscr{E}_{t})$. It is straightforward to check that
there is $C>0$ such that $\mathcal{R}_{t}\leqslant
C\frac{(|\xi_{t}|+|\mathscr{E}_{t}|)^{2}}{n}$, and that the process

$Y_{t}:=\mathds{1}\\{S\leqslant t,\;S\leqslant T\\}-\int_{0}^{t\wedge S\wedge
T}\mathcal{R}_{s}\;\mathrm{d}s,\quad t\geqslant 0$

is a martingale. Then,

$0=\mathbb{E}[Y_{0}]=\mathbb{E}[Y_{\delta\log
n}]\geqslant\mathbb{P}(S\leqslant\delta\log n,\;S\leqslant T)-\delta\log
n\cdot C\frac{(n^{1/6})^{2}}{n}.$

Then, we have