# Balanced two-type annihilation: mean-field asymptotics

John Haslegrave Department of Mathematics and Statistics, Lancaster
University, UK. Supported by ERC Advanced Grant 883810. Peter Keevash
Mathematical Institute, University of Oxford, UK. Supported by ERC Advanced
Grant 883810.

###### Abstract

We consider an interacting particle system where equal-sized populations of
two types of particles move by random walk steps on a graph, the two types may
have different speeds, and meetings of opposite-type particles result in
annihilation. The key quantity of interest is the expected extinction time.
Even for the mean-field setting of complete graphs, the correct order of
magnitude was not previously known. Under essentially optimal assumptions on
the starting configuration, we determine not only the order of magnitude but
also the asymptotics: the expected extinction time on $K_{2n}$ is
$(2+o(1))n\log n$, independently of the relative speeds of the two types.

##  1 Introduction

Interacting particle systems have been intensively studied since the 1970s to
model a variety of phenomena in Statistical Physics and Mathematical Biology,
such as spin systems, chemical reactions, population dynamics and the spread
of infections. An important example is the two-type annihilation model for
chemical reactions, studied classically on integer lattices $\mathbb{Z}^{d}$,
where a celebrated series of papers by Bramson and Lebowitz [3, 4, 5] gives
order of magnitude estimates for the site occupancy probability. In this
model, there are two types of particles and interactions only occur between
two particles of different type, which makes the analysis particularly
difficult. A single type model introduced by Erdős and Ney [8] is easier to
analyse, although even here it was an open problem whether the origin would be
occupied infinitely often, solved in one dimension by Lootgieter [15] and in
higher dimensions by Arratia [1, 2]. Besides these diffusive models, ballistic
annihilation models have also been studied in the physics literature since the
1990s [7, 14], and more recently analysed rigorously in the mathematics
literature [13].

Considering the real-world motivations for interacting particle systems, it is
natural to consider systems on finite graphs and ask for the asymptotics of
key parameters when the number $n$ of vertices is large. Most previous
research on interacting particle systems on graphs (e.g. [9]) concerns
coalescing random walks, motivated by their connection with the voter model,
considered on general graphs by Donnelly and Welsh in the 1980s [11].
Coalescence is simpler to analyse than annihilation due to methods based on
duality and monotonicity. A more general framework, with a variety of models
including annihilation, was analysed by Cooper, Frieze and Radzik [10],
assuming that (a) the initial populations are polynomially small and randomly
distributed, (b) the underlying geometry is a random regular graph, and (c)
the types move simultaneously with equal speeds. By contrast, we will consider
an annihilation model with individual rather than simultaneous movements
starting from an arbitrary spanning configuration, so we cannot avoid
considering the so-called ‘big bang regime’ in which there is rapid action at
the beginning of the process that is harder to analyse.

We refer to our companion paper [12] for a more detailed study of particle
systems on expanders, with more history and new results for a variety of
models, including the balanced two-type annihilation to be considered here;
our main result here will be a more precise asymptotic result in the mean-
field setting. Our precise formulation of the model is taken from a recent
paper by Cristali, Jiang, Junge, Kassem, Sivakoff and York [6]. Fix a graph
with $2n$ vertices, and initialise with one particle at each vertex, with $n$
particles being blue and $n$ red. The particles represent molecules of two
reactants; when a red and a blue particle occupy the same vertex, they react
and are removed from the system, i.e. they mutually annihilate. At each time
step, with probability $p$ a red particle is chosen, uniformly at random from
the remaining red particles, or otherwise a uniformly random blue particle is
chosen. Without loss of generality, we assume $p\leq 1/2$. The chosen particle
performs a simple random walk step. If it reaches a vertex with one or more
particles of the opposite colour, it mutually annihilates with one such
particle. This process almost surely eventually terminates with no particles
remaining.

The key quantity of interest is the time taken for this to happen, which we
call the _extinction time_.

The above model was considered by Cristali et al. [6] for the complete graphs
(the mean-field case) and stars. For these graphs, the one-type annihilation
model is easy to analyse, but the two-type process is much harder, owing to
the possibility of multiple particles of the same type occupying a single
site. While they were able to give precise results on the extinction time for
stars, for the mean-field case, also assuming that $p$ is bounded away from
zero uniformly in the $n$, they gave a lower bound of $2n\log n$ and an upper
bound of $20n\log^{2}n/\log\log n$, thus leaving the open problem of showing
that it is $\Theta(n\log n)$. In [12] we solved this problem for any $p$ on
all regular graphs with sufficiently strong spectral expansion. Here we use
different methods to give the following more precise result in the mean-field
setting.

######  Theorem 1.

Consider an initial possibly random configuration on $K_{2n}$ having $n$
particles of each type, with each site having at most one type of particle,
where $n-A$ sites are initially occupied by red particles. Let $T$ be the
extinction time. If $\mathbb{E}(A)=o(pn\log n)$ then
$\mathbb{E}(T)=(2+o(1))n\log n$.

Note that if $p=\omega(1/\log n)$, i.e. the reds are not that slow, then
Theorem 1 applies to any starting configuration. The assumption on $A$ cannot
be significantly relaxed, as the result is not true for all starting
configurations when $p$ is of order $1/\log n$. To see this, notice that if
all reds start on the same vertex $v$ then extinction requires at least $n$
occasions where either a red moves or a blue moves onto $v$. The number of
these events in time $3n\log n$ is with high probability at most $3pn\log
n+O(\log n)$, so if $p=1/(4\log n)$ then extinction will not occur.

The idea of the proof is to control the distribution of the particles by
martingale arguments, categorising it as good, intermediate or bad for each
colour separately. If both distributions remain good or intermediate until
very few particles remain, this will imply sufficiently good bounds on
collision probabilities to give the desired result. We show that it is
unlikely that random walk steps alone can cause a colour to cross the
intermediate regime until late in the process. For blue particles, this also
applies when we take collisions into account, since they occur less frequently
than blue walk steps, but for rarely-moving red particles it is possible that
collisions have a dominant effect. We thus bound both the time taken for the
red distribution to recover from the effects of each collision, and the total
number of collisions that occur while the red distribution is bad. This part
of the proof could be avoided if we assumed bounded speed ratios as in [6],
but this would be an unnecessary and moreover a strange assumption, as the
limiting case when one colour is stationary seems intuitively easier! The
potential difficulty that must be avoided when $p$ is small but nonzero is
that the process may be slow to recover from a situation where due to blue
collisions the red particles have somehow become clustered on a few vertices.

##  2 Proof

Consider an initial possibly random configuration on $K_{2n}$ having $n$
particles of each type, with each site having at most one type of particle,
where $n-A$ sites are initially occupied by red particles. For simplicity we
will add a loop at every vertex, so that each random walk step is equally
likely to go to any vertex, including the current vertex. This produces a
modified process that is just a time change by a factor $1+O(1/n)$, so this
makes no difference to our result. We also assume throughout that $n$ is
sufficiently large.

At time $t$, we write $M_{t}$ for the number of particles of each colour,
$R_{t}$ for the number of sites with red particles, and $B_{t}$ for the number
of sites with blue particles. We will show that with high probability $R_{t}$
and $B_{t}$ remain close to $M_{t}$ until almost all particles have been
destroyed, except for short excursions. To quantify the closeness, we
introduce a function $f(m)=\max(6m/n,1/w(n))$, where $w(n)=\omega(1)$,
$w(n)^{2}=o(\log n)$ and $\mathbb{E}(A)w(n)^{2}=o(pn\log n)$, noting that such
a function $w$ exists by our assumption on $\mathbb{E}(A)$. We say that blue
is _good_ if $B_{t}(1+f(M_{t}))\geq M_{t}$, _bad_ if
$B_{t}(1+2f(M_{t}))<M_{t}$, or _intermediate_ otherwise, and likewise for red
with respect to $R_{t}$.

We will show that blue quickly becomes good, and thereafter is unlikely to
become bad within the timeframe of interest. On the other hand, the slower red
particles are harder to control due to fluctuations in their distribution
caused by annihilations with the faster blue particles. To analyse the red
distribution, we introduce the red ‘level’, defined as follows. Whenever red
becomes good the level is immediately set to $0$. Whenever a collision occurs
at some level $i$ and time $t_{i}$ such that red is not good and $R_{t}$
decreases after the collision then we increase to level $i+1$, marking the
previous value of $R_{t}$ as the _threshold_ for returning to level $i$. If
$R_{t^{\prime}}$ reaches this threshold at some later time $t^{\prime}$ then
we return to level $i$. If the initial configuration of red is good then the
starting level is $0$. If the initial configuration of red is not good, then
we start at level $n-R_{0}$ and for each $i$ let $n-i$ be the threshold for
level $i$. As $\frac{t}{1+f(t)}$ is increasing in $t$, this ensures that red
is good whenever the level returns to $0$.

We define a stopping time $\tau$ as the first time that one of the following
occurs:

  1. (i)

$M_{t}=\lfloor\log^{2}n\rfloor$,

  2. (ii)

the blue distribution becomes bad after the first time it is good,

  3. (iii)

the red distribution becomes bad while at level $0$,

  4. (iv)

$t=3n^{2}$.

At time $\tau$, the ‘success’ event is that (i) holds, i.e.
$M_{\tau}=\lfloor\log^{2}n\rfloor$, and the ‘failure’ event, denoted $F$, is
that (ii), (iii) or (iv) holds.

Our estimate for the extinction time $T$ will be $T\leq
T_{\operatorname{blue}}+T_{\operatorname{red}}+T_{\operatorname{late}}+T_{\operatorname{ok}}$,
where

  * •

$T_{\operatorname{blue}}$ is the number of steps before blue first becomes
good,

  * •

$T_{\operatorname{red}}$ is the number of steps when red is above level $0$,

  * •

$T_{\operatorname{late}}$ is the number of steps after $\tau$ with red at
level $0$, and

  * •

$T_{\operatorname{ok}}$ is the number of steps before $\tau$ where neither
colour is bad.

To see that this estimate is valid, consider any time $t$ counted by
$T-(T_{\operatorname{blue}}+T_{\operatorname{red}}+T_{\operatorname{late}})$.
Then $t$ is after blue first became good, red is at level $0$, and $t<\tau$.
Then blue cannot be bad, as this would trigger condition (ii) of $\tau$, and
red cannot be bad, as this would trigger condition (iii) of $\tau$, so $t$ is
counted by $T_{\operatorname{ok}}$.

We start our analysis with the following simple tail bound on the runtime of
the process.

######  Lemma 2.

From any starting position with $m\leq n$ particles of each type,
$\mathbb{E}(T)\leq 2mn$ and $\mathbb{P}(T>3n^{2})\leq e^{-\Theta(n)}$.

###### Proof.

At each step, conditional on the previous evolution, an annihilation occurs
with probability at least $\frac{1}{2n}$, so the expected time between
consecutive collisions is at most $2n$. Summing gives the bound for
$\mathbb{E}(T)$. The probability of needing more than $3n^{2}$ steps for
$m\leq n$ annihilations is at most
$\mathbb{P}(\operatorname{Bin}(3n^{2},\frac{1}{2n})<n)$, so the probability
bound holds by Chernoff. ∎

Next we consider the main term in the estimate for $T$.

######  Lemma 3.

We have $\mathbb{E}(T_{\operatorname{ok}})\leq 2n\log n+100w(n)^{-1}n\log n$.

###### Proof.

Each step when neither colour is bad results in a collision with probability
at least

$\frac{p{R_{t}}+(1-p){B_{t}}}{2n}\geq\frac{M_{t}}{2n(1+2f(M_{t}))}.$

Thus we bound the expected number of steps with neither colour bad before the
next collision by $26n/M_{t}$ while $M_{t}\geq n/w(n)$ (so $f(M_{t})\leq 6$)
or by $(1+2/w(n))2n/M_{t}$ while $M_{t}\leq n/w(n)$ (so $f(M_{t})=1/w(n)$).
Summing and using $\sum_{m=k}^{n}1/m\leq 1+\log n-\log k$ for all $n>k\geq 1$,

$\displaystyle\mathbb{E}(T_{\operatorname{ok}})$
$\displaystyle\leq(1+2/w(n))\sum_{m=1}^{n}2n/m+\sum_{m=n/w(n)}^{n}24n/m$
$\displaystyle\leq 2n\log n+100w(n)^{-1}n\log n,$

since $w(n)\leq\sqrt{\log n}$ and $n$ is sufficiently large. ∎

The evolution of $B_{t}$ may be bounded as follows, writing $q:=1-p$. We have

$\mathbb{P}(B_{t+1}=B_{t}+1)\geq
q\frac{M_{t}-B_{t}}{M_{t}}\cdot\frac{2n-B_{t}-R_{t}}{2n},$

since this occurs when a blue particle at a site occupied by at least one
other blue particle, of which there are at least $M_{t}-B_{t}$, moves to an
empty site. Similarly, we have

$\mathbb{P}(B_{t+1}=B_{t}-1)\leq
q\frac{B_{t}}{M_{t}}\cdot\frac{B_{t}+R_{t}}{2n}+p\frac{B_{t}}{2n},$

since for this to happen either the only blue particle at some site must move
to a non-empty site, or a red particle must move to a site occupied by exactly
one blue particle. In all other cases, $B_{t+1}=B_{t}$.

When tracking $R_{t}$, we update in two stages, firstly, moving the chosen
particle and updating $R_{t}$ to $R^{*}_{t+1}$, secondly, resolving any
collision and updating $R^{*}_{t+1}$ to $R_{t+1}$. We do so to distinguish
changes in $R_{t}$ owing to movement from changes owing to collisions, as the
latter may be dominant if blue is much faster than red. Not including the
effect of collisions, the corresponding transitions are

$\mathbb{P}(R^{*}_{t+1}=R_{t}+1)\geq
p\frac{M_{t}-R_{t}}{M_{t}}\cdot\frac{2n-R_{t}}{2n}$

and

$\mathbb{P}(R^{*}_{t+1}=R_{t}-1)\leq
p\frac{R_{t}}{M_{t}}\cdot\frac{R_{t}-1}{2n}.$

We will see that when a colour is not good then the bias in the walks
described above give a strong self-correcting effect. To describe this, we
need the following simple facts about biased random walks.

######  Lemma 4.

Let $0<\alpha\leq 2/3$ and $X_{t}$ be a random walk on $\mathbb{Z}$ such for
all $t$ we have

  * •

$X_{t+1}\in\\{X_{t}-1,X_{t},X_{t}+1\\}$;

  * •

$\mathbb{P}(X_{t+1}=X_{t}+1\mid X_{\leq t})\geq\alpha$; and

  * •

$\mathbb{P}(X_{t+1}=X_{t}-1\mid X_{\leq t})\leq\mathbb{P}(X_{t+1}=X_{t}+1\mid
X_{\leq t})/2$.

Then, given $X_{0}=k-1$, the probability of reaching $0$ before $k$ is at most
$2^{1-k}$, and the expected time to reach $k$ is at most $2\alpha^{-1}$.

###### Proof.

We first couple to a random walk $Y_{t}\leq X_{t}$ where the third condition
holds with equality. We may do this by decreasing the probability of an
increment, if necessary, until it is at most $2/3$, and then increasing the
probability of a decrement.

For the first statement, note that $2^{k-Y_{t}}$ is a martingale, and the
first time $T$ for which $Y_{t}\in\\{0,k\\}$ is a stopping time. It is easy to
verify that $\mathbb{E}(T)<\infty$ and hence by the Optional Stopping Theorem
we have $\mathbb{E}(2^{k-Y_{T}})=\mathbb{E}(2^{k-Y_{0}})=2$, so
$\mathbb{P}(Y_{T}=k)+2^{k}\mathbb{P}(Y_{T}=0)=2$, giving
$\mathbb{P}(Y_{T}=0)=2^{1-k}-2^{-k}\mathbb{P}(Y_{T}=0)<2^{1-k}$.

For the second statement, let $Z<\infty$ be the expected number of times the
value of $Y_{t}$ changes before reaching $k$. Conditioning on the first
change, we have $Z=1+2Z/3$, so $Z=3$. Since the expected time between changes
is at most $(3\alpha/2)^{-1}$, the expected time taken for $Z$ changes to
occur is at most $2\alpha^{-1}$. ∎

We next establish the necessary bias in our walks.

######  Lemma 5.

Provided that the blue distribution is not good, we have

$\frac{\mathbb{P}(B_{t+1}=B_{t}+1)}{\mathbb{P}(B_{t+1}=B_{t}-1)}\geq 2,$

and similarly, provided that the red distribution is not good, we have

$\frac{\mathbb{P}(R^{*}_{t+1}=R_{t}+1)}{\mathbb{P}(R^{*}_{t+1}=R_{t}-1)}\geq
2.$

###### Proof.

We prove the blue statement; the proof of the red statement only differs in
having more room to spare, since our bounds on the transition probabilities do
not include the term for opposite-colour collisions. Since $R_{t}\leq M_{t}$
and $p\leq q$, we have

$\mathbb{P}(B_{t+1}=B_{t}+1)\geq
q\frac{M_{t}-B_{t}}{M_{t}}\cdot\frac{2n-B_{t}-M_{t}}{2n}$

and

$\mathbb{P}(B_{t+1}=B_{t}-1)\leq
q\frac{B_{t}}{M_{t}}\cdot\frac{B_{t}+M_{t}}{2n}+p\frac{B_{t}}{2n}\leq
q\frac{B_{t}}{M_{t}}\cdot\frac{B_{t}+2M_{t}}{2n},$

and so it is sufficient to verify that

$(M_{t}-B_{t})(2n-B_{t}-M_{t})\geq 2B_{t}(B_{t}+2M_{t}),$

or equivalently that

$2n(M_{t}-B_{t})\geq M_{t}^{2}+4M_{t}B_{t}+B_{t}^{2}.$ (1)

First suppose $M_{t}\geq 7B_{t}$. Then, since $n\geq M_{t}$, the LHS of (1) is
at least $\frac{12}{7}M_{t}^{2}$ and the RHS is at most
$\frac{78}{49}M_{t}^{2}$, so (1) holds. Now suppose $7B_{t}\geq M_{t}$. As
blue is not good, we have $M_{t}\geq(1+6M_{t}/n)B_{t}$. Then the LHS of (1) is
at least $12M_{t}B_{t}$ and the RHS is at most $11M_{t}B_{t}$, so again (1)
holds. ∎

We deduce a suitable bound on the number of steps before blue first becomes
good.

######  Lemma 6.

We have $\mathbb{E}(T_{\operatorname{blue}})\leq 6n/7$.

###### Proof.

While blue is not good, Lemma 5 ensures we can couple $B_{t}$ to a random walk
satisfying the properties of Lemma 4, with $\alpha=2p/3\geq 1/3$. Since the
blue state is good whenever $B_{t}\geq n/7$, we may bound
$T_{\operatorname{blue}}$ by the time for this walk to reach $n/7$ starting
from $1$. By Lemma 4, this is at most $2\alpha^{-1}n/7$ in expectation, as
required. ∎

Next we bound the probability of the failure event $F$.

######  Lemma 7.

We have $\mathbb{P}(F)\leq 3n^{-3}$.

###### Proof.

We first deal with failure events for blue. We say that the genesis of such an
event is the last time $t^{*}$ prior to $B_{t}$ becoming bad that $B_{t}$
stopped being good, i.e. $B_{t^{*}-1}(1+f(M_{t^{*}-1})\geq M_{t^{*}-1}$ but
$B_{t^{*}}(1+f(M_{t^{*}}))<M_{t^{*}}$. As $\frac{M_{t}}{1+f(M_{t})}$ is non-
increasing, when this occurs $B_{t^{*}}$ has just decreased by $1$ and we have
$B_{t^{*}}\geq\genfrac{\lceil}{\rceil}{}{}{M_{t^{*}}}{1+f(M_{t^{*}})}-1$.
Also, for the same reason, a bad event with genesis $t^{*}$ requires $B_{t}$
to reach $\genfrac{\lfloor}{\rfloor}{}{}{M_{t^{*}}}{1+2f(M_{t^{*}})}$ before
$\genfrac{\lceil}{\rceil}{}{}{M_{t^{*}}}{1+f(M_{t^{*}})}$. Note that
$\frac{f}{(1+f)(1+2f)}$ is increasing for $0\leq f\leq 2^{-1/2}$ and
decreasing for $f\geq 2^{-1/2}$. Also, we have $1/w(n)\leq f(M_{t})\leq 6$ and
$M_{t^{*}}\geq\log^{2}n$. Consequently, we have

$\displaystyle\genfrac{\lceil}{\rceil}{}{}{M_{t^{*}}}{1+f(M_{t^{*}})}-\genfrac{\lfloor}{\rfloor}{}{}{M_{t^{*}}}{1+2f(M_{t^{*}})}$
$\displaystyle\geq\frac{M_{t^{*}}f(M_{t^{*}})}{(1+f(M_{t^{*}}))(1+2f(M_{t^{*}}))}$
$\displaystyle\geq\min(M_{t^{*}}/(4w(n)),6M_{t^{*}}/91)\geq 10\log n.$

Thus, by Lemmas 5 and 4, a blue failure with genesis $t^{*}$ has probability
at most $2^{-10\log n}\leq n^{-6}$. By a union bound over all $t^{*}<3n^{2}$,
the probability of a bad event for blue is at most $n^{-3}$.

The analysis of red failure events is similar, considering the evolution of
$R_{t}=R^{*}_{t}$ after deleting excursions above level $0$, which do not have
any effect on red failure events (their steps are not counted in the
definition, and such an excursion returns $R_{t}$ to its original value).

Finally, the probability of failure due to taking too many steps is bounded by
$\mathbb{P}(T\geq 3n^{2})\leq n^{-3}$ by Lemma 2. ∎

Next we control the time spent with red not at level zero.

######  Lemma 8.

We have $\mathbb{E}(T_{\operatorname{red}})\leq
6nw(n)^{2}+3p^{-1}\mathbb{E}(A)w(n)^{2}$.

###### Proof.

We break the calculation into the following two claims, where the first bounds
the contribution from each increase in level, and the second the expected
number of increases in level.

######  Claim 9.

Suppose red moved up to level $i>0$ at time $t^{*}$. Then the expected number
of steps taken at level exactly $i$ before next returning to a lower level is
at most $2p^{-1}(1+w(n))$, independently of the evolution before $t^{*}$.

###### Proof.

We consider the sequence $R_{t}$ for $t\geq t^{*}$ until returning to a lower
level, removing any excursions above level $i$ (each of which returns $R_{t}$
to the value before the excursion). Removing the excursions ensures
$R_{t}=R^{*}_{t}$ throughout. At each step, as red is not good the probability
of $R_{t}$ increasing is at least

$p\frac{M_{t}-R_{t}}{M_{t}}\cdot\frac{2n-R_{t}}{2n}\geq
p\frac{f(M_{t})}{1+f(M_{t})}\geq p\frac{1}{1+w(n)}.$

Thus the expected time to exceed its initial value is at most
$2p^{-1}(1+w(n))$. ∎

######  Claim 10.

The expected number of increases in level is at most
$(2qn+\mathbb{E}(A))w(n)$.

###### Proof.

Recall that $A=n-R_{0}$. Let $L$ be the number of remaining red particles when
the level first increases. It suffices to show $\mathbb{E}(L\mid
A=a)\leq(2qn+a)w(n)$ for each $a$ such that $\mathbb{P}(A=a)>0$. This is easy
to see if red is not initially good, as then $a\geq 6n/7$ and $L=n<aw(n)$.

Now suppose red is initially good. We say that a ‘bad move’ by red is a
movement of a red particle onto another site occupied by red. We write
$\Xi_{t}$ for the number of bad moves by time $t$. As $M_{t}-R_{t}$ can only
increase via bad moves, we have $M_{t}-R_{t}\leq a+\Xi_{t}\leq a+\Xi_{T}$.
When the level increases red is not good, so $M_{t}-R_{t}\geq
R_{t}f(R_{t})\geq R_{t}/w(n)$. We deduce $L\leq(a+\Xi_{T})w(n)$.

It remains to bound $\Xi_{T}$. We note that a bad move at time $t$ has
probability at most $p\frac{R_{t}}{2n}$, whereas the probability of a
collision is at least $q\frac{R_{t}}{2n}$, since this is the probability of a
blue particle moving onto a site occupied by red particles. Thus
$pC_{t}-q\Xi_{t}$ is a submartingale, where $C_{t}$ is the number of
collisions by time $t$. At the stopping time $T$, since $C_{T}=n$, we have
$\mathbb{E}(\Xi_{T})\leq np/q\leq 2pn$, as required. ∎

Now we deduce the lemma from the following calculation combining these two
claims:

$\displaystyle\mathbb{E}(T_{\operatorname{red}})$
$\displaystyle\leq(2pn+\mathbb{E}(A))w(n)\cdot 2p^{-1}(1+w(n))$
$\displaystyle=(4n+2\mathbb{E}(A)p^{-1})(w(n)+w(n)^{2})$ $\displaystyle\leq
6nw(n)^{2}+3p^{-1}\mathbb{E}(A)w(n)^{2}.\qed$

It remains to bound the time for the end of the process once only $\log^{2}n$
particles remain.

######  Lemma 11.

We have $\mathbb{E}(T_{\operatorname{late}})\leq 26n\log\log n$.

###### Proof.

Recalling that $F$ is the failure event, we write
$\mathbb{E}(T_{\operatorname{late}})=\mathbb{P}(F)\mathbb{E}(T_{\operatorname{late}}\mid
F)+\mathbb{E}(T_{\operatorname{late}}1_{\neg F})$. By Lemmas 2 and 7, the
first term is at most $9/n$. For the second, we assume $F$ does not occur, and
note that $T_{\operatorname{late}}$ only counts steps $t$ after $\tau$ with
red at level $0$, so red must be good at such $t$. In particular, $R_{t}\geq
M_{t}/2$, so the probability of a collision is at least
$p\frac{M_{t}}{4n}\geq\frac{M_{t}}{8n}$. Thus this contribution has expected
size at most $\sum_{m=1}^{\log^{2}n}8n/m\leq 16n\log\log n+8n$. ∎

Combining the bounds from Lemmas 3, 6, 8 and 11, using
$\mathbb{E}(A)w(n)^{2}=o(pn\log n)$ gives

$\displaystyle\mathbb{E}(T)$ $\displaystyle\leq 2n\log n+100w(n)^{-1}n\log
n+6n/7+6nw(n)^{2}+3p^{-1}\mathbb{E}(A)w(n)^{2}+26n\log\log n$
$\displaystyle=(2+o(1))n\log n,\quad\text{as required to prove Theorem
\ref{thm:complete}.}$

As a variant form of Theorem 1, one can obtain an explicit estimate for the
second order term under the stronger assumption $\mathbb{E}(A)\leq pn$.
Indeed, then applying the argument with $w(n)=\log^{1/3}n$ we obtain
$\mathbb{E}(T)\leq 2n\log n+O(n\log^{2/3}n)$. This form of the second order
term seems to be an artefact of the proof; we do not think it is optimal.

##  3 Concluding remarks

In a companion paper [12] we consider a more general class of interacting
particle systems on expanders, for which we obtain similar $\Theta(n\log n)$
bounds on the equilibrium time. Our methods there are entirely different, and
while they apply in much greater generality, they only reveal the order of
magnitude, not the asymptotics. It may be interesting to extend the methods of
this paper to obtain asymptotic results for other graphs with simple
structure, such as the complete bipartite graph $K_{n,n}$. This question
conceals another, more basic question: does $K_{n,n}$ have a well-defined
asymptotic extinction time from any starting distribution, or do some initial
distributions reach extinction much faster than others?

For $K_{n,n}$ we believe that the starting distribution does not make much
difference. We give some evidence for this by sketching a proof in the case of
stationary reds. In this case the extinction time does not depend on the order
in which blue particles are chosen to move (the ‘abelian sandpile’ property,
see [12]). Thus we may consider blues in turn, moving each one until it hits a
red. Each time taken is a random variable of the following form: count the
number of independent trials required for success, where odd trials have some
success probability $p_{1}$ and even trials have some success probability
$p_{2}$. While $p_{1}$ and $p_{2}$ depend on the arrangement of remaining
reds, $p_{1}+p_{2}=m/n$ does not, where $m$ is the number of reds remaining.
Now this is $2X-Y$ where $X$ is a geometric random variable with success
probability $p_{1}+p_{2}-p_{1}p_{2}$, i.e. the probability that one of any
given pair of trials succeeds, and $Y$ is an independent Bernoulli random
variable with probability $p_{1}/(p_{1}+p_{2}-p_{1}p_{2})$. In particular,
$\mathbb{E}(2X-Y)$ is minimised when $p_{2}=0$, at $2n/m-1$. Assuming
$m<n/\log n$ we have $p_{1}p_{2}<(p_{1}+p_{2})^{2}/4<(p_{1}+p_{2})/(4\log n)$,
so $\mathbb{E}(2X-Y)\leq(2+1/\log n)m/n$, and the sum of all terms with
$m<n/\log n$ is at most $2n\log n-2n\log\log n+O(n)$. The sum of all other
terms is increased by at most a constant factor, and so has sum $O(n\log\log
n)$. Thus for stationary reds on $K_{n,n}$ we have
$\mathbb{E}(T)=(2+o(1))n\log n$ for any starting distribution.

## References

  * [1] R. Arratia,  Limiting point processes for rescalings of coalescing and annihilating random walks on $Z^{d}$.  Ann. Probab. 9:6 (1981), 909–936.
  * [2] R. Arratia,  Site recurrence for annihilating random walks on $Z^{d}$.  Ann. Probab. 11:3 (1983), 706–713.
  * [3] M. Bramson and J. L. Lebowitz,  Asymptotic behavior of densities in diffusion dominated two-particle reactions.  Phys. A 168:1 (1990), 88–94.
  * [4] M. Bramson and J. L. Lebowitz,  Spatial structure in diffusion-limited two-particle reactions.  J. Statist. Phys. 65:5–6 (1991), 941–951.
  * [5] M. Bramson and J. L. Lebowitz,  Spatial structure in low dimensions for diffusion limited two-particle reactions.  Ann. Appl. Probab. 11:1 (2001), 121–181.
  * [6] I. Cristali, Y. Jiang, M. Junge, R. Kassem, D. Sivakoff, and G. York,  Two-type annihilating systems on the complete and star graph.  Stochastic Process. Appl. 139 (2021), 321–342.
  * [7] Y. Elskens and H. L. Frisch,  Annihilation kinetics in the one-dimensional ideal gas.  Phys. Rev. A, 31 (1985), 3812–3816.
  * [8] P. Erdős and P. Ney,  Some problems on random intervals and annihilating particles,  Ann. Probab. 2:5 (1974), 828–839.
  * [9] C. Cooper, R. Elsässer, H. Ono, and T. Radzik,  Coalescing random walks and voting on connected graphs.  SIAM J. Discrete Math. 27:4 (2013), 1748–1758.
  * [10] C. Cooper, A. Frieze and T. Radzik,  Multiple random walks in random regular graphs.  SIAM J. Discrete Math. 23 (2009), 1738–1761.
  * [11] P. Donnelly and D. Welsh, (1983).  Finite particle systems and infection models.  Math. Proc. Camb. Phil. Soc. 94 (1983), 167–182.
  * [12] J. Haslegrave and P. Keevash,  Dissipative particle systems on expanders.  Manuscript, 2024.
  * [13] J. Haslegrave, V. Sidoravicius and L. Tournier,  Three-speed ballistic annihilation: phase transition and universality.  Selecta Math. (N.S.) 27:5 (2021), paper 84, 38pp.
  * [14] P. L. Krapivsky, S. Redner and F. Leyvraz,  Ballistic annihilation kinetics: The case of discrete velocity distributions.  Phys. Rev. E, 51 (1995), 3977–3987.
  * [15] J.-C. Lootgieter,  Problèmes de récurrence concernant des mouvements aléatoires de particules sur $Z$ avec destruction.  Ann. Inst. H. Poincaré Sect. B (N.S.) 13:2 (1977), 127–139.