# Limit Laws for Critical Dispersion on Complete Graphs

Umberto De Ambroggio LMU Munich, Department of Mathematics, Theresienstr. 39,
80333 Munich, Germany. Email<EMAIL_ADDRESS>Supported by ERC Grant Agreement 772606-PTRCSP. Tamás Makai11footnotemark: 1
Konstantinos Panagiotou11footnotemark: 1 Annika Steibel11footnotemark: 1

###### Abstract

We consider a synchronous process of particles moving on the vertices of a
graph $G$, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018).
Initially, $M$ particles are placed on a vertex of $G$. In subsequent time
steps, all particles that are located on a vertex inhabited by at least two
particles jump independently to a neighbour chosen uniformly at random. The
process ends at the first step when no vertex is inhabited by more than one
particle; we call this (random) time step the dispersion time.

In this work we study the case where $G$ is the complete graph on $n$ vertices
and the number of particles is $M=n/2+\alpha n^{1/2}+o(n^{1/2})$,
$\alpha\in\mathbb{R}$. This choice of $M$ corresponds to the critical window
of the process, with respect to the dispersion time. We show that the
dispersion time, if rescaled by $n^{-1/2}$, converges in $p$-th mean, as
$n\rightarrow\infty$ and for any $p\in\mathbb{R}$, to a continuous and almost
surely positive random variable $T_{\alpha}$. We find that $T_{\alpha}$ is the
absorption time of a standard logistic branching process, thoroughly
investigated by Lambert (2005), and we determine its expectation. In
particular, in the middle of the critical window we show that
$\mathbb{E}[T_{0}]=\pi^{3/2}/\sqrt{7}$, and furthermore we formulate explicit
asymptotics when $|\alpha|$ gets large that quantify the transition into and
out of the critical window. We also study the (random) _total number of jumps_
that are performed by the particles until the dispersion time is reached. In
particular, we prove that it centers around $\frac{2}{7}n\ln n$ and that it
has variations linear in $n$, whose distribution we can describe explicitly.

Mathematics Subject Classification. 05C81, 60C05, 60F05, 60H30.

##  1 Introduction

The dispersion process introduced by Cooper, McDowell, Radzik, Rivera and
Shiraga [4] consists of particles moving on the vertices of a given graph $G$.
A particle is said to be  _happy_ if there are no other particles occupying
the same vertex and  _unhappy_ otherwise. Initially, $M\geq 2$ (unhappy)
particles are placed on some vertex of $G$. Subsequently, at discrete time
steps, all unhappy particles move simultaneously and independently to a
neighbouring vertex selected uniformly at random, while the happy particles
remain in place. The process terminates at the first time step at which all
particles are happy; we call this (random) time step the _dispersion time_.

It is clear that if the number of particles is small – compared to the number
of vertices in the graph – then the dispersion time should be small as well.
Intuitively, increasing the number of particles makes it more and more
difficult for the particles to disperse quickly. This transition from ’fast’
to ’slow’ dispersion is quite well-understood and sharp when the underlying
graph is the complete graph on $n$ vertices with loops, in which case we write
$T_{n,M}$ for the dispersion time started with $M$ particles at an arbitrary
vertex (see further below for a precise definition of the model). The typical
order of $T_{n,M}$ changes rather abruptly around $M=n/2$. Indeed, if we write
$M=M(n)=(1+\varepsilon)n/2\in\mathbb{N}$ for some sequence
$\varepsilon=\varepsilon(n)\in[-1,1]$, then in [4] it was established that
$T_{n,M}$ is typically

  * •

at most logarithmic in $n$ when $\limsup_{n\to\infty}\varepsilon<0$ and

  * •

at least exponential in $n$ when $\liminf_{n\to\infty}\varepsilon>0$.

The details of this apparent and abrupt transition from logarithmic to
exponential time are obviously of great interest and were investigated further
in [5], where the authors studied the typical order and the tails of $T_{n,M}$
when $\varepsilon=o(1)$, that is, when $M=n/2+o(n)$. In this setting they
showed that for any constant $C>0$, if $\varepsilon\leq-Cn^{-1/2}$, then the
process typically finishes in
$\Theta(|\varepsilon|^{-1}\ln(\varepsilon^{2}n))$ steps, while if
$\varepsilon\geq Cn^{-1/2}$, then a much larger number
$\varepsilon^{-1}\exp(\Theta(\varepsilon^{2}n))$ of steps is required.
Moreover, within the _critical window_ corresponding to the range
$|\varepsilon|=O(n^{-1/2})$, they showed that the process typically runs for
$\Theta(n^{1/2})$ steps, making the transition into and out of the critical
window smooth, see also Figure 1.

$|\varepsilon|^{-1}\ln(\varepsilon^{2}n)$$n^{1/2}$$\varepsilon^{-1}\exp(\Theta(\varepsilon^{2}n))$$T_{n,M}$$\varepsilon$$-Cn^{-1/2}$
$0$ $Cn^{-1/2}$ Figure 1: The typical order of $T_{n,M}$ when
$M=(1+\varepsilon)n/2$ and $|\varepsilon|=o(1)$. Note that
$|\varepsilon^{-1}|\ln(\varepsilon^{2}n)$ and
$\varepsilon^{-1}\exp(\varepsilon^{2}n)$ are in $\Theta(n^{1/2})$ when
$|\varepsilon|=\Theta(n^{-1/2})$, and so the transition into and out of the
critical window is smooth.

In this paper we will perform a fine analysis of the dispersion process within
the critical window, that is, when $M=n/2+O(n^{1/2})$. Our first main result
establishes that the dispersion time, scaled by $n^{-1/2}$, converges in
distribution to some continuous and almost surely positive random variable.
For a sequence of real-valued random variables $(Z_{n})_{n\in\mathbb{N}}$ and
a random variable $Z$ we write $Z_{n}\overset{d}{\longrightarrow}Z$ to denote
that the sequence $(Z_{n})_{n\in\mathbb{N}}$ converges to $Z$ in distribution.

######  Theorem 1.1.

Let $\alpha\in\mathbb{R}$ and $M=M(n)=n/2+\alpha
n^{1/2}+o(n^{1/2})\in\mathbb{N}$. Then there is a continuous and almost surely
positive random variable $T_{\alpha}$ such that, as $n\to\infty$,

$n^{-1/2}T_{n,M}\overset{d}{\longrightarrow}T_{\alpha}\leavevmode\nobreak\ .$

Within the proof of Theorem 1.1 we derive an explicit description of the
distribution of $T_{\alpha}$, see also (48). In order to specify it at this
point we need to step back a bit and introduce some notation and present some
facts about the process. Let us write $U_{t}$ for the (random) number of
unhappy particles at the end of step $t$, so that $U_{0}=M$, and let us fix
some $\delta>0$. As we will see in Section 4, $U_{t}$ drops rather quickly to
$\Theta(n^{1/2})$ particles. In particular, with probability at least
$1-\delta$, after $t^{*}\sim\frac{4}{7}\delta n^{1/2}$ steps we have that
$U_{t^{*}}\sim n^{1/2}/\delta$; here and everywhere else ‘$\sim$’ will stand
for ‘$=(1+o(1))$’ and asymptotic statements are, unless stated explicitly
otherwise, with respect to $n\to\infty$ and uniform in all other parameters.
After $t^{*}$ steps the process $(U_{t})_{t\geq t^{*}}$ of unhappy particles
starts fluctuating significantly, see Figure 2 for outcomes of a simulation
study when $M=n/2$.

$\phantom{{}^{\prime}}0\phantom{{}^{\prime}}$$t^{\prime}$’1000’’3000’’5000’’7000’$0$$1$$2$$4$$6$$8$
$\begin{split}\mathbb{E}[T_{n,M}]&\sim\sqrt{\pi^{3}n/7}\approx
6655\end{split}$ $t$$\frac{U_{t}}{1000}$Iterated Mean Figure 2: Three sample
runs of the dispersion process with $n=10^{7}$ and $M=n/2$, where we depict
the number of unhappy particles $U_{t}$, divided by 1000, at each step $t$.
The trajectory is revealed only after $t^{\prime}=500$, where
$U_{t^{\prime}}\approx 10^{4}\approx 3n^{1/2}$ in all cases. The dotted line
represents the iterated mean of $U_{t}$, see also Lemma 4.4. For the
asymptotics of $\mathbb{E}[T_{n,M}]$ see (4).

In order to get a grip on it, we scale time and space by a factor of $n^{1/2}$
and establish that $(n^{-1/2}U_{t^{*}+\lfloor sn^{1/2}\rfloor})_{s\geq 0}$
converges weakly to a diffusion process. Here weak convergence denotes, as
usual, convergence in $D([0,T],\mathbb{R})$ for all $T<\infty$, where
$D([0,T],\mathbb{R})$ is the space of all càdlàg functions from $[0,T]$ to
$\mathbb{R}^{d}$ that we equip with the Skorokhod metric.

######  Lemma 1.2.

Let $\alpha\in\mathbb{R}$ and $M=M(n)=n/2+\alpha
n^{1/2}+o(n^{1/2})\in\mathbb{N}$. Let $\delta>0$ and

$T_{n,M,\delta}\coloneqq\inf\\{t>0:U_{t}\leq n^{1/2}/\delta\\}$

be the first step at which there are at most $n^{1/2}/\delta$ unhappy
particles. Then, as $n\to\infty$, weakly

$\Big{(}n^{-1/2}\,U_{T_{n,M,\delta}+\lfloor sn^{1/2}\rfloor}\Big{)}_{s\geq
0}\to X,$

where $X$ is a logistic branching process. In particular, if we denote by $B$
a standard Brownian motion, then $X$ uniquely satisfies the stochastic
differential equation

$dX_{s}=\left(2\alpha
X_{s}-\frac{7}{4}X_{s}^{2}\right)ds+\sqrt{X_{s}}dB_{s},\leavevmode\nobreak\
\leavevmode\nobreak\ s>0,\quad\text{ and }\quad X_{0}=\delta^{-1}.$ (1)

For more background on SDEs in general and the specific equation encountered
here we refer to Section 2. Let us mention only that stochastic processes
satisfying (1) are well-studied and are also called in the literature
_logistic Feller diffusions_ or _Feller diffusions with logistic growth_.
Generally, such processes satisfy an SDE of the form

$dX_{s}=(aX_{s}-cX_{s}^{2})ds+\sqrt{\gamma X_{s}}dB_{s},\;s>0,\text{ with
initial condition }X_{0}=x\geq 0,$ (2)

where $a\in\mathbb{R}$ and $c,\gamma>0$. They appear in the context of
population dynamics and stochastically extend the deterministic logistic
growth model that describes the evolution of a population under the influences
of natural birth, mortality and inter-individual competition. A prime source
on the topic is Lambert [13], who provides a thorough and detailed discussion
of the properties of solutions to (2).

With Lemma 1.2 at hand we readily establish in Section 5, see Lemma 5.2 there,
that the first time step at which the unhappy particles vanish, divided by
$n^{1/2}$, converges in distribution to the _absorption time_ of $X$, that is,
the first time when $X$ hits zero. Letting $\delta\to 0$ then yields the
claimed statement. In particular, $T_{\alpha}$ in Theorem 1.1 is the
absorption time of the limiting solution of (1) when the initial condition
$X_{0}\to\infty$; as we will see, this limiting process, called _standard
logistic branching process_ , is well-defined and well-studied, see [13, 9]
and Section 2.2.

The explicit descriptions of $X$ and $T_{\alpha}$ pave the way to obtain
further bits of information. To achieve this we will exploit the following
bounds, stating that $n^{-1/2}T_{n,M}$ has exponential tails, that are an
immediate consequence of the main theorems in [5].

######  Theorem 1.3.

Let $\alpha\in\mathbb{R}$ and $M=n/2+\alpha n^{1/2}+o(n^{1/2})\in\mathbb{N}$.
Then there is a constant $c_{\alpha}>0$ such that for all sufficiently large
$n$

$\mathbb{P}\big{(}T_{n,M}\leq n^{1/2}/Ac_{\alpha}\big{)}\leq
e^{-A}\quad\mbox{and}\quad\mathbb{P}\big{(}T_{n,M}>Ac_{\alpha}n^{1/2}\big{)}\leq
e^{-A},\qquad A\geq 1.$

Together with Theorem 1.1 we readily obtain convergence in ${\cal L}^{p}$, for
any $p\in\mathbb{R}$, that is,

$n^{-p/2}\mathbb{E}\big{[}T_{n,M}^{p}\big{]}\sim\mathbb{E}\big{[}T_{\alpha}^{p}\big{]},\quad
p\in\mathbb{R}.$ (3)

As we shall show in Lemma 6.1, we obtain for $M=n/2+\alpha n^{1/2}+o(n^{1/2})$
the series representation

$\mathbb{E}[T_{\alpha}]=\lim_{n\to\infty}\mathbb{E}\big{[}n^{-1/2}T_{n,M}\big{]}=\frac{\pi^{3/2}}{\sqrt{7}}+\frac{1}{\sqrt{7}}\sum_{m\geq
1}\frac{\Gamma(\frac{m+1}{2})}{m!}\left(\frac{8\alpha}{\sqrt{7}}\right)^{m}t_{m},\quad\alpha\in\mathbb{R},$

where $\Gamma(\cdot)$ is the Gamma function and

$t_{m}\coloneqq\sum_{k\geq
0}\frac{2}{(\frac{m+1}{2}+2k)(\frac{m+3}{2}+2k)}=H_{(m-1)/4}-H_{(m-3)/4},\quad
m\in\mathbb{N}_{0},$

and $H_{x}=\sum_{k\geq 1}\big{(}\frac{1}{k}-\frac{1}{k+x}\big{)}$ denotes the
‘$x$-th harmonic number’. Let us highlight the specific case $\alpha=0$: when
we are essentially  _at_ the critical point, then we obtain the beautiful
formula

$\mathbb{E}[T_{0}]=\lim_{n\to\infty}\mathbb{E}\big{[}n^{-1/2}T_{n,n/2+o(n^{1/2})}\big{]}=\frac{\pi^{3/2}}{\sqrt{7}},$
(4)

which is in the interval $2.104\pm 0.001$, see also Figure 2. Our methods also
allow us to study the behavior of the transition in and out of the critical
window, that is, $\mathbb{E}[T_{\alpha}]$ when $\alpha\to-\infty$ or
$\alpha\to\infty$. In Section 6 we show that

$\mathbb{E}[T_{\alpha}]\stackrel{{\scriptstyle\alpha\to-\infty}}{{\sim}}\frac{\ln|\alpha|}{|\alpha|}\qquad\text{and}\qquad\mathbb{E}[T_{\alpha}]\stackrel{{\scriptstyle\alpha\to\infty}}{{\sim}}\frac{\sqrt{7\pi}}{8}\frac{e^{16\alpha^{2}/7}}{\alpha^{2}}.$

So, when $\alpha$ gets big, then $\mathbb{E}[T_{\alpha}]$ behaves (up to
polynomial corrections) quadratic exponential in $\alpha$; already for
$\alpha=3$ we obtain the enormous value $\mathbb{E}[T_{3}]\approx 5.894\cdot
10^{7}$. On the other hand, for negative $\alpha$ we get a moderate polynomial
behavior with logarithmic corrections. Note that the large $|\alpha|$
asymptotics presented here are in accordance with the transition in and out of
the critical window, see also Figure 1 and the discussion at the beginning of
the introduction. To see this, note that if we set $M=n/2+\alpha
n^{1/2}+o(n^{1/2})=(1+\varepsilon)n/2$, then $\varepsilon\sim 2\alpha
n^{-1/2}$, and so

$\frac{\ln(\varepsilon^{2}n)}{|\varepsilon|}\sim
2\frac{\ln|\alpha|}{|\alpha|}n^{1/2}\quad\text{and}\quad\varepsilon^{-1}e^{\Theta(\varepsilon^{2}n)}=\frac{n^{1/2}}{2\alpha}e^{\Theta(\alpha^{2})}=\frac{e^{\Theta(\alpha^{2})}}{\alpha^{2}}n^{1/2}.$

Our second main result addresses the total number of jumps $\sum_{t\geq
0}U_{t}$ performed by the particles until the dispersion time is reached.

######  Theorem 1.4.

Let $\alpha\in\mathbb{R}$ and $M=M(n)=n/2+\alpha
n^{1/2}+o(n^{1/2})\in\mathbb{N}$. Then there is a continuous random variable
$A_{\alpha}$ such that, as $n\to\infty$,

$n^{-1}\bigg{(}\sum_{t\geq 0}U_{t}-\frac{2}{7}n\ln
n\bigg{)}\overset{d}{\longrightarrow}A_{\alpha}.$

In particular, when $\alpha=0$ there exists a $\chi\in\mathbb{R}$ such that

$\mathbb{P}(A_{0}\geq
a)=\mathrm{erf}\left(\frac{\sqrt{7}}{2}e^{-7(a-\chi)/4}\right),\quad
a\in\mathbb{R},$

where
$\mathrm{erf}(x)=\frac{2}{\sqrt{\pi}}\int_{0}^{x}e^{-y^{2}}dy,x\in\mathbb{R}$,
denotes the error function.

Regarding the definition and the actual value of $\chi$ we refer to Section
4.1, see also Remark 4.6. As a consequence of the theorem we deduce that each
of the $M\sim n/2$ particles performs on average typically $\sim\frac{4}{7}\ln
n$ jumps before everybody settles, and this is independent of $\alpha$.
However, the fluctuations in the total number of jumps are linear in $n$ and
the limiting distribution depends on $\alpha$. Towards the proof of Theorem
1.4 we show in our analysis of the early, i.e., the first $o(n^{1/2})$, steps,
which can be found in Section 4, that there are already $\sim\frac{2}{7}n\ln
n$ jumps in those steps of the process. With Lemma 1.2 and Theorem 1.1 in
mind, it is not surprising that the remaining $\Theta(n^{1/2})$ steps only
contribute an additional $O(n)$ jumps, as $n^{-1/2}U_{t}$ is typically bounded
for $t=\Theta(n^{1/2})$. We verify this intuition in the proof of Theorem 1.4
in Section 7. In particular, Theorem 1.1 and Lemma 1.2 assert that
$(n^{-1/2}U_{T_{n,M,\delta}+\lfloor sn^{1/2}\rfloor})_{s\geq 0}$ converges
weakly to a logistic branching process $X$, and so the total number of jumps
behaves like $n^{1/2}A_{\alpha,\delta}$, where
$A_{\alpha,\delta}\coloneqq\int_{0}^{\infty}X_{s}ds$, plus the additional
$\frac{2}{7}n\ln n$ jumps from the first $T_{n,M,\delta}$ steps. Some care
needs to be taken and some significant extra work needs to be done to take the
$\delta\to 0$ limit; in particular, we need a sufficiently tight control of
$U_{t}$ for $t\leq T_{n,M,\delta}$, so that the errors do add up to $o(n)$,
and this is accomplished by means of a delicate martingale argument in Section
4. All pieces are then put together in Section 7.

#### Variations on the Theme.

Our work opens up opportunities for studying a variety of models that are
related to the dispersion process or extensions of it. In a general setting,
_happiness_ can be defined as a property of individual vertices and particles.
More specifically, each vertex may have a _capacity_ , which, if exceeded,
deems all particles on that vertex as unhappy. On the other side, each
particle $p$ may have a _stress level_ , which dictates an upper bound on the
particles that share a vertex with $p$ so that $p$ is still happy. We leave it
as an open problem to study the precise behavior in a general setting, where
for example the empirical distributions of the capacities and the stress
levels fulfill appropriate convergence properties.

In a different line of research it would be challenging to provide detailed
studies of dispersion processes on graphs different than the complete graph.
We believe, for example, that our results also hold if the underlying graph is
a sufficiently dense Erdős-Rényi random graph, which is obtained by retaining
independently each edge of the complete graph on $n$ vertices with probability
$p$. In particular, if, say, $p=\omega(n^{-1/2})$, guaranteeing that the
minimum degree is much larger than $n^{1/2}$, then similar results as in
Theorem 1.1 should hold, as the process finishes after $O(n^{1/2})$ rounds if
the graph is complete. However, it might be the case that even on much sparser
graphs the behavior does not change (since, for example, in most steps just an
$O(n^{1/2})$ number of particles move). We consider it as an important and
eminent challenge to study the effect of the edge probability $p$ on the
distribution of the dispersion time.

#### Related work.

The aforementioned paper [10] studies, apart from complete graphs, the
dispersion time on several other families, like paths, trees, grids,
hypercubes and Cayley graphs. The dispersion process was also studied by
Frieze and Pegden [10], who considered the _dispersion distance_ on the
infinite line $L_{\infty}$. They showed that the dispersion distance is
$\Theta(n)$ when there are $n$ particles in the system, improving upon
previous results in [4]. A similar setup was considered by Shang [17], who
studied the dispersion distance on $L_{\infty}$ in a non-uniform dispersion
process.

Processes where particles move on the vertices of a graph have been widely
studied over the past decades; we refer to [4] for references. Concerning
processes whose scope is to disperse particles on discrete structures,
arguably the best known such model is Internal Diffusion Limited Aggregation,
see [7, 14, 3]. There, particles sequentially start (one at a time) from a
specific vertex designated as the origin. Each particle moves randomly until
it finds an unoccupied vertex; then it occupies it forever and it does not
move at subsequent steps. Another well-studied class of models are Activated
Random Walks that evolve on $\mathbb{Z}^{d}$, see [16] for an extensive
review. Roughly speaking, we place particles on $\mathbb{Z}^{d}$, and some of
them are initially active while others are asleep. The rules of the process
are then as follows. Whenever a particle is alone on a vertex, it falls asleep
with a certain rate. On the other hand, active particles jump according to
independent random choices, and whenever they encounter a particle that is
asleep, they wake it up.

In the remainder of the section we provide a formal definition of the model
that we study, then we fix some notation, and eventually we conclude with a
brief outline of the paper.

#### Model.

Let $n\in\mathbb{N}$. We denote by $M\geq 2$ the number of particles and we
write $\mathcal{U}_{t}$ and $\mathcal{H}_{t}$ for the sets of unhappy and
happy particles at step $t$, respectively. Moreover, we set
$U_{t}\coloneqq|\mathcal{U}_{t}|$ and $H_{t}\coloneqq|\mathcal{H}_{t}|$.
Initially, which is at step $t=0$, all $M$ particles are placed on one
distinguished vertex, say vertex 1, and are unhappy. Thus, writing $p_{i}$ for
the $i$-th particle, $1\leq i\leq M$, we set

$\mathcal{U}_{0}={\cal P}\coloneqq\\{p_{1},\dots,p_{M}\\},\leavevmode\nobreak\
\leavevmode\nobreak\
U_{0}=M\quad\text{and}\quad\mathcal{H}_{0}=\emptyset,\leavevmode\nobreak\
\leavevmode\nobreak\ H_{0}=0.$

For every $t\in\mathbb{N}_{0}$, the distribution of $\mathcal{H}_{t+1}$ (and
thus also of $\mathcal{U}_{t+1},U_{t+1},H_{t+1}$), given $\mathcal{U}_{t}$, is
defined as follows. Each particle in $\mathcal{U}_{t}$ moves to one of the $n$
vertices selected independently and uniformly at random and each particle in
$\mathcal{H}_{t}$ remains at its position. In particular, if we denote by
$p_{i,t}$ the position of particle $i$ at step $t\in\mathbb{N}_{0}$, then

$p_{i,0}=1,\leavevmode\nobreak\ 1\leq i\leq M,\quad\text{and, in
distribution,}\quad p_{i,t+1}=\begin{cases}p_{i,t},&\text{ if }p_{i}\in{\cal
H}_{t},\\\ G_{i,t+1},&\text{ if }p_{i}\in{\cal
U}_{t},\end{cases},\leavevmode\nobreak\ 1\leq i\leq M,t\in\mathbb{N}_{0},$

where $(G_{i,t})_{1\leq i\leq n,t\in\mathbb{N}_{0}}$ are independent and
uniform from $\\{1,\dots,n\\}$. In addition, we set for $t\in\mathbb{N}_{0}$

${\cal H}_{t+1}=\big{\\{}p_{i}\in{\cal P}:p_{i,t+1}\neq p_{j,t+1}\text{ for
all $j\in\\{1,\dots,M\\}\setminus\\{i\\}$}\big{\\}},\quad{\cal U}_{t+1}={\cal
P}\setminus{\cal H}_{t+1}.$

With this notation, the _dispersion time_ considered in Theorem 1.1 is defined
as the smallest $t$ at which there are no unhappy particles, that is,

$T_{n,M}\coloneqq\inf\big{\\{}t\in\mathbb{N}_{0}:U_{t}=0\big{\\}}.$ (5)

#### Notation.

Let $\mathbb{N}$ denote the set of positive integers and set
$\mathbb{N}_{0}=\mathbb{N}\cup\\{0\\}$. Given $k\in\mathbb{N}$, we write
$[k]\coloneqq\\{1,\dots,k\\}$. Given functions
$f:\mathbb{N}\mapsto\mathbb{R},g:\mathbb{N}\mapsto\mathbb{R}$, we write
$f=o(g)$ if $|f(n)/g(n)|\rightarrow 0$ as $n\rightarrow\infty$ and $f=O(g)$ if
there is a constant $C>0$ such that $|f(n)|\leq C|g(n)|$ for all large enough
$n$. We write $f=\Theta(g)$ if $f=O(g)$ and $g=O(f)$, whereas the notation
$f=\omega(g)$ means that $|f(n)/g(n)|\rightarrow\infty$ as
$n\rightarrow\infty$. For convenience, given functions
$f,g,h:\mathbb{R}\to\mathbb{R}$ we will write

$f(u)=g(u)\pm h(u)\Longleftrightarrow|f(u)-g(u)|\leq h(u),\quad
u\in\mathbb{R}.$

Given $a,b,c\in\mathbb{R}$, we set $a\vee b\coloneqq\max\\{a,b\\}$, $a\wedge
b\coloneqq\min\\{a,b\\}$. Moreover, for $b,c\neq 0$ we write, whenever it is
not ambiguous, $a/bc$ (instead of, say, $a/(bc)$) for $\frac{a}{bc}$ and
$ab/c$ for $\frac{ab}{c}$.

#### Outline.

The paper is structured as follows. In the next section we give some basic
background on SDEs and present the main tool, diffusion approximation, that we
use to study the process of the number of unhappy particles. Moreover, we take
a closer look at the logistic branching processes and collect the properties
that will be relevant here; our main source is the thorough study [13].
Moreover, we collect some facts about martingales that will be useful. In
order to apply the diffusion approximation framework it is necessary to study
the _drift_ (expected change) and the _variation_ (square of the expected
change) of the underlying Markov chain; this is performed in Section 3 for the
process of unhappy particles. Subsequently, in Section 4 we study the early
steps of the dispersion process and provide, by means of martingale
concentration arguments, tight bounds for $U_{t}$ for $t=o(n^{1/2})$. With
this at hand we prove Theorems 1.2 and 1.1 in Section 5. In Section 6 we study
the expectation of the absorption time and prove the explicit and asymptotic
formulae. Finally, in Section 7 we prove Theorem 1.4 about the total number of
jumps.

##  2 Probabilistic Preliminaries

In this section we collect several probabilistic facts that we will use:
diffusion approximation, properties of the logistic Feller diffusion and
martingale inequalities.

###  2.1 Diffusion Approximation

A main tool that we will use in the proof of Theorem 1.1 is the concept of
_diffusion approximation_ , which allows us to approximate a sequence
$(\mathbf{Y}^{(n)})_{n\in\mathbb{N}}$ of Markov chains with values in
$\mathbb{R}^{d}$, where ${d\in\mathbb{N}}$, by a continuous-time stochastic
process. More specifically, we examine convergence properties of
$(\mathbf{Y}^{(n)})_{n\in\mathbb{N}}$ to a process satisfying a stochastic
differential equation (SDE)

$d\mathbf{X}_{s}=b(\mathbf{X}_{s})ds+\sigma(\mathbf{X}_{s})d\mathbf{B}_{s},\quad
s>0,$ (6)

where $b:\mathbb{R}^{d}\to\mathbb{R}^{d}$ and
$\sigma:\mathbb{R}^{d}\to\mathbb{R}^{d\times d}$ are suitable functions and
$\mathbf{B}$ is a $d$-dimensional standard Brownian motion. In this section we
provide an overview of the necessary results from stochastic calculus.
Additionally, we collect some properties of the limit process that will emerge
within the proof of Theorem 1.1. In what follows we denote discrete time by
$t\in\mathbb{N}_{0}$ (so, for example,
$\mathbf{Y}^{(n)}=(\mathbf{Y}^{(n)}_{t})_{t\in\mathbb{N}_{0}}$), whereas
$s\geq 0$ represents continuous time. Moreover, for all $i,j\in[d]$, the
subscript $i$ denotes the $i$-th component of a $d$-dimensional vector and the
subscript $ij$ refers to the entry in row $i$ and column $j$ of a $d\times
d$-dimensional matrix.

Let us consider (6). A _(weak) solution to ( 6) with initial value
$\mathbf{X}_{0}=\mathbf{x}\in\mathbb{R}^{d}$_ is a triple
$(\mathbf{X},\mathbf{B},\mathscr{P})$, where
$\mathscr{P}=(\Omega,\mathcal{F},(\mathcal{F}_{s})_{s\geq 0},\mathbb{P})$ is a
filtered probability space with the filtration satisfying the usual
conditions, i.e. $(\mathcal{F}_{s})_{s\geq 0}$ is right-continuous and
complete. Further, $\mathbf{X}=(\mathbf{X}_{s})_{s\geq 0}$ and
$\mathbf{B}=(\mathbf{B}_{s})_{s\geq 0}$ are continuous stochastic processes
that are adapted to $(\mathcal{F}_{s})_{s\geq 0}$ such that

  * •

$\mathbf{B}$ is a standard $d$-dimensional Brownian motion with respect to
$(\mathcal{F}_{s})_{s\geq 0}$, i.e. $\mathbf{B}$ is a standard Brownian motion
and $\mathbf{B}_{s}-\mathbf{B}_{r}$ is independent of $\mathcal{F}_{r}$ for
any $0\leq r<s$;

  * •

$\mathbf{X}_{s}$ satisfies (6) and the initial condition, i.e.

$\mathbf{X}_{s}=\mathbf{x}+\int_{0}^{s}b(\mathbf{X}_{r})dr+\int_{0}^{s}\sigma(\mathbf{X}_{r})d\mathbf{B}_{r},\quad
s\geq 0,$

or, equivalently, if we write $\mathbf{X}_{s}=(X_{1,s},\dots,X_{d,s})$ for
$s\geq 0$, then

$X_{i,s}=x_{i}+\int_{0}^{s}b_{i}(\mathbf{X}_{r})dr+\sum_{j=1}^{d}\int_{0}^{s}\sigma_{ij}(\mathbf{X}_{r})dB_{j,r},\quad
i\in[d],\leavevmode\nobreak\ s\geq 0.$

Moreover, we say that there is _(weak) uniqueness_ if whenever
$(\mathbf{X},\mathbf{B},\mathscr{P})$ and
$(\mathbf{\tilde{X}},\mathbf{\tilde{B}},\tilde{\mathscr{P}})$ solve (6) weakly
and satisfy $\mathbf{X}_{0}=\mathbf{\tilde{X}}_{0}$, then $\mathbf{X}$ and
$\mathbf{\tilde{X}}$ have the same law.

In order to get the diffusion approximation to work, we construct a sequence
of right-continuous and continuous-time stochastic processes from the given
sequence $(\mathbf{Y}^{(n)})_{n\in\mathbb{N}}$ of discrete time Markov chains
by using constant interpolation between the time points. Then, under
appropriate conditions specified in the subsequent theorem,
$(\mathbf{Y}^{(n)})_{n\in\mathbb{N}}$ converges weakly to the solution of an
SDE. With the necessary concepts at hand we are now ready to present our main
tool, and we refer for example to [8, Ch. 8] for an extensive treatment.

######  Theorem 2.1 (Diffusion Approximation).

Let $d\in\mathbb{N}$, $\sigma:\mathbb{R}^{d}\to\mathbb{R}^{d\times d}$ and
$b:\mathbb{R}^{d}\to\mathbb{R}^{d}$ be continuous functions and assume that
for any $\mathbf{x}\in\mathbb{R}^{d}$ the SDE (6) possesses a unique solution
such that $\mathbf{X}_{0}=\mathbf{x}$. Furthermore, let
$h:\mathbb{N}\to\mathbb{R}_{+}$ be a sequence with $\lim_{n\to\infty}h(n)=0$
and for all $n\in\mathbb{N}$ let
$\mathbf{Y}^{(n)}=(\mathbf{Y}_{t}^{(n)})_{t\in\mathbb{N}_{0}}$ be a discrete-
time Markov chain with values in $S^{(n)}\subseteq\mathbb{R}^{d}$. Define, for
all $t\in\mathbb{N}_{0}$, $\mathbf{x}\in S^{(n)}$ and $i,j\in[d]$

$b_{i}^{(n)}(\mathbf{x})\coloneqq\frac{\mathbb{E}\big{[}Y_{i,t+1}^{(n)}-x_{i}\mid\mathbf{Y}_{t}^{(n)}=\mathbf{x}\big{]}}{h(n)},\quad
a_{ij}^{(n)}(\mathbf{x})\coloneqq\frac{\mathbb{E}\big{[}(Y_{i,t+1}^{(n)}-x_{i})(Y_{j,t+1}^{(n)}-x_{j})\mid\mathbf{Y}_{t}^{(n)}=\mathbf{x}\big{]}}{h(n)},$

and
$\gamma^{(n)}_{p}(\mathbf{x})\coloneqq\mathbb{E}\big{[}|\mathbf{Y}^{(n)}_{t+1}-\mathbf{x}|^{p}\mid\mathbf{Y}_{t}^{(n)}=\mathbf{x}\big{]}/h(n)$
for $p\geq 2$. Let $a\coloneqq\sigma\sigma^{T}$ and assume that for all
$R<\infty$ and $i,j\in[d]$

$\lim_{n\to\infty}\sup_{\mathbf{x}\in S^{(n)},|\mathbf{x}|\leq
R}|b_{i}^{(n)}(\mathbf{x})-b_{i}(\mathbf{x})|=0,\quad\lim_{n\to\infty}\sup_{\mathbf{x}\in
S^{(n)},|\mathbf{x}|\leq R}|a_{ij}^{(n)}(\mathbf{x})-a_{ij}(\mathbf{x})|=0,$

and

$\lim_{n\to\infty}\sup_{\mathbf{x}\in S^{(n)},|\mathbf{x}|\leq
R}\gamma^{(n)}_{p}(\mathbf{x})=0\leavevmode\nobreak\ \text{ for some
}\leavevmode\nobreak\ p\geq 2.$

Finally, assume that $\mathbf{Y}^{(n)}_{0}\to\mathbf{x}$ as $n\to\infty$. Then
$(\mathbf{Y}^{(n)}_{\lfloor s/h(n)\rfloor})_{s\geq 0}$ converges weakly to a
strong Markov process $\mathbf{X}$ that satisfies the SDE (6) with
$\mathbf{X}_{0}=\mathbf{x}$.

###  2.2 The (Standard) Logistic Branching Process

We already discussed in the introduction that the processes that will be
relevant here are the so-called logistic branching processes, given by the
solution of

$dX_{s}=(aX_{s}-cX_{s}^{2})ds+\sqrt{\gamma X_{s}}dB_{s},\;s>0,$

with $X_{0}=x\geq 0$, $a\in\mathbb{R}$ and $c,\gamma>0$, see also (2) (and (1)
for the particular case that will appear here). In the remainder of this
section we collect some key properties that will be handy. The first one is
about the existence and uniqueness of solutions, see for example [9, Cor.
2.11], [13, Sec. 3], [11, Thm. 5.1] and references therein.

######  Lemma 2.2.

For all initial states $x\geq 0$ and for all $a\in\mathbb{R}$ and
$c,\gamma>0$, there exists a unique solution
$(X_{a,c,\gamma,x},B_{a,c,\gamma,x},\mathscr{P}_{a,c,\gamma,x})$ to (2).
Moreover, $X_{a,c,\gamma,x}$ is non-negative.

In what follows it will be convenient to consider a specific choice of the
filtered probability space
$\mathscr{P}_{a,c,\gamma,x}=(\Omega^{\prime},\mathcal{F}^{\prime},(\mathcal{F}^{\prime}_{s})_{s\geq
0},\mathbb{P}^{\prime})$ (where all components depend on the parameters
$a,c,\gamma,x$) from the previous lemma that we construct as follows. Let
$C([0,\infty),\mathbb{R})$ be the space of all continuous maps
$\xi:[0,\infty)\to\mathbb{R}$ and let $X$ be the coordinate process given by
$X_{s}(\xi)=\xi(s)$ for all $s\geq 0$ and ${\xi\in C([0,\infty),\mathbb{R})}$.
Additionally, consider the $\sigma$-algebra $\mathcal{F}=\sigma\\{X_{s}\mid
s\geq 0\\}$ and equip the measurable space
$(C([0,\infty),\mathbb{R}),\mathcal{F})$ with the filtration
$(\mathcal{F}_{s})_{s\geq 0}$ given by ${\mathcal{F}_{s}=\sigma\\{X_{r}\mid
0\leq r\leq s\\}}$ for all $s\geq 0$, which we may complete and right-
continuously extend in order to fulfil the usual conditions. Since
$X_{a,c,\gamma,x}$ is a continuous process, it is possible to switch from
$\mathscr{P}_{a,c,\gamma,x}$ to the canonical probability space
$(C([0,\infty),\mathbb{R}),\mathcal{F},(\mathcal{F}_{s})_{s\geq
0},\mathbb{P}_{a,c,\gamma,x})$ via the map
${\Omega^{\prime}\ni\xi^{\prime}\mapsto X_{a,c,\gamma,x}(\xi^{\prime})\in
C([0,\infty),\mathbb{R})}$, where $\mathbb{P}_{a,c,\gamma,x}$ is the
probability measure given by
$\mathbb{P}_{a,c,\gamma,x}(A)={\mathbb{P}^{\prime}}((X_{a,c,\gamma,x})^{-1}(A))$
for all $A\in\mathcal{F}$. By this particular choice of probability measure we
obtain that the coordinate process $X$ on the space
$(C([0,\infty),\mathbb{R}),\mathcal{F},(\mathcal{F}_{s})_{s\geq
0},\mathbb{P}_{a,c,\gamma,x})$ has the same law as $X_{a,c,\gamma,x}$ under
$\mathbb{P}^{\prime}$, i.e. under $\mathbb{P}_{a,c,\gamma,x}$ the process $X$
satisfies (2). The following corollary is now an immediate consequence of
Lemma 2.2, and a similar construction was also performed in [13].

######  Corollary 2.3.

For all initial states $x\geq 0$ and for all $a\in\mathbb{R}$ and
$c,\gamma>0$, there is a unique solution
$(X,B_{a,c,\gamma,x},\mathscr{P}_{a,c,\gamma,x})$ to (2), where $X$ is the
coordinate process and thus independent of $a,c,\gamma,x$. Moreover, $X$ is
non-negative $\mathbb{P}_{a,c,\gamma,x}$-almost surely, where
$\mathbb{P}_{a,c,\gamma,x}$ denotes the probability measure of
$\mathscr{P}_{a,c,\gamma,x}$.

For the rest of this paper we will adopt the above procedure and consider
solutions to (2) only with respect to the canonical probability space
$(C([0,\infty),\mathbb{R}),\mathcal{F},(\mathcal{F}_{s})_{s\geq
0},\mathbb{P}_{a,c,\gamma,x})$. Our first main object of interest in Theorem
1.1 is the time at which the logistic branching process $X$ hits zero. To this
end, define

$T(\xi)\coloneqq\inf\big{\\{}s\geq 0:\xi(s)=0\big{\\}},\quad\xi\in
C([0,\infty),\mathbb{R}).$

The author of [13] establishes that $T$ is finite
$\mathbb{P}_{a,c,\gamma,x}$-almost surely. Moreover, $X_{s}=0$ for all ${s\geq
T}$ under $\mathbb{P}_{a,c,\gamma,x}$, i.e. upon hitting zero the process
becomes constant, which is why we also refer to $T$ as _absorption time_.
Although it seems to be well-known, we could not find an explicit reference
for the fact that $T$ is continuous if the underlying process is a logistic
Feller diffusion.

######  Lemma 2.4.

Let $x>0,a\in\mathbb{R}$ and $c,\gamma>0$. Then $T$ is continuous under
$\mathbb{P}_{a,c,\gamma,x}$.

###### Proof.

Since $X$ has continuous paths and $X_{0}=x>0$ under
$\mathbb{P}_{a,c,\gamma,x}$, we obtain $\mathbb{P}_{a,c,\gamma,x}(T=0)=0$. The
continuity of $T$ then follows for example from [12, Thm. 5.1], which states
that $T$ is an infinite convolution of elementary mixtures of exponential
distributions. ∎

Within our context, it will be necessary to consider solutions to (2) with
initial value $x\to\infty$. The required results are covered by the following
statement, whose proof can be found in [13, Thm. 3.9, Cor. 3.10]. Set

$\theta:[0,\infty)\to\mathbb{R},\qquad\lambda\mapsto\int_{0}^{\lambda}\exp\left(\frac{\gamma}{4c}v^{2}-\frac{a}{c}v\right)dv.$
(7)

######  Lemma 2.5.

Let $x\geq 0,a\in\mathbb{R}$ and $c,\gamma>0$. Then the expectation of $T$
under $\mathbb{P}_{a,c,\gamma,x}$ is finite and

$\mathbb{E}_{a,c,\gamma,x}\left[T\right]=\frac{1}{c}\int_{0}^{\infty}\frac{\theta(\lambda)}{\lambda\theta^{\prime}(\lambda)}(1-e^{-x\lambda})\;d\lambda.$

In addition, the measures $(\mathbb{P}_{a,c,\gamma,x})_{x\geq 0}$ converge
weakly, as $x\to\infty$, to the law $\mathbb{P}_{a,c,\gamma,\infty}$ of the
so-called _standard logistic branching process_. Under
$\mathbb{P}_{a,c,\gamma,\infty}$, the absorption time $T$ is a continuous
random variable that is finite almost surely and has finite expectation given
by

$\mathbb{E}_{a,c,\gamma,\infty}\left[T\right]=\sup_{x\geq
0}\mathbb{E}_{a,c,\gamma,x}\left[T\right]=\frac{1}{c}\int_{0}^{\infty}\frac{\theta(\lambda)}{\lambda\theta^{\prime}(\lambda)}\;d\lambda.$

We remark that the continuity of $T$ under $\mathbb{P}_{a,c,\gamma,\infty}$ is
not explicitly claimed in [13]. However, it follows from Lemma 2.4, as we can
apply the Markov property of $X$ and restart the process at some $x>0$ to
express $T$ under $\mathbb{P}_{a,c,\gamma,\infty}$ as the sum of two
independent random variables that are distributed as $T$ under
$\mathbb{P}_{a,c,\gamma,x}$ and the hitting time $\inf\\{s\geq
0\mid\xi(s)=x\\}$ under $\mathbb{P}_{a,c,\gamma,\infty}$.

Within the proof of Theorem 1.4 we will also need information about the
distribution of $\int_{0}^{\infty}X_{s}ds$, where $X$ is a logistic branching
process that satisfies (2). Set

$A_{s}(\xi)\coloneqq\int_{0}^{s}\xi(u)du,\quad s\geq 0,\leavevmode\nobreak\
\xi\in C([0,\infty),\mathbb{R})\leavevmode\nobreak\ .$

In order to study the distribution of $A_{\infty}$ under
$\mathbb{P}_{a,c,\gamma,x}$ the following lemma from [13, Prop. 3.1] will be
very handy, as it establishes that under an appropriate time-change the
logistic branching process fulfills another SDE, which, in turn, is much
easier to analyse.

######  Lemma 2.6.

For any $\xi\in C([0,\infty),\mathbb{R})$ let
$A(\xi)\coloneqq(A_{s}(\xi))_{s\geq 0}$ and let $A^{-1}(\xi)$ be its right-
inverse, i.e. $(A(\xi)\circ A^{-1}(\xi))_{s}=s$ for all $s\in\\{A_{u}(\xi)\mid
u\geq 0\\}$. Let $X$ be the coordinate process. Then, for all $x\geq 0$,
$a\in\mathbb{R}$ and $c,\gamma>0$, the process $R\coloneqq X\circ A^{-1}$
under $\mathbb{P}_{a,c,\gamma,x}$ satisfies the SDE

$dR_{s}=(a-cR_{s})ds+\sqrt{\gamma}dB_{s},\;s\in[0,A_{\infty}],\text{ with
initial condition }R_{0}=x.$ (8)

Processes satisfying (8) for all $s\geq 0$ are called _Ornstein-Uhlenbeck
(O-U) processes_ and are very well-studied. With this lemma at hand we show
the following handy relation between $A_{\infty}$ (under
$\mathbb{P}_{a,c,\gamma,x}$) and the first time that the corresponding O-U
process hits zero.

######  Lemma 2.7.

Let $R$ be defined as in Lemma 2.6. For all $x\geq 0$, $a\in\mathbb{R}$ and
$c,\gamma>0$,

$A_{\infty}=T(R)=\inf\\{s\geq
0:R_{s}=0\\}\quad\mathbb{P}_{a,c,\gamma,x}\text{-almost surely.}$

###### Proof.

Let $X,A^{-1}$ be as in Lemma 2.6. Let $\xi\in C([0,\infty),\mathbb{R})$ be
non-negative such that $\xi(s)=0$ for all $s\geq T(\xi)$, so that $\xi(s)>0$
for all $s\in[0,T(\xi))$. In order to simplify notation we omit the dependence
on $\xi$ in the forthcoming calculations, that is, we write $R_{s}$ for
$R_{s}(\xi)$, $R=(R_{s})_{s\geq 0}$ and similarly for $A,A^{-1},X$ and $T$; in
particular, since $X$ is the coordinate process, $X=\xi$. Note that by our
choice of $\xi$ the integral $A$ is strictly increasing on $[0,T)$ and hence
invertible on $[0,T)$, i.e., $A^{-1}$ is also the left-inverse of $A$ on
$[0,T)$. Therefore, $A^{-1}(A_{T})\geq T$ and, by definition of $R$ and since
$\xi(s)=0$ for all $s\geq T$,

$R_{A_{T}}=(X\circ A^{-1})_{A_{T}}=\xi(A^{-1}(A_{T}))=0,$

so that $A_{T}\geq T(R)$. In order to see the converse inequality, note that,
again by definition of $R$,

$0=R_{T(R)}=X_{A^{-1}_{T(R)}}=\xi(A^{-1}_{T(R)}),$

and so $T\leq A^{-1}_{T(R)}$. Since $\xi$ is non-negative, $A$ is non-
decreasing and so

$A_{T}\leq A_{A^{-1}_{T(R)}}=T(R).$

All in all, $A_{T}=T(R)$ whenever $\xi$ is non-negative with $\xi(s)=0$ for
all $s\geq T$. To conclude the proof, Corollary 2.3 guarantees that
$\mathbb{P}_{a,c,\gamma,x}$-almost surely, the process $X$ is non-negative and
absorbing, where the latter implies $A_{T}=A_{\infty}$. ∎

The connection established in the previous lemma will be very useful, as the
hitting times of O-U processes are well-studied, see for example [1, Rem.
2.3]. We just need the case $a=0$.

######  Lemma 2.8.

Let $R$ be defined as in Lemma 2.6. For all $x\geq 0$ and $c,\gamma>0$, the
density of $T(R)$ under $\mathbb{P}_{0,c,\gamma,x}$ is given by

$p(s)=\frac{2c^{3/2}x}{\sqrt{\gamma\pi}}e^{2cs}\left(e^{2cs}-1\right)^{-3/2}\exp\left(-\frac{cx^{2}}{\gamma(e^{2cs}-1)}\right),\quad
s\geq 0.$

###  2.3 Estimates for Martingales (with Subgaussian Increments)

Here we collect some preliminary facts concerning subgaussian random variables
and martingales. Following standard notation, see for example the extensive
book [2], we call a random variable $X$ _subgaussian with parameter_
$\sigma^{2}>0$ if

$\mathbb{E}\Big{[}e^{s(X-\mathbb{E}[X])}\Big{]}\leq
e^{s^{2}\sigma^{2}/2}\text{ for every }s\in\mathbb{R}.$

The following result provides a handy way of checking whether a random
variable is subgaussian.

######  Theorem 2.9 (Thm. 2.1 in [2]).

Let $X$ be a random variable with $\mathbb{E}[X]=0$. If, for some $v>0$,

$\mathbb{P}(X>\lambda),\mathbb{P}(X<-\lambda)\leq
e^{-\lambda^{2}/2v}\quad\text{for all }\lambda>0,$

then $X$ is subgaussian with parameter $\sigma^{2}=16v$.

Let $(\mathcal{F}_{t})_{t\in\mathbb{N}_{0}}$ be a filtration on some
probability space. Let $(M_{t})_{t\in\mathbb{N}_{0}}$ be a real-valued,
discrete-time stochastic process adapted to
$(\mathcal{F}_{t})_{t\in\mathbb{N}_{0}}$ and such that
$\mathbb{E}[M_{t}]<\infty$ for each $t$. We say that
$(M_{t})_{t\in\mathbb{N}_{0}}$ is called a martingale if
$\mathbb{E}[M_{t+1}|\mathcal{F}_{t}]=M_{t}$ for each $t\in\mathbb{N}_{0}$. We
say that $(M_{t})_{t\in\mathbb{N}_{0}}$ is a _submartingale_ if
$\mathbb{E}[M_{t+1}|\mathcal{F}_{t}]\geq M_{t}$, whereas it is called a
_supermartingale_ if $\mathbb{E}[M_{t+1}|\mathcal{F}_{t}]\leq M_{t}$ for
$t\in\mathbb{N}_{0}$. We continue with a simple lemma that provides a
concentration bound for subgaussian supermartingales. Even though such a
result is probably known or implicit in other works, we could not find a
proper reference and hence we include the (short) proof for completeness.

######  Lemma 2.10.

Let $(M_{t})_{t\in\mathbb{N}_{0}}$ be a supermartingale with respect to a
filtration $(\mathcal{F}_{t})_{t\in\mathbb{N}_{0}}$ such that $M_{0}=0$ and
$M_{t}$ conditional on $\mathcal{F}_{t-1}$ is a subgaussian random variable
with parameter $\sigma_{t}^{2}$. Then

$\mathbb{P}(M_{t}\geq\lambda)\leq\exp\left(-\frac{\lambda^{2}}{2\sum_{i=1}^{t}\sigma_{i}^{2}}\right),\qquad\lambda>0,\leavevmode\nobreak\
\leavevmode\nobreak\ t\in\mathbb{N}_{0}\enspace.$

###### Proof.

Let $s\geq 0$. Using the supermartingale property of $M_{t}$ and the fact that
$M_{t}$, conditional on ${\cal F}_{t-1}$, is subgaussian with parameter
$\sigma_{t}^{2}$, we readily obtain that

$\mathbb{E}\big{[}e^{s(M_{t}-M_{t-1})}\mid\mathcal{F}_{t-1}\big{]}\leq\mathbb{E}\big{[}e^{s(M_{t}-\mathbb{E}[M_{t}\mid\mathcal{F}_{t-1}])}\mid\mathcal{F}_{t-1}\big{]}\leq
e^{s^{2}\sigma_{t}^{2}/2}.$

Using the tower property of conditional expectation and induction we see that

$\mathbb{E}\big{[}e^{sM_{t}}\big{]}=\mathbb{E}\big{[}e^{sM_{t-1}}\mathbb{E}\big{[}e^{s(M_{t}-M_{t-1})}\mid\mathcal{F}_{t-1}\big{]}\big{]}\leq
e^{s^{2}\sigma_{t}^{2}/2}\mathbb{E}\big{[}e^{sM_{t-1}}\big{]}\leq\exp\left(\frac{1}{2}\sum_{i=1}^{t}s^{2}\sigma_{i}^{2}\right).$

Then, by Markov’s inequality,

$\mathbb{P}(M_{t}\geq\lambda)=\mathbb{P}\big{(}e^{sM_{t}}\geq
e^{s\lambda}\big{)}\leq
e^{-s\lambda}\mathbb{E}\big{[}e^{sM_{t}}\big{]}\leq\exp\left(\frac{1}{2}\sum_{i=1}^{t}s^{2}\sigma_{i}^{2}-s\lambda\right).$

Choosing $s=\lambda/\sum_{1\leq i\leq t}\sigma_{i}^{2}>0$ completes the proof.
∎

Hoeffding’s lemma implies that every bounded random variable is subgaussian
and one can deduce the well-known Azuma-Hoeffding inequality, see e.g. [15,
Theorem 3.2.1].

######  Theorem 2.11.

Let $(M_{t})_{t\in\mathbb{N}_{0}}$ be a supermartingale and let
$N\in\mathbb{N}$. Suppose that $|M_{i}-M_{i-1}|\leq c_{i}$ for all $1\leq
i\leq N$. Then

$\mathbb{P}(M_{N}-M_{0}\geq
b)\leq\exp\left(-\frac{b^{2}}{2\sum_{i=1}^{N}c^{2}_{i}}\right),\quad b\geq
0\enspace.$

##  3 Drift and Variation of the Unhappy Particles

In this section we study the drift and the _variation_ of the process of
unhappy particles; more precisely, we determine exact and asymptotic
expressions for the quantities

$\mathbb{E}\big{[}U_{t+1}-U_{t}\mid
U_{t}\big{]}\quad\text{and}\quad\mathbb{E}\big{[}(U_{t+1}-U_{t})^{2}\mid
U_{t}\big{]}.$

We begin as in [5] by writing

$U_{t+1}-U_{t}=X_{t+1}-Y_{t+1},\quad\text{where}\quad
X_{t+1}\coloneqq\left|\mathcal{H}_{t}\cap\mathcal{U}_{t+1}\right|,\leavevmode\nobreak\
Y_{t+1}\coloneqq\left|\mathcal{U}_{t}\cap\mathcal{H}_{t+1}\right|.$ (9)

That is, $X_{t+1}$ stands for the number of particles that were happy at step
$t$ but become unhappy in step $t+1$ (because some unhappy particle in
$\mathcal{U}_{t}$ moved onto their vertex) and $Y_{t+1}$ is the number of
unhappy particles at time $t$ that become happy at step $t+1$ (because at time
$t+1$ they are alone on the vertex that they occupy). From here on we deviate
from [5]. Define

$X_{t+1,h}\coloneqq\mathbb{1}[h\in\mathcal{U}_{t+1}]\quad\text{and}\quad
Y_{t+1,u}\coloneqq\mathbb{1}[u\in\mathcal{H}_{t+1}]$

so that we can write

$X_{t+1}=\sum_{h\in\mathcal{H}_{t}}X_{t+1,h}\enspace\quad\text{and}\quad
Y_{t+1}=\sum_{u\in\mathcal{U}_{t}}Y_{t+1,u}.$ (10)

The following simple lemma, also established in [5], determines the drift. We
include a (short) proof here that uses our notation and because it is
instructive for the computation of the second moment that will follow.

######  Lemma 3.1.

Let $t\in\mathbb{N}_{0}$. Then

$\mathbb{E}\big{[}U_{t+1}-U_{t}\mid
U_{t}\big{]}=H_{t}\left(1-\left(1-\frac{1}{n}\right)^{U_{t}}\right)-U_{t}\frac{n-H_{t}}{n}\left(1-\frac{1}{n}\right)^{U_{t}-1}.$

###### Proof.

The probability that none of the $U_{t}$ unhappy particles jump to a specific
fixed vertex is $(1-1/n)^{U_{t}}$. So, an arbitrary happy particle $h\in{\cal
H}_{t}$ is not joined by any unhappy particle (and thus remains happy) with
that probability, and we obtain

$\mathbb{E}\big{[}X_{t+1,h}\mid
U_{t}\big{]}=1-\left(1-\frac{1}{n}\right)^{U_{t}},\quad h\in\mathcal{H}_{t}.$
(11)

Similarly, any unhappy particle $u\in{\cal U}_{t}$ has $n-H_{t}$ choices for a
position $p_{u,t+1}$ that is not occupied by a happy particle, and all other
$U_{t}-1$ unhappy particles will not choose $p_{u,t+1}$ to move to with
probability $(1-1/n)^{U_{t}-1}$. Thus

$\mathbb{E}\big{[}Y_{t+1,u}\mid
U_{t}\big{]}=\frac{n-H_{t}}{n}\left(1-\frac{1}{n}\right)^{U_{t}-1},\quad
u\in\mathcal{U}_{t}.$ (12)

The statement follows from (9), (10) and linearity of expectation. ∎

We will need later the following simple, non-asymptotic estimate that was
shown in [5] and that follows rather easily from Lemma 3.1.

######  Lemma 3.2.

Let $\varepsilon:\mathbb{N}\to[-1,1]$ and
$M=M(n)\coloneqq(1+\varepsilon)n/2\in\mathbb{N}$. Then, for any
$t\in\mathbb{N}$,

$(1+\varepsilon)U_{t}-7U_{t}^{2}/2n\leq{\mathbb{E}}\big{[}U_{t+1}\mid
U_{t}\big{]}\leq(1+\varepsilon)U_{t}-U_{t}^{2}/n.$

We proceed by deriving an exact expression for the variation. To this end, we
introduce the following quantities:

$A\coloneqq
H_{t}\left(1-(1-1/n)^{U_{t}}\right)+U_{t}\frac{n-H_{t}}{n}(1-1/n)^{U_{t}-1};$
$B\coloneqq
H_{t}(H_{t}-1)\left(1-2\left(1-1/n\right)^{U_{t}}+\left(1-2/n\right)^{U_{t}}\right);$
$C\coloneqq
U_{t}(U_{t}-1)\frac{n-H_{t}}{n}\frac{n-H_{t}-1}{n}(1-2/n)^{U_{t}-2};$
$D\coloneqq
2H_{t}U_{t}\frac{n-H_{t}}{n}(1-1/n)^{U_{t}-1}\left(1-\big{(}1-1/(n-1)\big{)}^{U_{t}-1}\right).$

######  Lemma 3.3.

Let $t\in\mathbb{N}_{0}$. Then

$\mathbb{E}\left[(U_{t+1}-U_{t})^{2}\mid U_{t}\right]=A+B+C-D.$

###### Proof.

From (9) we obtain that
$(U_{t+1}-U_{t})^{2}=X^{2}_{t+1}+Y^{2}_{t+1}-2X_{t+1}Y_{t+1}$, and so

$\mathbb{E}\left[(U_{t+1}-U_{t})^{2}\mid
U_{t}\right]=\mathbb{E}\left[X^{2}_{t+1}\mid
U_{t}\right]+\mathbb{E}\left[Y^{2}_{t+1}\mid
U_{t}\right]-2\mathbb{E}\left[X_{t+1}Y_{t+1}\mid U_{t}\right].$ (13)

Recalling (10) and that $X_{t+1,h}=\mathbb{1}[h\in\mathcal{U}_{t+1}]$, we
obtain

$X^{2}_{t+1}=\sum_{h\in\mathcal{H}_{t}}X_{t+1,h}+\sum_{\begin{subarray}{c}h,h^{\prime}\in\mathcal{H}_{t},h\neq
h^{\prime}\end{subarray}}X_{t+1,h}X_{t+1,h^{\prime}}.$

Note that the distribution of $X_{t+1}$, conditional on $U_{t}$, is invariant
under the choice of $\mathcal{H}_{t}$ and $\mathcal{U}_{t}$. We will use this
fact without further reference within this proof. Then, by linearity of
expectation and (11) we see that

$\mathbb{E}\left[X^{2}_{t+1}\mid
U_{t}\right]=H_{t}\left(1-(1-1/n)\right)^{U_{t}}+\sum_{\begin{subarray}{c}h,h^{\prime}\in\mathcal{H}_{t},h\neq
h^{\prime}\end{subarray}}\mathbb{P}(h,h^{\prime}\in\mathcal{U}_{t+1}\mid
U_{t}).$ (14)

Similarly, we obtain

$Y^{2}_{t+1}=\sum_{u\in\mathcal{U}_{t}}Y_{t+1,u}+\sum_{\begin{subarray}{c}u,u^{\prime}\in\mathcal{U}_{t},u\neq
u^{\prime}\end{subarray}}Y_{t+1,u}Y_{t+1,u^{\prime}},$

where $Y_{t+1,u}=\mathbb{1}[u\in\mathcal{H}_{t+1}]$, and so, using (12), we
obtain

$\mathbb{E}\left[Y^{2}_{t+1}\mid
U_{t}\right]=U_{t}\frac{n-H_{t}}{n}(1-1/n)^{U_{t}-1}+\sum_{\begin{subarray}{c}u,u^{\prime}\in\mathcal{U}_{t},u\neq
u^{\prime}\end{subarray}}\mathbb{P}(u,u^{\prime}\in\mathcal{H}_{t+1}\mid
U_{t}).$ (15)

Note that from (14) and (15) we already spot the $A$ term in the statement of
the lemma. Next we compute the probabilities that appear in the sums on the
right-hand side of (14) and (15). To this end, let
$h,h^{\prime}\in\mathcal{H}_{t}$ with $h\neq h^{\prime}$ and note that

$\mathbb{P}(h,h^{\prime}\in\mathcal{U}_{t+1}\mid
U_{t})=1-\mathbb{P}(h\notin\mathcal{U}_{t+1}\mid
U_{t})-\mathbb{P}(h^{\prime}\notin\mathcal{U}_{t+1}\mid
U_{t})+\mathbb{P}(h,h^{\prime}\notin\mathcal{U}_{t+1}\mid U_{t}).$

We have already argued in Lemma 3.1 when deriving (11) that

$\mathbb{P}(h\notin\mathcal{U}_{t+1}\mid
U_{t})=\mathbb{P}(h^{\prime}\notin\mathcal{U}_{t+1}\mid
U_{t})=(1-1/n)^{U_{t}}.$

Moreover, $h$ and $h^{\prime}$ both remain happy if all particles in ${\cal
U}_{t}$ jump to vertices different from $p_{h,t},p_{h^{\prime},t}$, which
occurs with probability $(1-2/n)^{U_{t}}$. So

$\sum_{\begin{subarray}{c}h,h^{\prime}\in\mathcal{H}_{t},h\neq
h^{\prime}\end{subarray}}\mathbb{P}(h,h^{\prime}\in\mathcal{U}_{t+1}\mid
U_{t})=H_{t}(H_{t}-1)\left(1-2(1-1/n)^{U_{t}}+(1-2/n)^{U_{t}}\right),$ (16)

which gives the term $B$ in the statement of the lemma. Next, let
$u,u^{\prime}\in\mathcal{U}_{t}$ with $u\neq u^{\prime}$. Then we claim that

$\mathbb{P}(u,u^{\prime}\in\mathcal{H}_{t+1}\mid
U_{t})=\frac{n-H_{t}}{n}\frac{n-H_{t}-1}{n}(1-2/n)^{U_{t}-2}.$

To see this, note that there are $n-H_{t}$ vertices that are not occupied by
happy particles and to which $u$ could jump to in order to become happy. This
leaves $n-H_{t}-1$ spots where $u^{\prime}$ could jump to become happy.
Moreover, in order to actually be happy, none of the remaining $U_{t}-2$
particles in $U_{t}$ may jump on the vertices where $u$ and $u^{\prime}$ moved
to. Thus

$\sum_{\begin{subarray}{c}u,u^{\prime}\in\mathcal{U}_{t},u\neq
u^{\prime}\end{subarray}}\mathbb{P}(u,u^{\prime}\in\mathcal{H}_{t+1}\mid
U_{t})=U_{t}(U_{t}-1)\frac{n-H_{t}}{n}\frac{n-H_{t}-1}{n}(1-2/n)^{U_{t}-2},$
(17)

which corresponds to the term $C$ in the statement of the lemma. It remains to
evaluate the term $2\mathbb{E}[X_{t+1}Y_{t+1}\mid U_{t}]$ in (13), which, by
linearity of expectation equals

$2\sum_{\begin{subarray}{c}h\in\mathcal{H}_{t},u\in\mathcal{U}_{t}\end{subarray}}\mathbb{P}(h\in\mathcal{U}_{t+1},u\in\mathcal{H}_{t+1}\mid
U_{t}).$

Observe that, conditional on $u\in{\cal U}_{t}$ becoming happy at time $t+1$,
there remain $U_{t}-1$ unhappy particles that could make $h\in{\cal H}_{t}$
unhappy, and they jump independently to uniformly random positions in
$\\{1,\dots,n\\}\setminus\\{p_{u,t+1}\\}$. Therefore

$\mathbb{P}(h\in\mathcal{U}_{t+1}\mid
U_{t},u\in\mathcal{H}_{t+1})=1-(1-1/(n-1))^{U_{t}-1},\quad h\in{\cal
H}_{t},u\in{\cal U}_{t}.$

Hence, by recalling (12), we obtain

$\displaystyle\mathbb{P}(h\in\mathcal{U}_{t+1},u\in\mathcal{H}_{t+1}\mid
U_{t})$ $\displaystyle=\mathbb{P}(u\in\mathcal{H}_{t+1}\mid
U_{t})\left(1-(1-1/(n-1))^{U_{t}-1}\right)$
$\displaystyle=\frac{n-H_{t}}{n}(1-1/n)^{U_{t}-1}\left(1-(1-1/(n-1))^{U_{t}-1}\right).$

Summing over all $h\in{\cal H}_{t},u\in{\cal U}_{t}$ yields the term $D$. ∎

We proceed with establishing sharp asymptotic bounds for the drift and the
variation; later, when we apply Theorem 2.1, we will exploit these estimates
when $U_{t}=\Theta(n^{1/2})$. In what follows we will make use of the
following elementary asymptotic estimate, which can readily be established by
considering the Taylor series expansion with a remainder term of the function
$x\mapsto(1-x)^{N}$, $N\in\mathbb{N}$, at $x=0$.

######  Fact 3.4.

Uniformly for any $x\in[0,1]$ and $N\in\mathbb{N}_{0}$ we have

$(1-x)^{N}=1-xN+\binom{N}{2}x^{2}-\binom{N}{3}x^{3}+O(N^{4}x^{4}),$ (18)

as $N\to\infty$.

We proceed with deriving an asymptotic expression for the drift. Note that in
the next two lemmas we work under the general assumption that the number of
particles $M=(1+\varepsilon)n/2$, with $\varepsilon=o(1)$; later we will set
$\varepsilon=2\alpha/n^{1/2}+o(1/n^{1/2})$ so that $M=n/2+\alpha
n^{1/2}+o(n^{1/2})$, which is the main focus of the present paper.

######  Lemma 3.5.

Let $\varepsilon=\varepsilon(n)=o(1)$, $u:\mathbb{N}\to\mathbb{N}$ and
$M=M(n)\coloneqq(1+\varepsilon)n/2\in\mathbb{N}$. Then, uniformly,

${\mathbb{E}}\big{[}U_{t+1}-U_{t}\mid U_{t}=u\big{]}=\varepsilon
u-\frac{u^{2}}{n}\left(\frac{7}{4}+\frac{3\varepsilon}{4}\right)+O\left(\frac{u}{n}+\frac{u^{3}}{n^{2}}\right).$

###### Proof.

Recall that $M-U_{t}=H_{t}$. Since $M=(1+\varepsilon){n}/{2}$, it follows from
Lemma 3.1 that

$\mathbb{E}\left[U_{t+1}\mid U_{t}=u\right]\\\
=(1+\varepsilon)\frac{n}{2}\left(1-\Big{(}1-\frac{1}{n}\Big{)}^{u}\right)+u\left(\Big{(}1-\frac{1}{n}\Big{)}^{u}-\Big{(}\frac{1-\varepsilon}{2}+\frac{u}{n}\Big{)}\Big{(}1-\frac{1}{n}\Big{)}^{u-1}\right).$
(19)

We use (18) to obtain the uniform bounds

$(1-1/n)^{u}=1-\frac{u}{n}+\frac{u^{2}}{2n^{2}}+O\left(\frac{u}{n^{2}}+\frac{u^{3}}{n^{3}}\right),\quad(1-1/n)^{u-1}=1-\frac{u-1}{n}+O\left(\frac{u^{2}}{n^{2}}\right).$
(20)

By approximating the terms in (19) with (20), where only a second order
estimate is used for the second $(1-n^{-1})^{n}$ term, and using that
$\varepsilon$ is bounded, we obtain, maintaining the order of the terms within
(19),

$\displaystyle\mathbb{E}[U_{t+1}\mid U_{t}=u]$
$\displaystyle=(1+\varepsilon)\frac{n}{2}\left(\frac{u}{n}-\frac{u^{2}}{2n^{2}}+O\Big{(}\frac{u}{n^{2}}+\frac{u^{3}}{n^{3}}\Big{)}\right)$
$\displaystyle\qquad+u\Bigg{(}1-\frac{u}{n}+O\Big{(}\frac{u^{2}}{n^{2}}\Big{)}-\Big{(}\frac{1-\varepsilon}{2}+\frac{u}{n}\Big{)}\Big{(}1-\frac{u-1}{n}+O\Big{(}\frac{u^{2}}{n^{2}}\Big{)}\Big{)}\Bigg{)}.$

Collecting and cancelling terms then yields the statement. ∎

The next lemma establishes an asymptotic expression for the variation when
$U_{t}$ is not too big.

######  Lemma 3.6.

Let $\varepsilon=\varepsilon(n)=o(1)$ and $u:\mathbb{N}\to\mathbb{N}$ be such
that $u=o(n^{2/3})$ and $M=M(n)\coloneqq(1+\varepsilon)n/2\in\mathbb{N}$.
Then, uniformly,

${\mathbb{E}}\big{[}(U_{t+1}-U_{t})^{2}\mid U_{t}=u\big{]}=u+o(\varepsilon
u^{2}+u).$

###### Proof.

Recall from Lemma 3.3 that

$\mathbb{E}\left[(U_{t+1}-U_{t})^{2}\mid U_{t}\right]=A+B+C-D,$

where the terms $A,B,C,D$ are defined just prior to Lemma 3.3. We estimate
these terms individually, under the assumption that $U_{t}=u=o(n^{2/3})$. We
start with $A$ which, using $H_{t}=M-U_{t}=M-u$, can be rewritten as

$A=(M-u)\left(1-(1-1/n)^{u}\right)+u(n-(M-u))n^{-1}(1-1/n)^{u-1}.$

Using (20) and recalling that $M=(1+\varepsilon)n/2$ we obtain

$1-(1-1/n)^{u}=\frac{u}{n}+O\Big{(}\frac{u^{2}}{n^{2}}\Big{)},\leavevmode\nobreak\
(1-1/n)^{u-1}=1-\frac{u-1}{n}+O\Big{(}\frac{u^{2}}{n^{2}}\Big{)}$

and

$u\frac{n-(M-u)}{n}=u\frac{1-\varepsilon}{2}+\frac{u^{2}}{n}.$

Note that, since $u=o(n)$,

$(M-u)\left(1-(1-1/n)^{u}\right)=\frac{1+\varepsilon}{2}u+o(u),\quad
u(n-(M-u))n^{-1}(1-1/n)^{u-1}=\frac{1-\varepsilon}{2}u+o(u);$

whence we obtain

$A=u+o(u).$ (21)

We proceed by evaluating $B$ which, as $U_{t}=u$, is given by

$B=(M-u)((M-u)-1)\left(1-2\left(1-1/n\right)^{u}+\left(1-2/n\right)^{u}\right).$

Let us start by making a useful observation. Note that, by applying (18) to
the expressions $(1-x)^{N}$ and $(1-2x)^{N}$ for $x\in[0,1/2]$ and
$N\in\mathbb{N}_{0}$ we obtain uniformly

$1-2(1-x)^{N}+(1-2x)^{N}=N(N-1)x^{2}-N(N-1)(N-2)x^{3}+O(N^{4}x^{4}).$ (22)

Consequently, using (22) we obtain

$1-2\left(1-1/n\right)^{u}+\left(1-2/n\right)^{u}=\frac{u(u-1)}{n^{2}}-\frac{u^{3}}{n^{3}}+O\left(\frac{u^{2}}{n^{3}}+\frac{u^{4}}{n^{4}}\right).$
(23)

Also, using once more the fact that $M=(1+\varepsilon)n/2$ we see that

$(M-u)((M-u)-1)=\left(\frac{1+\varepsilon}{2}n-u\right)^{2}-\frac{1+\varepsilon}{2}n+u=\frac{(1+\varepsilon)^{2}}{4}n^{2}-un(1+\varepsilon)+O(u^{2}+n).$

Then, recalling our assumption $u=o(n^{2/3})$, after multiplying the
expression that we have just derived for $(M-u)((M-u)-1)$ with the expression
on the right-hand side of (23) and truncating the computations at terms that
are $o(u)$ we obtain

$B=\frac{(1+\varepsilon)^{2}}{4}u(u-1)-\frac{u^{3}}{n}\left(\frac{5}{4}+\frac{3\varepsilon}{2}+\frac{\varepsilon^{2}}{4}\right)+o(u).$
(24)

Next we consider the terms $C$ and $D$. Recall that, since $U_{t}=u$,

$C=u(u-1)\frac{n-(M-u)}{n}\frac{n-(M-u)-1}{n}(1-2/n)^{u-2}.$

Since $M=n(1+\varepsilon)/2$ we can write

$\frac{n-(M-u)}{n}\frac{n-(M-u)-1}{n}=\frac{(1-\varepsilon)^{2}}{4}+\frac{u}{n}(1-\varepsilon)+O\left(\frac{u^{2}}{n^{2}}+\frac{1}{n}\right).$

Then, since $u=o(n^{2/3})$, truncating at $o(u)$ terms we obtain

$u(u-1)\frac{n-(M-u)}{n}\frac{n-(M-u)-1}{n}=u(u-1)\frac{(1-\varepsilon)^{2}}{4}+\frac{u^{3}}{n}(1-\varepsilon)+o(u).$

Moreover, using (18) we see that

$(1-2/n)^{u-2}=1-\frac{2u}{n}+O\left(\frac{u^{2}}{n^{2}}+\frac{1}{n}\right).$

By multiplying the last two expressions and using $u=o(n^{2/3})$ we arrive at

$C=u(u-1)\frac{(1-\varepsilon)^{2}}{4}+\frac{u^{3}}{n}\frac{1-\varepsilon^{2}}{2}+o(u).$
(25)

Finally we evaluate the term $D$ which, as $U_{t}=u$, can be written as

$D=\left(1-(1-1/(n-1))^{u-1}\right)2(M-u)u\frac{n-(M-u)}{n}(1-1/n)^{u-1}=D_{1}D_{2}(1-1/n)^{u-1},$

where we set

$D_{1}\coloneqq 1-(1-1/(n-1))^{u-1}\text{ and }D_{2}\coloneqq
2(M-u)u\frac{n-(M-u)}{n}.$

Since $M=(1+\varepsilon)n/2$, we can write

$D_{2}=\left(n(1+\varepsilon)-2u\right)u\left(\frac{1-\varepsilon}{2}+\frac{u}{n}\right)=\frac{un}{2}(1-\varepsilon^{2})+2\varepsilon
u^{2}-\frac{2u^{3}}{n}.$ (26)

Moreover, again using (18), we claim that

$D_{1}=\frac{u-1}{n}-\frac{u^{2}}{2n^{2}}+O\left(\frac{u^{3}}{n^{3}}+\frac{u}{n^{2}}\right).$

To see this, let us start by noticing that, thanks to (18), we can write

$D_{1}=\frac{u-1}{n-1}-\frac{u^{2}}{2(n-1)^{2}}+O\left(\frac{u^{3}}{n^{3}}+\frac{u}{n^{2}}\right).$

Observing that $n/(n-1)=1+1/n+O(1/n^{2})$ then establishes the claim about
$D_{1}$. Analogous computations show that the remaining $(1-1/n)^{u-1}$ term
that appears in the expression for $D$ satisfies

$(1-1/n)^{u-1}=1-\frac{u-1}{n}+O\left(\frac{u^{2}}{n^{2}}\right)$

and hence after a little algebra we arrive at

$D_{1}(1-1/n)^{u-1}=\frac{u-1}{n}-\frac{3u^{2}}{2n^{2}}+O\left(\frac{u}{n^{2}}+\frac{u^{3}}{n^{3}}\right).$

Multiplying the last expression with (26) and using that $u=o(n^{2/3})$ we
obtain

$D=u(u-1)\frac{1-\varepsilon^{2}}{2}-\frac{u^{3}}{n}\left(\frac{3}{4}(1-\varepsilon^{2})-2\varepsilon\right)+o(u).$

Consequently, by combining this bound with (25) we obtain

$\displaystyle C-D$
$\displaystyle=u(u-1)\left(\frac{(1-\varepsilon)^{2}}{4}-\frac{1-\varepsilon^{2}}{2}\right)+\frac{u^{3}}{n}\left(\frac{1-\varepsilon^{2}}{2}+\frac{3}{4}(1-\varepsilon^{2})-2\varepsilon\right)+o(u)$
$\displaystyle=-u(u-1)\left(\frac{1}{4}+\frac{\varepsilon}{2}-\frac{3\varepsilon^{2}}{4}\right)+\frac{u^{3}}{n}\left(\frac{5}{4}(1-\varepsilon^{2})-2\varepsilon\right)+o(u).$

Summing $A$ and $B$ as given in (21) and (24), respectively, we obtain

$\displaystyle A+B+C-D$
$\displaystyle=u+\frac{(1+\varepsilon)^{2}}{4}u(u-1)-\frac{u^{3}}{n}\left(\frac{5}{4}+\frac{3\varepsilon}{2}+\frac{\varepsilon^{2}}{4}\right)$
$\displaystyle-u(u-1)\left(\frac{1}{4}+\frac{\varepsilon}{2}-\frac{3\varepsilon^{2}}{4}\right)+\frac{u^{3}}{n}\left(\frac{5}{4}(1-\varepsilon^{2})-2\varepsilon\right)+o(u)$
$\displaystyle=u(1-\varepsilon^{2})+u^{2}\varepsilon^{2}-\frac{u^{3}}{n}\left(\frac{5}{4}+\frac{3\varepsilon}{2}+\frac{\varepsilon^{2}}{4}-\frac{5}{4}(1-\varepsilon^{2})+2\varepsilon\right)+o(u)$
$\displaystyle=u-u\varepsilon^{2}+u^{2}\varepsilon^{2}-\frac{u^{3}}{n}\left(\frac{7\varepsilon}{2}+\frac{3}{2}\varepsilon^{2}\right)+o(u).$

But $u^{3}\varepsilon/n,u^{2}\varepsilon^{2}=o(\varepsilon u^{2})$ and so the
proof is finished. ∎

##  4 The Early Steps

In this section we provide, roughly speaking, tight bounds for the typical
trajectory of the process $(U_{t})_{t\in\mathbb{N}_{0}}$ of unhappy particles
until the first step where $U_{t}$ drops to a value below $n^{1/2}/\delta$,
where $\delta>0$ is (arbitrarily) small. The main result of this section is
the following statement.

######  Lemma 4.1.

There is a $\chi\in\mathbb{R}$ such that the following is true. Let
$\epsilon>0,\alpha\in\mathbb{R}$, $M=n/2+\alpha
n^{1/2}+o(n^{1/2})\in\mathbb{N}$, and let for $\delta>0$

$T_{n,M,\delta}\coloneqq\inf\left\\{t>0:U_{t}\leq n^{1/2}/\delta\right\\}.$

Then, for all sufficiently small $\delta>0$ and all sufficiently large $n$,
with probability at least $1-\delta$,

$U_{T_{n,M,\delta}}\sim n^{1/2}/\delta,\quad
T_{n,M,\delta}=(1\pm\epsilon)\frac{4}{7}\delta
n^{1/2},\quad\text{and}\quad\sum_{0\leq t\leq
T_{n,M,\delta}}U_{t}=\frac{2}{7}n\ln n+\frac{4}{7}n\ln{\delta}+\chi
n\pm\epsilon n.$

In particular, (roughly) $\frac{4}{7}\delta n^{1/2}$ steps are required to
drop below $n^{1/2}/\delta$ unhappy particles, and at this step the
accumulated number of unhappy particles, which corresponds to the total number
of jumps, is (roughly) $\frac{2}{7}n\ln n$.

The rest of this section is devoted to the proof of Lemma 4.1. As a
preparation we first establish that the (conditional) distribution of the
number $U_{t+1}$ of unhappy particles, given $U_{t}$, is subgaussian. This
simple fact will be useful in several occasions, and it will allow us to apply
the machinery from Section 2.3.

######  Lemma 4.2.

Let $M=M(n)\in\mathbb{N}$. Then, conditional on $U_{t}$, the random variable
$U_{t+1}$ is subgaussian with parameter $64U_{t}$. In particular,

$\mathbb{P}\big{[}U_{t+1}-\mathbb{E}[U_{t+1}\mid U_{t}]\geq\lambda\mid
U_{t}\big{]},\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbb{P}\big{[}U_{t+1}-\mathbb{E}[U_{t+1}\mid U_{t}]\leq-\lambda\mid
U_{t}\big{]}\leq e^{-\lambda^{2}/8U_{t}},\quad\lambda>0.$

###### Proof.

Let us assume without loss of generality that the set of unhappy particles at
time $t$ is $\mathcal{U}_{t}=\\{p_{1},\ldots,p_{U_{t}}\\}$. Define the Doob
martingale

$M_{i}\coloneqq\mathbb{E}_{p_{1,t+1},\dots,p_{i,t+1}}[U_{t+1}\mid U_{t}],\quad
1\leq i\leq U_{t},$

and set $M_{0}=\mathbb{E}[U_{t+1}\mid U_{t}]$. In words, $M_{i}$ is the
(conditional) expectation of $U_{t+1}$ given $U_{t}$, knowing the values of
$p_{1,t+1},\dots,p_{i,t+1}$, i.e. the movements of the first $i$ particles
that were unhappy at step $t$. Clearly, $M_{U_{t}}=U_{t+1}$ and
$|M_{i+1}-M_{i}|\leq 2$ for $1\leq i\leq U_{t}$ since, by changing the
position to which any one of the $U_{t}$ particles moves to, we alter
$U_{t+1}$ by at most $2$. Therefore, we can apply the Azuma-Hoeffding
inequality from Theorem 2.11 and obtain

$\mathbb{P}\big{[}U_{t+1}-\mathbb{E}[U_{t+1}\mid U_{t}]\geq\lambda\mid
U_{t}\big{]}\leq\exp\left(-\lambda^{2}/8U_{t}\right);$

the other bound is obtained analogously. The claim then follows from Theorem
2.9. ∎

An important and useful consequence of the previous statement is the powerful
property that the number of unhappy particles $U_{t+1}$ is typically always
‘close’ to its conditional expected value $\mathbb{E}[U_{t+1}\mid U_{t}]$, as
stated in the following lemma.

######  Lemma 4.3.

Let $\alpha\in\mathbb{R}$ and $M=n/2+\alpha n^{1/2}+o(n^{1/2})\in\mathbb{N}$.
Then ${\mathbb{P}}({\cal E})=1-o(1/n)$, where

${\cal E}\coloneqq\bigcap_{t\geq 0}{\cal
E}_{t}\quad\text{and}\quad\mathcal{E}_{t}\coloneqq\left\\{\big{|}U_{t+1}-{\mathbb{E}}[U_{t+1}\mid
U_{t}]\big{|}\leq 4\sqrt{U_{t}\ln n}\right\\}.$

###### Proof.

Theorem 1.3 asserts that $T_{n,M}\leq t_{n}\coloneqq n^{1/2}\ln^{2}n$ with
probability $1-o(1/n)$, so it suffices to consider $t\leq t_{n}$ only in the
following sense. Since $\mathcal{E}^{c}_{t}=\emptyset$ for $t\geq T_{n,M}$, we
obtain

$\mathbb{P}(\mathcal{E}^{c})=\mathbb{P}\Big{(}\bigcup_{t\leq
T_{n,M}}\mathcal{E}^{c}_{t}\Big{)}\leq\mathbb{P}\Big{(}\bigcup_{t\leq
t_{n}}\mathcal{E}^{c}_{t}\Big{)}+\mathbb{P}(T_{n,M}>t_{n})=\mathbb{P}\Big{(}\bigcup_{t\leq
t_{n}}\mathcal{E}^{c}_{t}\Big{)}+o(1/n),$

and hence we can focus on the events $\mathcal{E}^{c}_{t}$ for $t\leq t_{n}$
only. It follows from Lemma 4.2 that

$\mathbb{P}\left(|U_{t+1}-{\mathbb{E}}[U_{t+1}\mid U_{t}]\big{|}\geq
4\sqrt{U_{t}\ln n}\mid U_{t}\right)\leq 2\exp\left(-\frac{16U_{t}\ln
n}{8U_{t}}\right)=2n^{-2}.$

A union bound then yields $\mathbb{P}({\cal
E})=1-o(1/n)-2t_{n}n^{-2}=1-o(1/n)$, as claimed. ∎

We proceed with the proof of Lemma 4.1. For any $0<\delta,\eta<1$ set

$i^{*}=i^{*}(\delta,\eta)\coloneqq\left\lfloor\left(\frac{\ln(\delta
n^{3/10})}{\eta}\right)^{3}\right\rfloor\text{ and }u_{i}\coloneqq
u_{i}(\delta,\eta)=\delta^{-1}n^{1/2}\exp\left(\eta(i^{*}-i)^{1/3}\right),\leavevmode\nobreak\
0\leq i\leq i^{*}.$ (27)

Note that $u_{i^{*}}=n^{1/2}/\delta$ and $e^{-\eta}n^{4/5}\leq u_{0}\leq
n^{4/5}$. Moreover, let $T_{0}\coloneqq\inf\\{t\geq 0:U_{t}<u_{0}\\}$, and
define recursively the stopping times

$T_{i}\coloneqq\inf\big{\\{}t\geq
0:U_{T_{0}+T_{1}+\dots+T_{i-1}+t}<u_{i}\big{\\}},\quad 1\leq i\leq i^{*}.$

These times play the role of ‘checkpoints’ for the evolution of the number of
unhappy particles. Indeed, at time $T_{0}$ we have, for the first time, less
than $u_{0}$ unhappy particles. Then, after $T_{1}$ additional steps, the
number of unhappy particles falls for the first time below $u_{1}$, …, and
after $T_{i}$ additional steps, the number of unhappy particles falls for the
first time below $u_{i}$. Eventually, after $T_{0}+\dots+T_{i^{*}}$ steps the
number of unhappy particles will fall for the first time below
$n^{1/2}/\delta$, so that $T_{n,M,\delta}=T_{0}+\dots+T_{i^{*}}$. The
definition of the $u_{i}$’s may look a bit cumbersome, but, as we will see, it
is chosen with great care so that it allows us to control the total deviation
of all the $U_{t}$’s simultaneously from their typical trajectory.

The rest of the section is structured as follows. First, we study $T_{0}$ by
showing that $U_{t}$, as long as it is rather largish, stays ‘very close’ to a
deterministic value that can be obtained by iterating a (deterministic)
function $t$ times. This statement is in a specific sense best possible, as
after some point in time the number of unhappy particles starts fluctuating
too much. Moreover, we obtain fine control of the sum of the iterates of this
function. Then, in Subsection 4.2 we use martingale arguments to show a
general statement that allows us to bound the number of steps that are needed
to drop from a given number $u$ of unhappy particles to a slightly smaller
number $(1-\eta)u$. Then we apply this statement with (essentially) the ratios
$1-\eta\approx u_{i+1}/u_{i}$ to gain sufficient control of all $T_{i}$’s.
Finally, in Subsection 4.3 we combine our findings to prove Lemma 4.1.

###  4.1 Analysis of $T_{0}$

In order to study the beginning of the process we show that the number of
unhappy particles at step $t$, as long as $t$ is not too large, stays close to
it’s iterated expectation, or, more precisely, to an asymptotic version
thereof, using Lemma 3.1.

######  Lemma 4.4.

Let $\alpha\in\mathbb{R}$ and $M=n/2+\alpha n^{1/2}+o(n^{1/2})\in\mathbb{N}$.
Define the functions

$f:\mathbb{R}\to\mathbb{R},\quad x\mapsto
x+\left(\frac{1}{2}-x\right)(1-e^{-x})-x\left(\frac{1}{2}+x\right)e^{-x}.$

and $f^{(t)}:\mathbb{R}\to\mathbb{R}$ inductively by $f^{(0)}(x)=x$ and
$f^{(t+1)}(x)=f(f^{(t)}(x))$ for any $x\in\mathbb{R}$ and
$t\in\mathbb{N}_{0}$. Then, with probability tending to one,

$U_{t}=f^{(t)}(1/2)n\pm(t+1)n^{1/2}\ln n,\quad t\geq 0.$

###### Proof.

We begin with two observations that we shall use later. Since $U_{t}\leq n$,
by applying Lemma 4.3 we obtain that with probability $1-o(1)$ and with room
to spare

$U_{t+1}=\mathbb{E}[U_{t+1}\mid U_{t}]\pm 4n^{1/2}\ln^{1/2}n,\quad\text{for
all}\quad t\in\mathbb{N}_{0}.$ (28)

Moreover, using Lemma 3.1 we obtain for all sufficiently large $n$ and for all
$0\leq x\leq 1$ such that $xn\in\mathbb{N}$ and $t\in\mathbb{N}_{0}$

$\frac{1}{n}\mathbb{E}\big{[}U_{t+1}-U_{t}\mid
U_{t}=xn\big{]}=(1/2-x)\left(1-\Big{(}1-\frac{1}{n}\Big{)}^{xn}\right)-x(1/2+x)\Big{(}1-\frac{1}{n}\Big{)}^{xn-1}\pm
3\alpha n^{-1/2}.$

Note that $(1-n^{-1})^{n}=e^{-1}(1\pm n^{-1})$, since $(1-n^{-1})^{n}$ is
increasing and $(1-n^{-1})^{n-1}$ is decreasing (and both approach $e^{-1})$.
Thus it follows from the definition of $f(x)$ given in the statement of the
lemma that, for all sufficiently large $n$,

$\frac{1}{n}\mathbb{E}\big{[}U_{t+1}\mid
U_{t}=xn\big{]}=f(x)\pm(3|\alpha|+1)n^{-1/2},\quad\text{where}\quad
xn\in\mathbb{N},t\in\mathbb{N}_{0}.$ (29)

In the rest we will assume that $n$ is so large that we can use (29) and $\ln
n\geq 4|\alpha|$. Moreover, we assume that (28) holds. Under these assumptions
we will show (by induction on $t$) that

$U_{t}=f^{(t)}(1/2)n\pm(t+1)n^{1/2}\ln n\text{ for all }t\in\mathbb{N}_{0},$

so that the lemma is established. Since $U_{0}=M$ and $f^{(0)}(1/2)=1/2$ the
claim is obviously true for $t=0$. Next, assume the claim holds for some
$t\in\mathbb{N}$. From (28) and (29) together with the induction hypothesis we
obtain

$\frac{1}{n}U_{t+1}=f\big{(}f^{(t)}(1/2)\pm(t+1)n^{-1/2}\ln
n\big{)}\pm(3|\alpha|+1)n^{-1/2}.$

Note that $f^{\prime}(x)=e^{-x}(1-5x/2+x^{2})$, so that $|f^{\prime}(x)|\leq
1$ for all, say, $x\in[0,1]$. Thus, by Taylor’s theorem, $f(x+y)=f(x)\pm y$
for all $x,y$ such that $x,x+y\in[0,1]$. We obtain

$\frac{1}{n}U_{t+1}=f^{(t+1)}(1/2)\pm(t+1)n^{-1/2}\ln
n\pm(3|\alpha|+1)n^{-1/2}.$

Since $\ln n\geq(3|\alpha|+1)$ the claim is established. ∎

Towards the proof of Theorem 1.4 the following lemma about the sum of the
iterates of $f$ will be very useful.

######  Lemma 4.5.

Let $f,f^{(t)}$ be as in Lemma 4.4. Then $f^{(t)}(1/2)$ is decreasing in $t$
and there is a $\chi\in\mathbb{R}$ such that, as $N\to\infty$,

$f^{(N)}(1/2)=\frac{4}{7}N^{-1}+O\big{(}N^{-2}\ln
N\big{)}\quad\mbox{and}\quad\sum_{t\leq N}f^{(t)}(1/2)=\frac{4}{7}\ln
N+\chi+O(N^{-1}\ln N).$

######  Remark 4.6.

Numerical investigations show that $\chi=-0.1236(\dots)$. However, the
convergence is quite slow, as indicated by our error bounds.

###### Proof.

Let us collect some properties of $f$. Note that
$f^{\prime}(x)=e^{-x}(1-5x/2+x^{2})$ and that $1/2$ and $2$ are the roots of
$1-5x/2+x^{2}$. So, $f^{\prime}$ is positive and decreases on $[0,1/2)$. Since
$f(0)=0$ we obtain $f(x)>0$ for $x\in(0,1/2]$. Moreover, $f^{\prime}(0)=1$ and
thus $(f(x)-x)^{\prime}<0$ on $(0,1/2]$; again using that $f(0)=0$ we obtain
$f(x)<x$ in this interval. All in all we have established

$0<f(x)<x,\quad x\in(0,1/2].$ (30)

Let us consider the sequence $(f^{(t)}(1/2))_{t\in\mathbb{N}_{0}}$ which,
according to (30), is _decreasing_ and _positive_. Since $0$ is the only
fixpoint of the (continuous) $f$ in $[0,1/2]$ we obtain

$f^{(t)}(1/2)\to 0\quad\text{as}\quad t\to\infty.$ (31)

A simple computation shows that

$f(0)=0,f^{\prime}(0)=1,f^{\prime\prime}(0)=-\frac{7}{2}\quad\text{and}\quad
f^{\prime\prime\prime}(x)=e^{-x}(8-13x/2+x^{2}).$

and so there is a $C>0$ such that

$f(x)=x-\frac{7}{4}x^{2}\pm Cx^{3},\quad x\in[0,1/2].$ (32)

Up to now we have collected several properties of $f$ that are actually
sufficient to establish the claim. We will proceed with a routine argument,
and the interested reader may consult [6, Ch. 8.4] for prototypical
applications. Let us abbreviate $x_{t}=f^{(t)}(1/2)$ and define
$y_{t}=x_{t}^{-1}$. We obtain from (32) and (31), as $t\to\infty$,

$y_{t+1}=y_{t}\Big{(}1-\frac{7}{4}x_{t}+O(x_{t}^{2})\Big{)}^{-1}=y_{t}\Big{(}1+\frac{7}{4}x_{t}+O(x_{t}^{2})\Big{)}=y_{t}+\frac{7}{4}+O(x_{t}).$

Since $x_{t}\to 0$ as $t\to\infty$ we obtain that, say, $y_{t+1}-y_{t}\geq 1$
for all sufficiently large $t$. Thus $y_{t}\geq t/2$ and so $x_{t}\leq 2/t$
for all sufficiently large $t$. This, in turn, implies
$y_{t}=\frac{7t}{4}+O(\ln t)$, and thus

$x_{t}=f^{(t)}(1/2)=\frac{4}{7}t^{-1}+O\big{(}t^{-2}\ln t\big{)},\quad
t\to\infty.$

In other words, if we set $g(t)\coloneqq f^{(t)}(1/2)-4/7t$, then
$|g(t)|=O(t^{-2}\ln t)$. Thus $\sum_{t\geq 0}g(t)$ is absolutely convergent,
and since $\sum_{1\leq t\leq N}t^{-1}=\ln N+\gamma+O(N^{-1})$ for a
$\gamma\in\mathbb{R}$ the claim is established. ∎

By combining the previous facts we readily obtain the likely value of $T_{0}$
and $U_{T_{0}}$.

######  Corollary 4.7.

Let $\alpha\in\mathbb{R},M=n/2+\alpha n^{1/2}+o(n^{1/2})\in\mathbb{N}$ and
$0<\delta,\eta<1$. Then, with probability tending to one as $n\to\infty$,

$T_{0}=(1\pm 2\eta)\frac{4}{7}n^{1/5}\quad\text{and}\quad
U_{T_{0}}=(1+o(\ln^{-4}n))u_{0}.$

###### Proof.

Recall from (27) that $e^{-\eta}n^{4/5}\leq u_{0}\leq n^{4/5}$. By Lemma 4.4
with probability tending to one as $n\to\infty$

$U_{t}=f^{(t)}(1/2)n\pm(t+1)n^{1/2}\ln n,\quad t\geq 0.$

We will assume that this event holds for the remainder of the proof. Setting
$N_{-}\coloneqq 4(1-\eta)n^{1/5}/7$ by Lemma 4.5, we have for every $t\leq
N_{-}$ that

$U_{t}\geq(1+\eta)n^{4/5}+O\left(n^{3/5}\ln{n}\right)\pm 2n^{7/10}\ln
n>n^{4/5}\geq u_{0}$

for all large enough $n$. Moreover, setting $N_{+}\coloneqq
4(1+2\eta)n^{1/5}/7$,

$U_{N_{+}}\leq\frac{n^{4/5}}{1+2\eta}+O\left(n^{3/5}\ln{n}\right)\pm
2n^{7/10}\ln n<e^{-\eta}n^{4/5}\leq u_{0}$

for all large enough $n$. Therefore $4(1-\eta)n^{1/5}/7\leq T_{0}\leq
4(1+2\eta)n^{1/5}/7,$ establishing the first claim. Concerning the second
statement, it follows again from Lemma 4.5 that, whenever $t\in[N_{-},N_{+}]$,

$|U_{t+1}-U_{t}|\leq O(nt^{-2}\ln t)+2(t+2)n^{1/2}\ln n=o(n/t\ln^{4}{n})$

and so $U_{t+1}=(1+o(\ln^{-4}{n}))U_{t}$ for all such $t$. ∎

###  4.2 Analysis of $T_{i},1\leq i\leq i^{*}$

Our next lemma states that if we begin with a sufficiently large number $u$ of
unhappy particles, then typically the number of steps that are required to
drop below $(1-\eta)u$ unhappy particles is roughly $4\eta n/7u$ and, during
those steps, the number of unhappy particles never exceeds $(1+\eta)u$. In the
sequel, this will allow us to study $T_{i}$, by selecting
$u_{i}=(1-\eta_{i})u_{i-1}$, see (27). In the proof of Lemma 4.8 below we
construct two processes, a supermartingale and a submartingale, which bound
from below and above, respectively, the number of unhappy particles; then we
analyse these processes by exploiting that $U_{t}$, conditional on $U_{t-1}$,
is subgaussian, see Lemma 4.2.

######  Lemma 4.8.

Let $0<\eta<1/16$. Then there is an $n_{0}\in\mathbb{N}$ such that for all
$n\geq n_{0}$ the following is true. Let $\alpha\in\mathbb{R}$ and
$M=n/2+\alpha n^{1/2}+o(n^{1/2})\in\mathbb{N}$. Moreover, let
$u:\mathbb{N}\to\mathbb{N}$ be such that $3|\alpha|\eta^{-1}n^{1/2}\leq u\leq
n/\ln^{1/2}n$ and, for $t_{0}\in\mathbb{N}$, let

$T=T(u,t_{0})\coloneqq\inf\big{\\{}t\in\mathbb{N}_{0}:U_{t_{0}+t}\not\in[(1-\eta)u,(1+\eta)u]\big{\\}}.$

Then, conditional on $U_{t_{0}}=u$, with probability at least
$1-8\exp\left(-\eta^{3}u^{2}/800n\right)$,

$T=(1\pm 5\eta)\frac{4\eta n}{7u}\quad\text{and}\quad
U_{t_{0}+T}=(1-\eta)(1\pm 12\eta^{2})u.$

###### Proof.

Since $(U_{t})_{t\in\mathbb{N}_{0}}$ is a Markov chain, we assume without loss
of generality within the proof that $t_{0}=0$; in particular, with slight
abuse of notation, $U_{0}=u$. Set
$\varepsilon\coloneqq{2M}/{n}-1\sim{2\alpha}n^{-1/2}$ and define, for
$t\in\mathbb{N}_{0}$, the two discrete-time random processes

$W_{t}^{+}\coloneqq U_{t\wedge
T}+\frac{7}{4}\frac{(1+\eta)^{3}u^{2}}{n}(t\wedge T)\quad\mbox{and}\quad
W_{t}^{-}\coloneqq U_{t\wedge
T}+\frac{7}{4}\frac{(1-\eta)^{3}u^{2}}{n}(t\wedge T).$

For $t\in\mathbb{N}_{0}$, let $\mathcal{F}_{t}$ be the $\sigma$-algebra
generated by the process of unhappy particles until step $t$, and set ${\cal
F}\coloneqq({\cal F}_{t})_{t\in\mathbb{N}_{0}}$. We will argue that
$(W_{t}^{+})_{t\in\mathbb{N}_{0}}$ is a submartingale and that
$(W_{t}^{-})_{t\in\mathbb{N}_{0}}$ is a supermartingale (both with respect to
$\cal F$). By applying Lemma 3.5 we see that there is a $n_{0}\in\mathbb{N}$
such that for all $n\geq n_{0}$ we have for every
$3|\alpha|\eta^{-1}n^{1/2}\leq u\leq n/\ln^{1/2}n$ that

${\mathbb{E}}\big{[}U_{t+1}-U_{t}\mid U_{t}=u\big{]}=\varepsilon
u-\frac{u^{2}}{n}\left(\frac{7}{4}+\frac{3\varepsilon}{4}\right)+O\left(\frac{u}{n}+\frac{u^{3}}{n^{2}}\right)=-\big{(}1\pm\eta)\frac{7}{4}\frac{u^{2}}{n}.$

In what follows we will always assume that $n\geq n_{0}$. Note that, by the
Markov property of $(U_{t})_{t\geq 0}$,
$\mathbb{E}[W_{t}^{-}\mid\mathcal{F}_{t-1}]=\mathbb{E}[W_{t}^{-}\mid
U_{t-1}]$. Since $(1-\eta)u\leq U_{t-1}\leq(1+\eta)u$ if $t\leq T$, we obtain
under this assumption that

$\displaystyle\mathbb{E}[W_{t}^{-}\mid\mathcal{F}_{t-1}]$
$\displaystyle=\mathbb{E}[U_{t}\mid
U_{t-1}]+\frac{7}{4}\frac{(1-\eta)^{3}u^{2}}{n}t$ $\displaystyle\leq
U_{t-1}-(1-\eta)\frac{7}{4}\frac{U_{t-1}^{2}}{n}+\frac{7}{4}\frac{(1-\eta)^{3}u^{2}}{n}t$
$\displaystyle\leq
U_{t-1}-(1-\eta)\frac{7}{4}\frac{(1-\eta)^{2}u^{2}}{n}+\frac{7}{4}\frac{(1-\eta)^{3}u^{2}}{n}t=W_{t-1}^{-}.$
(33)

On the other hand, $W_{t}^{-}=W_{t-1}^{-}$ when $t>T$, showing that
$W_{t}^{-}$ is a supermartingale. An analogous argument, using again that
$(1-\eta)u\leq U_{t-1}\leq(1+\eta)u$ when $t\leq T$, shows that
$\mathbb{E}[W_{t}^{+}\mid\mathcal{F}_{t-1}]\geq W_{t-1}^{+}$ and therefore
$W_{t}^{+}$ is a submartingale. Having established the super/sub-martingale
nature of $W^{-}$ and $W^{+}$ we claim that

$\mathbb{P}(T<t^{-})\leq
2\exp\left(-\frac{\eta^{3}u^{2}}{800n}\right),\quad\text{where}\quad
t^{-}=t^{-}(u,n,\eta)\coloneqq\frac{4\eta n}{7u}\frac{1-\eta}{(1+\eta)^{3}}.$
(34)

To see this, note that if $T<t^{-}$ then either $U_{t^{-}\wedge T}>(1+\eta)u$
or $U_{t^{-}\wedge T}<(1-\eta)u$ and hence

$\mathbb{P}(T<t^{-})\leq\mathbb{P}(U_{t^{-}\wedge
T}>(1+\eta)u)+\mathbb{P}(U_{t^{-}\wedge T}<(1-\eta)u).$ (35)

We start by estimating the probability that $U_{t^{-}\wedge T}>(1+\eta)u$. To
this end we will utilize the supermartingale $W^{-}_{t^{-}}$ since, roughly
speaking, it is ‘hard’ for a supermartingale to become large and hence the
probability of interest should be (very) small. Similarly, we will estimate
the probability that $U_{t^{-}\wedge T}$ is smaller than $(1-\eta)u$ by by
utilizing $W^{+}_{t^{-}}$; this will give us a good bound on the probability
of interest since it is ‘hard’ for a submartingale to become small. Following
this discussion and using that $W^{-}_{0}=U_{0}=u$ we obtain

$\mathbb{P}(U_{t^{-}\wedge
T}>(1+\eta)u)=\mathbb{P}\Big{(}W^{-}_{t^{-}}-\frac{7}{4}\frac{(1-\eta)^{3}u^{2}}{n}(t^{-}\wedge
T)>(1+\eta)u\Big{)}\leq\mathbb{P}\big{(}W^{-}_{t^{-}}-W^{-}_{0}>\eta
u\big{)}.$ (36)

Lemma 4.2 asserts that $U_{t}$, conditional on $U_{t-1}$, is a subgaussian
random variable with parameter $64U_{t-1}$. This in turn implies that, for
every $t\in\mathbb{N}$, the random variable $W_{t}^{-}$ conditional on
$U_{t-1}$ is subgaussian with parameter $64(1+\eta)u\leq 100u$ (with room to
spare); the same is true for $W_{t}^{+}$ conditional on $U_{t-1}$. Thus, using
Lemma 2.10 we obtain that

$\mathbb{P}\big{(}W^{-}_{t^{-}}-W^{-}_{0}\geq\eta
u\big{)}\leq\exp\left(-\frac{\eta^{2}u^{2}}{200ut^{-}}\right),$

and substituting the value of $t^{-}$ we see that the last expression is at
most half of the upper bound on $\mathbb{P}(T<t^{-})$ in (34). It remains to
bound the second probability on the right-hand side of (35). Note that

$\displaystyle\mathbb{P}(U_{t^{-}\wedge T}<(1-\eta)u)$
$\displaystyle=\mathbb{P}\Big{(}W^{+}_{t^{-}}-W^{+}_{0}<-\eta
u+\frac{7}{4}\frac{(1+\eta)^{3}u^{2}}{n}(t^{-}\wedge T)\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}W^{+}_{t^{-}}-W^{+}_{0}<-\eta
u+\frac{7}{4}\frac{(1+\eta)^{3}u^{2}}{n}t^{-}\Big{)}$
$\displaystyle=\mathbb{P}\big{(}W^{+}_{t^{-}}-W^{+}_{0}<-\eta u+\eta
u-\eta^{2}u\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}-(W^{+}_{t^{-}}-W^{+}_{0})>\eta^{2}u\big{)}.$

Using once more Lemmas 2.10 and 4.2 we see that the last expression is at most
$\exp\big{(}-\frac{7\eta^{3}u^{2}}{800n}\big{)}$, which is also at most half
of the expression in (34), completing its proof. Our next goal is to show

$\mathbb{P}(T>t^{+})\leq\exp\left(-\frac{\eta^{3}u^{2}}{800n}\right),\quad\text{where}\quad
t^{+}=t^{+}(u,n,\eta)\coloneqq\frac{4\eta
n}{7u}\frac{1+\eta}{(1-\eta)^{3}}>t^{-}.$ (37)

To see this, observe first that if $T>t^{+}$, then
$(1-\eta)u<U_{t^{+}}<(1+\eta)u$. So, obviously,

$\mathbb{P}(T>t^{+})\leq\mathbb{P}\big{(}U_{t^{+}}>(1-\eta)u,T>t^{+}\big{)}.$

Note that it doesn’t look necessary to maintain the event $\\{T>t^{+}\\}$, but
we will actually need it in a moment. Expressing $U_{t}$ in terms of
$W^{-}_{t}$ once more we obtain

$\mathbb{P}\big{(}U_{t^{+}}>(1-\eta)u,T>t^{+}\big{)}\leq\mathbb{P}\Big{(}W^{-}_{t^{+}}-W^{-}_{0}\geq-\eta
u+\frac{7}{4}\frac{(1-\eta)^{3}u^{2}}{n}t^{+}\Big{)}=\mathbb{P}\Big{(}W^{-}_{t^{+}}-W^{-}_{0}\geq\eta^{2}u\Big{)}.$

Hence, using again Lemmas 2.10 and 4.2, we obtain

$\mathbb{P}(T>t^{+})\leq\exp\left(-\frac{7u^{2}\eta^{3}(1-\eta)^{3}}{800n(1+\eta)}\right)\leq\exp\left(-\frac{u^{2}\eta^{3}}{800n}\right),$

So far we have established that

$\mathbb{P}(t^{-}\leq T\leq t^{+})\geq
1-3\exp\left(-\frac{\eta^{3}u^{2}}{800n}\right).$ (38)

To complete the proof of the lemma, it remains to show that
$U_{T}=(1-\eta)(1\pm 12\eta^{2})u$ with the required probability bound
indicated in the statement of the lemma. Note that either $U_{T}\geq(1+\eta)u$
or $U_{T}\leq(1-\eta)u$. Thus, proceeding as in (36), we obtain that

$\displaystyle\mathbb{P}(U_{T}\geq(1+\eta)u)$
$\displaystyle\leq\mathbb{P}\big{(}W^{-}_{T}-W^{-}_{0}\geq\eta
u\big{)}\leq\mathbb{P}\big{(}W^{-}_{T\wedge t^{+}}-W^{-}_{0}\geq\eta
u\big{)}+\mathbb{P}(T>t^{+}).$

Using Lemmas 2.10 and 4.2 we obtain

$\mathbb{P}\big{(}W^{-}_{T\wedge t^{+}}-W^{-}_{0}\geq\eta
u\big{)}\leq\exp\left(-\frac{7\eta u^{2}}{16\cdot
200n}\right)\leq\exp\left(-\frac{\eta^{3}u^{2}}{800n}\right),$

and so, together with (37), we arrive at

$\mathbb{P}(U_{T}<(1+\eta)u)\geq
1-2\exp\left(-\frac{\eta^{3}u^{2}}{800n}\right).$ (39)

The last missing part is to show that
$\mathbb{P}\big{(}U_{T}\geq(1-\eta)(1-12\eta^{2})u\big{)}$ is large. To this
end we utilize for a last time the submartingale $W^{+}_{t}$. Therefore,

$\displaystyle\mathbb{P}\big{(}$ $\displaystyle
U_{T}<(1-\eta)(1-12\eta^{2})u\big{)}$
$\displaystyle\leq\mathbb{P}\left(W^{+}_{T\wedge t^{+}}-W^{+}_{0}<-\eta
u-12\eta^{2}u+12\eta^{3}u+\frac{7}{4}\frac{(1+\eta)^{3}u^{2}}{n}t^{+}\right)+\mathbb{P}(T>t^{+}).$
(40)

Our assumption $0<\eta<1/16$ guarantees that $(1+\eta)^{4}\leq 1+5\eta$ and
$(1-\eta)^{-3}\leq(1-3\eta)^{-1}\leq 1+4\eta$. Thus

$-\eta-12\eta^{2}+12\eta^{3}+\frac{7}{4}\frac{(1+\eta)^{3}u}{n}t^{+}\leq-\eta-11\eta^{2}+\eta(1+10\eta)\leq-\eta^{2},$

leading to the bound

$\mathbb{P}\left(W^{+}_{T\wedge t^{+}}-W^{+}_{0}<-\eta
u-12\eta^{2}u+12\eta^{3}u+\frac{7}{4}\frac{(1+\eta)^{3}u^{2}}{n}t^{+}\right)\leq\mathbb{P}\big{(}W^{+}_{T\wedge
t^{+}}-W^{+}_{0}<-\eta^{2}u\big{)}.$

Using once more Lemmas 2.10 and 4.2 we see that the last probability is at
most $\exp(-\eta^{3}u^{2}/800n)$, and together with (37) and (4.2) we conclude
that

$\mathbb{P}\big{(}U_{T}<(1-\eta)(1-12\eta^{2})u\big{)}\leq
2\exp\left(-\frac{\eta^{3}u^{2}}{800n}\right).$

Combining this with (38) and (39) gives the result. ∎

In the next step we apply Lemma 4.8 iteratively for $1\leq i\leq i^{*}$ to
obtain bounds for the $T_{i}$’s and the corresponding number of jumps.

######  Lemma 4.9.

Let $\epsilon>0,\alpha\in\mathbb{R}$ and $M=n/2+\alpha
n^{1/2}+o(n^{1/2})\in\mathbb{N}$. For all sufficiently small $\delta>0$ and
all sufficiently large $n$ the following holds with probability at least
$1-\delta$. Set $\eta\coloneqq 12\delta^{1/9}$ and $i^{*}=i^{*}(\delta,\eta)$.
Then $U_{T_{n,M,\delta}}\sim n^{1/2}/\delta,$

$T_{n,M,\delta}=\sum_{0\leq i\leq
i^{*}}T_{i}=T_{0}+(1\pm\epsilon)\frac{4}{7}\delta
n^{1/2},\quad\text{and}\quad\sum_{T_{0}<t\leq
T_{n,M,\delta}}U_{t}=\frac{6}{35}n\ln n+\frac{4}{7}n\ln{\delta}\pm\epsilon n.$

###### Proof.

Assume, with foresight, that
$0<\delta<\min\\{|\alpha|^{-3/2},2^{-54}3^{-9}\\}$. In addition abbreviate
$S_{i}\coloneqq T_{0}+\dots+T_{i}$ for $0\leq i\leq i^{*}$, so that
$S_{i^{*}}=T_{n,M,\delta}$ and set

$\eta_{i}\coloneqq\ln\left(\frac{u_{i}}{u_{i+1}}\right)=\eta\big{(}(i^{*}-i)^{1/3}-(i^{*}-i-1)^{1/3}\big{)}\leq\eta.$

We will apply Lemma 4.8 iteratively. For $0\leq i\leq i^{*}-1$ assume that
$\\{U_{S_{i}}=\hat{u}_{i}\\}$ for some
$(1-12\eta_{i}^{2})u_{i}\leq\hat{u}_{i}\leq u_{i}$. Set
$\hat{\eta}_{i}=1-u_{i+1}/\hat{u}_{i}$ and using $1-x\leq e^{-x}\leq
1-x+x^{2}$ when $x\geq 0$ we have

$\hat{\eta}_{i}\leq
1-\exp(-\eta_{i})\leq\eta_{i}\quad\text{and}\quad\hat{\eta}_{i}\geq
1-\frac{\exp(-\eta_{i})}{1-12\eta_{i}^{2}}\geq\frac{\eta_{i}-13\eta_{i}^{2}}{1-12\eta_{i}^{2}}\geq\eta_{i}-13\eta_{i}^{2}.$

Due to our choice of $\delta$ and $\eta$ we have $\hat{\eta}_{i}\leq\eta\leq
1/16$. Moreover, since $a-b=(a^{1/3}-b^{1/3})(a^{2/3}+(ab)^{1/3}+b^{2/3})$ we
obtain $\eta_{i}\geq\eta/3(i^{*}-i)^{2/3}$. Using that $\eta=12\delta^{1/9}$
we obtain

$\delta^{-1}=\delta^{-1/3}\cdot\delta^{-2/3}\geq
2^{6}3^{3}\eta^{-3}\cdot\max\\{|\alpha|,2^{36}3^{6}\\}\geq
2^{6}3^{3}|\alpha|\hat{\eta}_{i}^{-1}\cdot\frac{\hat{\eta}_{i}}{\eta^{3}}\geq
2^{6}3^{2}|\alpha|\hat{\eta}_{i}^{-1}\cdot\frac{1-13\eta}{\eta^{2}(i^{*}-i)^{2/3}}.$

Using $e^{x}\geq x^{2}/2,x\geq 0$, this in turn leads to

$\hat{u}_{i}\geq(1-12\eta^{2})u_{i}=(1-12\eta^{2})\delta^{-1}n^{1/2}\exp(\eta(i^{*}-i)^{1/3})\geq\delta^{-1}n^{1/2}\eta^{2}(i^{*}-i)^{2/3}/4\geq
3|\alpha|\hat{\eta}_{i}^{-1}n^{1/2}.$

We have established that conditional on $\\{U_{S_{i}}=\hat{u}_{i}\\}$ such
that $(1-12\eta_{i}^{2})u_{i}\leq\hat{u}_{i}\leq u_{i}$ every condition of
Lemma 4.8 is met if we choose $\hat{\eta}_{i}=1-u_{i+1}/\hat{u}_{i}$.
Therefore, using $\eta_{i}\geq\eta(i^{*}-i)^{-2/3}/3$ and $e^{x}\geq x^{9}/9!$
for $x\geq 0$, with probability at least

$1-8\exp\left(-\frac{\hat{\eta}_{i}^{3}\hat{u}_{i}^{2}}{800n}\right)\geq
1-8\exp\left(-\frac{\eta_{i}^{3}u_{i}^{2}}{4^{4}\cdot 1600n}\right)\geq
1-8\exp\left(-\frac{\eta^{12}(i^{*}-i)}{9!\cdot 3^{3}\cdot
800\delta^{2}}\right)\geq 1-8\exp\left(-\frac{i^{*}-i}{\delta^{2/3}}\right)$

the following three events hold:

$T_{i+1}=(1\pm 5\hat{\eta}_{i})\frac{4\hat{\eta}_{i}n}{7\hat{u}_{i}}=(1\pm
25\eta_{i})\frac{4\eta_{i}n}{7u_{i}},\qquad u_{i+1}\geq
U_{S_{i+1}}\geq(1-12\eta_{i+1}^{2})u_{i+1},$

and

$U_{t}=(1\pm\hat{\eta}_{i})\hat{u}_{i}=(1\pm 2\eta_{i})u_{i},\quad S_{i}\leq
t<S_{i+1}.$ (41)

With this at hand we will now consider the intersection of these events for
all $0\leq i\leq i^{*}-1$ and appropriately chosen $\hat{u}_{i}$’s. Indeed, by
Corollary 4.7, for sufficiently large $n$, $u_{0}\geq
U_{T_{0}}=(1-o(\ln^{-4}n))u_{0}\geq(1-12\eta_{0}^{2})u_{0}$ with probability
$1-o(1)$. Thus, by induction on $0\leq i\leq i^{*}-1$ and Lemma 4.3, with
probability at least

$1-8\sum_{0\leq i\leq
i^{*}-1}\exp\left(-\frac{i^{*}-i}{\delta^{2/3}}\right)-o(1)\geq
1-9\exp\left(-\delta^{-2/3}\right),$

we have

$U_{T_{n,M,\delta}}\geq\mathbb{E}[U_{T_{n,M,\delta}}\mid
U_{T_{n,M,\delta}-1}]-4\sqrt{U_{T_{n,M,\delta}-1}},$ $T_{i+1}=(1\pm
25\eta_{i})\frac{4\eta_{i}n}{7u_{i}},\leavevmode\nobreak\ \leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \leavevmode\nobreak\ U_{t}=(1\pm
2\eta_{i})u_{i},\quad\text{for all}\quad 0\leq i\leq i^{*}-1,S_{i}\leq
t<S_{i+1}.$ (42)

Since $u_{i^{*}-1}=O(n^{1/2})$ we also have $U_{T_{n,M,\delta}-1}=O(n^{1/2})$,
which together with Lemma 3.2 implies $T_{n,M,\delta}\sim n^{1/2}/\delta$. In
order to prove the remaining statements of the lemma, that is, to estimate the
sum of the $T_{i+1}$’s and the corresponding sum of the $U_{t}$’s, we require
suitable bounds for the ratios $\eta_{i}/u_{i}$. For $x\in\mathbb{R}$ we have
(using the classical inequality $1+x\leq e^{x}$)

$1-x\leq\frac{xe^{-x}}{1-e^{-x}}\leq 1.$ (43)

Since $\eta_{i}\leq\eta$ and $u_{i}=e^{\eta_{i}}u_{i+1}$ for $0\leq i\leq
i^{*}-1$, (43) implies for $0\leq i\leq i^{*}-1$ that

$\frac{\eta_{i}}{u_{i}}\leq\frac{\eta_{i}}{e^{\eta_{i}}u_{i+1}}\leq\frac{1}{u_{i+1}}-\frac{1}{u_{i}}\quad\text{and}\quad\frac{\eta_{i}}{u_{i}}\geq(1-\eta_{i})\left(1-\frac{1}{e^{\eta_{i}}}\right)\frac{1}{u_{i+1}}\geq(1-\eta)\left(\frac{1}{u_{i+1}}-\frac{1}{u_{i}}\right).$

Using (42) and these bounds, the sum of the $T_{i+1}$’s can be bounded by a
telescoping sum. So, for sufficiently large $n$, with probability at least
$1-p_{\delta}$, where $p_{\delta}\coloneqq 9\exp(-\delta^{-2/3})$,

$\sum_{0\leq i\leq i^{*}-1}T_{i+1}=(1\pm 30\eta)\frac{4n}{7u_{i^{*}}}=(1\pm
30\eta)\frac{4}{7}\delta n^{1/2}.$ (44)

Moreover, using (42),

$\sum_{T_{0}<t\leq S_{i^{*}}}U_{t}=\sum_{0\leq i\leq i^{*}-1}(1\pm
2\eta_{i})T_{i}u_{i}=\frac{4}{7}n\sum_{0\leq i\leq i^{*}-1}(1\pm
35\eta_{i})\eta_{i}.$

Now, using the definition of the $\eta_{i}$’s,

$\sum_{0\leq i\leq
i^{*}-1}\eta_{i}=\eta(i^{*})^{1/3}=\frac{3}{10}\ln{n}+\ln{\delta}\pm\eta\quad\mbox{and}\quad\sum_{0\leq
i\leq i^{*}-1}\eta_{i}^{2}\leq\eta^{2}\sum_{1\leq i\leq
i^{*}}\frac{1}{i^{4/3}}\leq 4\eta^{2}.$

Thus, whenever $n$ is sufficiently large

$\sum_{T_{0}<t\leq
S_{i^{*}}}U_{t}=\frac{6}{35}n\ln{n}+\frac{4}{7}n\ln{\delta}\pm 10\eta n$ (45)

Note that the error terms $\pm 30\eta$ in (44) and $\pm 10\eta$ in (45) can be
made arbitrarily small by choosing $\delta>0$ appropriately. Moreover, the
(error) probability $p_{\delta}$ can similarly be made arbitrarily small,
completing the proof. ∎

###  4.3 Putting everything together – Proof of Lemma 4.1

With all preparations at hand we now prove Lemma 4.1. Let $\epsilon>0$ and
throughout the proof we will assume that $\delta>0$ is sufficiently small and
$n$ is sufficiently large so that we can apply Lemma 4.9. Set $\eta\coloneqq
12\delta^{1/9}$. Then by Lemmas 4.4 and 4.9 with probability $1-\delta-o(1)$
the following four events hold:

$U_{t}=f^{(t)}(1/2)n\pm(t+1)n^{1/2}\ln n,\quad t\geq 0,\quad
U_{T_{n,M,\delta}}\sim n^{1/2}/\delta,$
$T_{n,M,\delta}=T_{0}+(1\pm\epsilon)\frac{4}{7}\delta
n^{1/2}\quad\text{and}\quad\sum_{T_{0}\leq t\leq
T_{n,M,\delta}}U_{t}=\frac{6}{35}n\ln n+\frac{4}{7}n\ln{\delta}\pm\epsilon n.$

For the remainder of the proof assume that the above three events hold. Then
by Corollary 4.7 we have $T_{0}=(1\pm 2\eta)4n^{1/5}/7$ and so
$T_{n,M,\delta}=(1\pm 2\epsilon)4\delta n^{1/2}/7$. Moreover, Lemma 4.5
implies that there is a $\chi\in\mathbb{R}$ such that

$\sum_{0\leq t\leq T_{0}}U_{t}=\frac{4}{7}n\ln\big{(}(1\pm
2\eta)4n^{1/5}/7\big{)}+\chi n+O(n^{9/10}\ln n)=\frac{4}{35}n\ln n+\chi
n\pm\epsilon n,$

and so

$\sum_{0\leq t\leq T_{n,M,\delta}}U_{t}=\frac{2}{7}n\ln
n+\frac{4}{7}n\ln{\delta}+\chi n\pm 2\epsilon n.$

The result follows as $\epsilon>0$ is arbitrary and $\delta$ can be chosen to
be arbitrarily small.

##  5 Proof of Theorem 1.1 and Lemma 1.2 – Dispersion Time

Recall that $M=M(n)=n/2+\alpha n^{1/2}+o(n^{1/2})$. In what follows we fix a
sufficiently small $\delta>0$ and a sufficiently large $n$ so that Lemma 4.1
is applicable with $\epsilon=1/2$. In particular,

$T_{n,M,\delta}=\inf\\{t>0:U_{t}\leq n^{1/2}/\delta\\}\leq\delta
n^{1/2}\leavevmode\nobreak\ \leavevmode\nobreak\ \text{with probability at
least}\leavevmode\nobreak\ \leavevmode\nobreak\ 1-\delta.$ (46)

With this at hand set

$T^{\prime}_{n,M,\delta}\coloneqq T_{n,M}-T_{n,M,\delta}.$ (47)

In words, $T^{\prime}_{n,M,\delta}$ is the number of steps that are taken by
the dispersion process after the first step at which the number of unhappy
particles drops below $n^{1/2}/\delta$. The forthcoming argument goes roughly
as follows. First, we will use the diffusion approximation toolbox from
Section 2.1 to establish that the number of unhappy particles after step
$T_{n,M,\delta}$, scaled appropriately, converges weakly to a process that
satisfies (1). From this, Lemma 1.2 will follow quickly. As a further
consequence we will then deduce that $n^{-1/2}T^{\prime}_{n,M,\delta}$
converges in distribution to the absorption time of this limiting process.
Finally, by combining (46) with Lemma 2.5 to take the limit $\delta\to 0$, we
will conclude that $n^{-1/2}T_{n,M}$ converges to an almost surely positive
random variable $T_{\alpha}$. It will turn out that $T_{\alpha}$ is
distributed as the first time $T$ at which the coordinate process hits zero
under the measure $\mathbb{P}_{2\alpha,7/4,1,\infty}$ given in Lemma 2.5,
i.e.,

$\mathbb{P}(T_{\alpha}\leq s)=\mathbb{P}_{2\alpha,7/4,1,\infty}(T\leq s),\quad
s\geq 0,$ (48)

and then Theorem 1.1 will be established as well. In order to make this
outline precise we consider the (continuous) time-shifted process

$U^{\prime}_{s}\coloneqq U_{\lfloor s\rfloor+T_{n,M,\delta}},\quad s\geq 0.$

By applying Theorem 2.1 we will show that
$(n^{-1/2}U^{\prime}_{sn^{1/2}})_{s\geq 0}$ converges weakly to a diffusion.
Note that the following lemma is just a reformulation of Lemma 1.2 in the
Introduction, as (49) corresponds to the SDE (1).

######  Lemma 5.1.

Let $\delta>0$. As $n\to\infty$, the process
$(n^{-1/2}U^{\prime}_{sn^{1/2}})_{s\geq 0}$ converges weakly to a process $X$
that satisfies

$dX_{s}=\left(2\alpha
X_{s}-\frac{7}{4}X_{s}^{2}\right)ds+\sqrt{X_{s}}dB_{s},\leavevmode\nobreak\
\leavevmode\nobreak\ s>0,\quad\text{and}\quad X_{0}=\delta^{-1}.$ (49)

###### Proof.

We will apply Theorem 2.1 with $h=h(n)=n^{-1/2}$ and $Y^{(n)}_{t}\coloneqq
n^{-1/2}U^{\prime}_{t}$ for $t\in\mathbb{N}_{0}$. First, note that it is
necessary to extend the SDE (49) in a way that it has a unique solution not
only for all initial values $x\geq 0$, but for all $x\in\mathbb{R}$. To this
end, write $a^{+}=\max\\{a,0\\}$ for $a\in\mathbb{R}$ and consider the SDE

$dX_{s}=\left(2\alpha
X_{s}^{+}-\frac{7}{4}(X_{s}^{+})^{2}\right)ds+\sqrt{X_{s}^{+}}dB_{s},\quad
s>0,\text{ with }X_{0}=x\in\mathbb{R}.$ (50)

Note that if the initial value $x$ is negative, then $X=x$ uniquely satisfies
this SDE. For ${x\geq 0}$, recall that Corollary 2.3 guarantees the existence
of a unique solution $(X,B_{2\alpha,7/4,1,x},\mathscr{P}_{2\alpha,7/4,1,x})$
to (49) with $X_{0}=x$ and such that $X\geq 0$ almost surely. Hence, if $x\geq
0$, (50) coincides with (49) with initial value $X_{0}=x$ and we conclude that
(50) possesses a unique solution for all $x\in\mathbb{R}$.

Next, we employ Lemmas 3.5 and 3.6 with $\varepsilon(n)=2\alpha
n^{-1/2}+o(n^{-1/2})$, as $M=n/2+\alpha n^{1/2}+o(n^{1/2})$. For this purpose,
let $R<\infty$ and consider ${x\in
S^{(n)}\subseteq\\{0,n^{-1/2},2n^{-1/2},...,n^{1/2}\\}}$ with $|x|\leq R$.
Then, Lemma 3.5 with $u=xn^{1/2}$ implies that

$b^{(n)}(x)=\frac{\mathbb{E}\left[n^{-1/2}U^{\prime}_{t+1}-n^{-1/2}U^{\prime}_{t}\mid
n^{-1/2}U^{\prime}_{t}=x\right]}{n^{-1/2}}=2\alpha
x-\frac{7}{4}x^{2}+o\left(R+R^{3}\right).$

Further, as $xn^{1/2}=o(n^{2/3})$ due to $|x|\leq R$, it follows from Lemma
3.6 with $u=xn^{1/2}$ that

$a^{(n)}(x)=\frac{\mathbb{E}\left[(n^{-1/2}U^{\prime}_{t+1}-n^{-1/2}U^{\prime}_{t})^{2}\mid
n^{-1/2}U^{\prime}_{t}=x\right]}{n^{-1/2}}=x+o\left(R+R^{2}\right).$ (51)

We therefore obtain that for any $R<\infty$

$\lim_{n\to\infty}\sup_{x\in S^{(n)},|x|\leq R}\left|b^{(n)}(x)-\left(2\alpha
x-\frac{7}{4}x^{2}\right)\right|=0\text{ and }\lim_{n\to\infty}\sup_{x\in
S^{(n)},|x|\leq R}|a^{(n)}(x)-x|=0.$ (52)

By Lemma 4.1 we have

$U^{\prime}_{0}=U_{T_{n,M,\delta}}\sim n^{1/2}/\delta\leavevmode\nobreak\
\leavevmode\nobreak\ \text{with probability}\leavevmode\nobreak\
\leavevmode\nobreak\ 1-o(1).$

Moreover, we will argue in a moment that

$\gamma_{3}^{(n)}(x)=\frac{\mathbb{E}\left[|n^{-1/2}U^{\prime}_{t+1}-n^{-1/2}U^{\prime}_{t}|^{3}\mid
n^{-1/2}U^{\prime}_{t}=x\right]}{n^{-1/2}}=\frac{\mathbb{E}\left[|U^{\prime}_{t+1}-U^{\prime}_{t}|^{3}\mid
U^{\prime}_{t}=xn^{1/2}\right]}{n}$

satisfies

$\lim_{n\to\infty}\sup_{x\in S^{(n)},|x|\leq R}|\gamma^{(n)}_{3}(x)|=0.$ (53)

The last two facts, together with (52) and the existence of a unique solution
to (50) guarantee that we can apply Theorem 2.1 to conclude that
$(n^{-1/2}U^{\prime}_{sn^{1/2}})_{s\geq 0}$ converges weakly to a process $X$
that satisfies (49) with $X_{0}=1/\delta$, and the proof is finished.

It remains to establish (53). Set

$\mathcal{E}_{t}\coloneqq\left\\{\left|U^{\prime}_{t+1}-\mathbb{E}\left[U^{\prime}_{t+1}\mid
U^{\prime}_{t}\right]\right|\leq 4\sqrt{U^{\prime}_{t}\ln n}\right\\}$

and start by noticing that $-U^{\prime}_{t}\leq
U^{\prime}_{t+1}-U^{\prime}_{t}\leq
2U^{\prime}_{t}-U^{\prime}_{t}=U^{\prime}_{t}$, i.e.
${|U^{\prime}_{t+1}-U^{\prime}_{t}|\leq U^{\prime}_{t}}$. Then, according to
Lemma 4.3, $\mathbb{P}(\mathcal{E}_{t})=1-o(1/n)$ and we obtain

$\displaystyle\mathbb{E}\left[\mathbb{1}_{\overline{\mathcal{E}_{t}}}\left|U^{\prime}_{t+1}-U^{\prime}_{t}\right|^{3}\mid
U^{\prime}_{t}=xn^{1/2}\right]\leq
x^{3}n^{3/2}\mathbb{E}\left[\mathbb{1}_{\overline{\mathcal{E}_{t}}}\mid
U^{\prime}_{t}=xn^{1/2}\right]=o\left(R^{3}n^{1/2}\right).$

Additionally, on the event $\mathcal{E}_{t}$, we can use Lemma 3.2 to obtain

$|U^{\prime}_{t+1}-U^{\prime}_{t}|\leq 4\sqrt{U^{\prime}_{t}\ln
n}+|\varepsilon|U^{\prime}_{t}+O\left((U^{\prime}_{t})^{2}n^{-1}\right).$

For $U^{\prime}_{t}=xn^{1/2}$ and since
$|\varepsilon|=O\left(n^{-1/2}\right)$, it follows that for $n$ sufficiently
large

$|U^{\prime}_{t+1}-U^{\prime}_{t}|\leq 4\sqrt{xn^{1/2}\ln n}+O(x+x^{2})\leq
5\sqrt{Rn^{1/2}\ln n}.$

Combined with (51), we obtain

$\displaystyle\mathbb{E}\left[\mathbb{1}_{\mathcal{E}_{t}}\left|U^{\prime}_{t+1}-U^{\prime}_{t}\right|\left(U^{\prime}_{t+1}-U^{\prime}_{t}\right)^{2}\mid
U^{\prime}_{t}=xn^{1/2}\right]$ $\displaystyle\leq 5\sqrt{Rn^{1/2}\ln
n}\;\mathbb{E}\left[(U^{\prime}_{t+1}-U^{\prime}_{t})^{2}\mid
U^{\prime}_{t}=xn^{1/2}\right]$
$\displaystyle=O\left(\left(R^{3/2}+R^{5/2}\right)n^{3/4}\sqrt{\ln n}\right).$

Hence,
$\gamma_{3}^{(n)}(x)=O\big{(}(R^{3/2}+R^{5/2})n^{-1/4}\sqrt{\ln{n}}+R^{3}n^{-1/2}\big{)}$,
which implies (53). ∎

Recall from Corollary 2.3 that
$(X,B_{2\alpha,7/4,1,x},\mathscr{P}_{2\alpha,7/4,1,x})$ represents a solution
of (49) with initial value $x\geq 0$ and that the corresponding hitting time
of zero is given by

$T=\inf\\{s\geq 0:X_{s}=0\\}$ (54)

under the probability measure $\mathbb{P}_{2\alpha,7/4,1,x}$. The next
statement asserts that $n^{-1/2}T^{\prime}_{n,M,\delta}$ converges in
distribution to $T$ under $\mathbb{P}_{2\alpha,7/4,1,1/\delta}$.

######  Lemma 5.2.

Let $\delta>0$. Then, as $n\to\infty$,
$n^{-1/2}T^{\prime}_{n,M,\delta}\stackrel{{\scriptstyle d}}{{\to}}T$, with $T$
given by (54) under the probability measure
$\mathbb{P}_{2\alpha,7/4,1,1/\delta}$.

###### Proof.

Let $s\geq 0$ and recall from Section 2.1 that, under
$\mathbb{P}_{2\alpha,7/4,1,1/\delta}$, $X_{s}=0$ is equivalent to $T\leq s$.
Similarly, $U_{\lfloor s\rfloor}=0$ if and only if $T_{n,M}\leq s$, from which
we obtain that $T^{\prime}_{n,M,\delta}=T_{n,M}-T_{n,M,\delta}\leq s$ if and
only if $U^{\prime}_{s}=U_{\lfloor s\rfloor+T_{n,M,\delta}}=0$. Hence,

$\mathbb{P}_{2\alpha,7/4,1,1/\delta}(X_{s}=0)=\mathbb{P}_{2\alpha,7/4,1,1/\delta}(T\leq
s)\quad\text{and}\quad\mathbb{P}(U^{\prime}_{s}=0)=\mathbb{P}(T^{\prime}_{n,M,\delta}\leq
s).$

As Lemma 5.1 entails
$\lim_{n\to\infty}\mathbb{P}\big{(}n^{-1/2}U^{\prime}_{sn^{1/2}}=0\big{)}=\mathbb{P}_{2\alpha,7/4,1,1/\delta}(X_{s}=0)$,
we conclude

$\lim_{n\to\infty}\mathbb{P}(n^{-1/2}T^{\prime}_{n,M,\delta}\leq
s)=\mathbb{P}_{2\alpha,7/4,1,1/\delta}(T\leq s).\qed$

With the convergence in distribution shown in the previous lemma at hand, we
are now in the position to prove Theorem 1.1. Indeed, recall from (46) that
$T_{n,M,\delta}\leq\delta n^{1/2}$ with probability at least $1-\delta$ for
$\delta$ sufficiently small and $n$ large enough. As $T_{n,M,\delta}$ is non-
negative, this implies that

$n^{-1/2}T^{\prime}_{n,M,\delta}\leq
n^{-1/2}T_{n,M}\leq\delta+n^{-1/2}T^{\prime}_{n,M,\delta}\text{ with
probability at least }1-\delta.$

Applying Lemma 5.2, we obtain for all $s\geq 0$

$\lim_{n\to\infty}\mathbb{P}(n^{-1/2}T_{n,M}\leq
s)\leq\lim_{n\to\infty}\mathbb{P}(n^{-1/2}T^{\prime}_{n,M,\delta}\leq
s)=\mathbb{P}_{2\alpha,7/4,1,1/\delta}(T\leq s)$

and

$\displaystyle\lim_{n\to\infty}\mathbb{P}\big{(}n^{-1/2}T_{n,M}\geq s\big{)}$
$\displaystyle\leq\lim_{n\to\infty}\mathbb{P}\big{(}n^{-1/2}T_{n,M}\geq
s,T_{n,M,\delta}\leq\delta n^{1/2}\big{)}+\delta$
$\displaystyle\leq\mathbb{P}_{2\alpha,7/4,1,1/\delta}\big{(}T\geq
s-\delta\big{)}+\delta.$

Note that for all
$\mathbb{P}_{2\alpha,7/4,1,x_{1}}(T\geq\tau)\geq\mathbb{P}_{2\alpha,7/4,1,x_{2}}(T\geq\tau)$
for all $x_{1}>x_{2}\geq 0$ and $\tau\geq 0$, since $X$ is almost surely
continuous and needs a positive and finite amount of time to drop from $x_{1}$
to $x_{2}$. So, since according to Lemma 2.5 we have $\lim_{\delta\to
0}\mathbb{P}_{2\alpha,7/4,1,1/\delta}=\mathbb{P}_{2\alpha,7/4,1,\infty}$ and
$T$ is continuous,

$\lim_{\delta\to 0}\mathbb{P}_{2\alpha,7/4,1,1/\delta}\big{(}T\geq
s-\delta\big{)}\leq\lim_{\delta\to
0}\mathbb{P}_{2\alpha,7/4,1,\infty}\big{(}T\geq
s-\delta\big{)}=\mathbb{P}_{2\alpha,7/4,1,\infty}\big{(}T\geq s\big{)},$

which yields

$\lim_{n\to\infty}\mathbb{P}(n^{-1/2}T_{n,M}\leq
s)=\mathbb{P}_{2\alpha,7/4,1,\infty}(T\leq s),\quad s\geq 0.$

Thus, $n^{-1/2}T_{n,M}\stackrel{{\scriptstyle d}}{{\to}}T_{\alpha}$, where
$T_{\alpha}$ satisfies (48). Moreover,
$\mathbb{P}_{2\alpha,7/4,1,\infty}(T>0)=1$ implies that $T_{\alpha}$ is
positive almost surely, and this completes the proof of Theorem 1.1.

##  6 Absorption Time of the Diffusion Process

Let $\alpha\in\mathbb{R}$. In this section we study properties of the
absorption time of the diffusion process $T_{\alpha}$ in Theorem 1.1, which,
as we showed in Section 5, is distributed like the first time $T$ the
coordinate process hits zero under the measure
$\mathbb{P}_{2\alpha,7/4,1,\infty}$, see also (48). We begin with considering
the expected value

$\lim_{n\to\infty}\mathbb{E}\left[n^{-1/2}T_{n,M}\right]=\mathbb{E}\left[T_{\alpha}\right]=\mathbb{E}_{2\alpha,7/4,1,\infty}\left[T\right],$

where $M=n/2+\alpha n^{1/2}+o(n^{1/2})$, and provide asymptotic bounds when
$|\alpha|\to\infty$.

######  Lemma 6.1.

Let $\alpha\in\mathbb{R}$. Then

$\mathbb{E}\left[T_{\alpha}\right]=\frac{\pi^{3/2}}{\sqrt{7}}+\frac{1}{\sqrt{7}}\sum_{m\geq
1}\frac{\Gamma(\frac{m+1}{2})}{m!}\left(\frac{8\alpha}{\sqrt{7}}\right)^{m}t_{m},$
(55)

where

$t_{m}\coloneqq\sum_{k\geq
0}\frac{2}{(\frac{m+1}{2}+2k)(\frac{m+3}{2}+2k)}=H_{(m-1)/4}-H_{(m-3)/4},\quad
m\in\mathbb{N}_{0},$

and $H_{x}=\sum_{k\geq 1}\Big{(}\frac{1}{k}-\frac{1}{k+x}\Big{)}$ for all
$x\in\mathbb{R}$ with $x>-1$.

###### Proof.

Abbreviate $A=A(\alpha)\coloneqq{8\alpha}/{7}$. From (7) and Lemma 2.5, we
obtain that

$\frac{7}{4}\mathbb{E}\left[T_{\alpha}\right]=\int_{0}^{\infty}\frac{1}{\lambda}\exp\left(-\frac{1}{7}\lambda^{2}+A\lambda\right)\int_{0}^{\lambda}\exp\left(\frac{1}{7}\mu^{2}-A\mu\right)d\mu\;d\lambda\enspace.$

Substituting $\mu=\lambda u$ and applying Fubini’s theorem yields

$\frac{7}{4}\mathbb{E}\left[T_{\alpha}\right]=\int_{0}^{1}\int_{0}^{\infty}\exp\left(-\frac{1}{7}(1-u^{2})\lambda^{2}+A(1-u)\lambda\right)d\lambda\;du.$
(56)

We shall use the well-known fact that for any $c>0$ and $n>-1$

$\int_{0}^{\infty}x^{n}\exp(-cx^{2})dx=\frac{1}{2}c^{-(n+1)/2}\Gamma\left(\frac{n+1}{2}\right),$

which follows directly by a simple change of variables in the definition of
the Gamma function. By expanding $\exp(A(1-u)\lambda)=\sum_{m\geq
0}(A(1-u))^{m}\lambda^{m}/m!$ we obtain, again by Fubini’s theorem,

$\begin{split}\int_{0}^{\infty}\exp\left(-\frac{1}{7}(1-u^{2})\lambda^{2}+A(1-u)\lambda\right)&d\lambda=\int_{0}^{\infty}\exp\left(-\frac{1}{7}(1-u^{2})\lambda^{2}\right)\sum_{m\geq
0}\frac{1}{m!}(A(1-u))^{m}\lambda^{m}d\lambda\\\ &=\sum_{m\geq
0}\frac{1}{m!}(A(1-u))^{m}\int_{0}^{\infty}\lambda^{m}\exp\left(-\frac{1}{7}(1-u^{2})\lambda^{2}\right)d\lambda\\\
&=\frac{1}{2}\sum_{m\geq
0}\frac{1}{m!}(A(1-u))^{m}\cdot\Gamma\left(\frac{m+1}{2}\right)\left(\frac{1-u^{2}}{7}\right)^{-(m+1)/2}.\end{split}$

Since $1-u^{2}=(1-u)(1+u)$ we further obtain from (56) and Fubini that

$\begin{split}\frac{7}{4}\mathbb{E}\left[T_{\alpha}\right]&=\frac{\sqrt{7}}{2}\int_{0}^{1}\sum_{m\geq
0}\frac{\Gamma(\frac{m+1}{2})}{m!}\left(\sqrt{7}A\right)^{m}\frac{(1-u)^{(m-1)/2}}{(1+u)^{(m+1)/2}}du\\\
&=\frac{\sqrt{7}}{2}\sum_{m\geq
0}\frac{\Gamma(\frac{m+1}{2})}{m!}\left(\frac{8\alpha}{\sqrt{7}}\right)^{m}\int_{0}^{1}\frac{(1-u)^{(m-1)/2}}{(1+u)^{(m+1)/2}}du.\end{split}$
(57)

To evaluate the last integral, we substitute $u=(1-\sqrt{v})/(1+\sqrt{v})$,
i.e. $du=-dv/(\sqrt{v}(1+\sqrt{v})^{2})$. Moreover, let $x>-1$, and notice
that by integration by parts, the fact that $(1-y^{x})\ln(1-y)\to 0$ as $y\to
1$, and the series representation of the logarithm

$\int_{0}^{1}\frac{1-y^{x}}{1-y}dy=-\int_{0}^{1}xy^{x-1}\ln(1-y)dy=\sum_{k\geq
1}x\int_{0}^{1}\frac{y^{x+k-1}}{k}dy=\sum_{k\geq 1}\frac{x}{k(x+k)}=H_{x}.$
(58)

Thus

$\int_{0}^{1}\frac{(1-u)^{(m-1)/2}}{(1+u)^{(m+1)/2}}du=\int_{0}^{1}\frac{v^{(m-3)/4}}{2(1+\sqrt{v})}dv=\int_{0}^{1}\frac{v^{(m-3)/4}-v^{(m-1)/4}}{2(1-v)}dv=\frac{H_{(m-1)/4}-H_{(m-3)/4}}{2}.$

By plugging this expression into (57), we obtain

$\mathbb{E}\left[T_{\alpha}\right]=\frac{2}{\sqrt{7}}\Gamma\Big{(}\frac{1}{2}\Big{)}\int_{0}^{1}\frac{1}{\sqrt{1-u^{2}}}du+\frac{1}{\sqrt{7}}\sum_{m\geq
1}\frac{\Gamma(\frac{m+1}{2})}{m!}\left(\frac{8\alpha}{\sqrt{7}}\right)^{m}\left(H_{(m-1)/4}-H_{(m-3)/4}\right).$

The statement now follows from $\Gamma(1/2)=\sqrt{\pi}$ and
$\int_{0}^{1}1/\sqrt{1-u^{2}}du=\pi/2.$ ∎

Next we establish the asymptotic behaviour for $|\alpha|\to\infty$ of
$\mathbb{E}[T_{\alpha}]$. In order to do so, we do not use the explicit sum
from (55) – although we could do so – but rather exploit the integral
representation that we have encountered previously. In particular, note that
from Lemma 2.5, see also (56), we obtain

$\frac{7}{4}\mathbb{E}\left[T_{\alpha}\right]=\int_{0}^{1}\int_{0}^{\infty}\exp\Big{(}-\frac{1}{7}(1-u^{2})\lambda^{2}+\frac{8\alpha}{7}(1-u)\lambda\Big{)}d\lambda\;du.$

By substituting $u$ for $1-u$ we obtain

$\frac{7}{4}\mathbb{E}\left[T_{\alpha}\right]=\int_{0}^{1}\int_{0}^{\infty}\exp\big{(}-Q\lambda^{2}+L\lambda\big{)}d\lambda\;du,\quad\text{where}\quad
Q=\frac{2u-u^{2}}{7},\leavevmode\nobreak\ L=\frac{8\alpha u}{7},$ (59)

which is the starting point in the following two proofs. We continue with the
case $\alpha\to\infty$, where we show that $\mathbb{E}\left[T_{\alpha}\right]$
grows very fast, namely quadratic exponential in $\alpha$.

######  Corollary 6.2.

As $\alpha\rightarrow\infty$, we have

$\mathbb{E}\left[T_{\alpha}\right]=(1+o(1))\frac{\sqrt{7\pi}}{8}\cdot\frac{e^{16\alpha^{2}/7}}{\alpha^{2}}.$
(60)

###### Proof.

In order to estimate (59) we first study in more abstract terms the general
behavior of the integral of $\exp(-A\lambda^{2}+B\lambda)$ where $A,B$ are
parameters; we will be particularly interested in the case where $A$ is
positive and bounded (later we will set $A=Q=\frac{1}{7}(2u-u^{2})$ for
$u\in[0,1]$) and $B\to\infty$ (later we will set $B=L=8\alpha u/7$, and the
main contribution will come from $u$ close to 1). Note that
$-A\lambda^{2}+B\lambda=-(\sqrt{A}\lambda-{B}/{2\sqrt{A}})^{2}+{B^{2}}/{4A}$,
so by changing the variable $x=\sqrt{A}\lambda-{B}/{2\sqrt{A}}$, we obtain

$\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda=\frac{1}{\sqrt{A}}e^{B^{2}/4A}\int_{-B/2\sqrt{A}}^{\infty}e^{-x^{2}}dx.$
(61)

Since $\int_{-\infty}^{\infty}e^{-x^{2}}dx=\sqrt{\pi}$ we readily obtain the
general upper bound

$\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda\leq\sqrt{\frac{\pi}{A}}e^{B^{2}/4A},\quad
A,B>0.$ (62)

However, we will also require tighter bounds. Note that

$\int_{-\infty}^{-B/2\sqrt{A}}e^{-x^{2}}dx=\int_{-\infty}^{-B/2\sqrt{A}}\frac{|x|}{|x|}e^{-x^{2}}dx\leq\frac{2\sqrt{A}}{B}\int_{-\infty}^{-B/2\sqrt{A}}|x|e^{-x^{2}}dx=\frac{\sqrt{A}}{B}e^{-B^{2}/4A}$

so that by

$\int_{-B/2\sqrt{A}}^{\infty}e^{-x^{2}}dx=\sqrt{\pi}-\int_{-\infty}^{-B/2\sqrt{A}}e^{-x^{2}}dx$

we obtain from (61) that

$\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda=(\pi/A)^{1/2}e^{B^{2}/4A}\pm\frac{1}{B},\quad
A,B>0.$ (63)

With these preparations at hand we turn to the task of estimating (59). Let
$0<\delta<1/2$ be some (small) quantity to be specified later. We split the
integration range $u\in(0,1]$ (neglecting $u=0$) in three parts
$(0,1/2],[1/2,1-\delta]$ and $[1-\delta,1]$. Let us consider the interval
$[1-\delta,1]$ first, namely we start by estimating

$\int_{1-\delta}^{1}\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda
du.$ (64)

As we will see, the main contribution to (59) comes from (64). We will apply
(63) with

$A=Q=\frac{2u-u^{2}}{7},B=L=\frac{8\alpha u}{7},\quad\text{so
that}\quad\frac{B^{2}}{4A}=\frac{16\alpha^{2}}{7}\frac{u}{2-u}.$

Note that for this particular choice of $A$ and $B$ we obtain

$\int_{1-\delta}^{1}\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda
du=\int_{1-\delta}^{1}\left(\frac{\sqrt{7\pi}}{\sqrt{2u-u^{2}}}e^{\frac{16\alpha^{2}}{7}\frac{u}{2-u}}\pm\frac{7}{8\alpha
u}\right)du.$ (65)

With the purpose of simplifying the terms $u/(2-u)$ and $1/\sqrt{2u-u^{2}}$
observe that

$\frac{u}{2-u}-(1-2(1-u))=\frac{2(1-u)^{2}}{2-u}$ (66)

and, since $1-\delta\leq u\leq 1$, we readily see that the ratio on the right-
hand side of (66) is at most $2(1-u)^{2}\leq 2\delta^{2}$. Whence we arrive at

$0\leq\frac{u}{2-u}-(1-2(1-u))\leq 2\delta^{2}.$

Moreover, for $1-\delta\leq u\leq 1$ we also have that

$\left|\frac{1}{\sqrt{2u-u^{2}}}-1\right|\overset{}{\leq}1-u\leq\delta,$

since, obviously, $\sqrt{2u-u^{2}}\leq 1$ and moreover, by writing, say,
$u=1-y$ for $0\leq y\leq 1/2$ and simplifying, $\sqrt{2u-u^{2}}(2-u)\geq 1$.
Going back to (65) we see that, uniformly in $\delta$ as $\alpha\to\infty$

$\int_{1-\delta}^{1}\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda
du=(1+O(\delta))\int_{1-\delta}^{1}\sqrt{7\pi}e^{\frac{16\alpha^{2}}{7}(1-2(1-u)+O(\delta^{2}))}du.$

Since

$\int_{1-\delta}^{1}e^{-\frac{32\alpha^{2}}{7}(1-u)}du=\frac{7}{32\alpha^{2}}\left(1-e^{-\frac{32\alpha^{2}}{7}\delta}\right)$

we arrive at the expression

$\int_{1-\delta}^{1}\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda
du=(1+O(\delta))\sqrt{7\pi}e^{\frac{16\alpha^{2}}{7}(1+O(\delta^{2}))}\frac{7}{32\alpha^{2}}(1-e^{-32\alpha^{2}\delta/7}).$
(67)

We now choose the value of $\delta$ that will be most convenient to work with.
Fix $\delta=9\alpha^{-2}\ln\alpha$, so that $\alpha^{2}\delta\to\infty$ and
$\alpha^{2}\delta^{2}\to 0$ as $\alpha\to\infty$. Substituting this value of
$\delta$ into (67) we conclude that

$\int_{1-\delta}^{1}\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda
du\sim\frac{(7^{3}\pi)^{1/2}}{32}\alpha^{-2}e^{\frac{16\alpha^{2}}{7}},\quad\alpha\to\infty.$
(68)

Let us now turn our attention to the range $u\in(0,1/2]\cup[1/2,1-\delta]$ in
(59). For the first interval we apply (62) with
$A=Q=\frac{2u-u^{2}}{7},B=L=\frac{8\alpha u}{7}$, so that

$\frac{B^{2}}{4A}=\frac{16\alpha^{2}}{7}\frac{u}{2-u}\leq\frac{1}{3}\frac{16\alpha^{2}}{7},\quad
u>0.$

Thus, recalling the basic integral $\int
1/\sqrt{2u-u^{2}}du=\text{arcsin}(u-1)+C$ and the values
$\text{arcsin}(-1)=-\pi/2$ and $\text{arcsin}(-1/2)=-\pi/6$, we arrive (by
(62)) at the (rough) bound

$\int_{0}^{1/2}\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda
du\leq
e^{\frac{1}{3}\frac{16\alpha^{2}}{7}}\int_{0}^{1/2}\frac{\sqrt{7\pi}}{\sqrt{2u-u^{2}}}du=\frac{\sqrt{7}\pi^{3/2}}{3}e^{\frac{1}{3}\frac{16\alpha^{2}}{7}},$
(69)

which is much smaller than the right-hand side in (68). We conclude by
considering the case $u\in[1/2,1-\delta]$. We apply again (62) with
$A=Q=\frac{2u-u^{2}}{7},B=L=\frac{8\alpha u}{7}$, so that

$\frac{B^{2}}{4A}\leq(1-\delta)\frac{16\alpha^{2}}{7}\quad\text{and,
say,}\quad\frac{1}{\sqrt{A}}\leq 4.$

Thus, we obtain

$\int_{1/2}^{1-\delta}\int_{0}^{\infty}\exp\big{(}-A\lambda^{2}+B\lambda\big{)}d\lambda
du\leq
4\sqrt{\pi}\int_{1/2}^{1-\delta}e^{(1-\delta)\frac{16\alpha^{2}}{7}}du\leq
4\sqrt{\pi}e^{(1-\delta)\frac{16\alpha^{2}}{7}},$

which, by our choice of $\delta=9\alpha^{-2}\ln\alpha$, is at most
$4\sqrt{\pi}\alpha^{-9}e^{{16\alpha^{2}}/7}$. By combining this with (69) for
the case $u\in(0,1/2]$ and (68) for $u\in[1-\delta,1]$ we finally obtain, as
$\alpha\to\infty$, from (59) the claim. ∎

In contrast to the quadratic exponential behavior as $\alpha\to\infty$
established in Corollary 6.2, we show that the behavior is rather moderate
(i.e., polynomial with logarithmic corrections) when $\alpha\to-\infty$.

######  Corollary 6.3.

As $\alpha\rightarrow-\infty$, we have

$\mathbb{E}\left[T_{\alpha}\right]=(1+o(1))\frac{\ln|\alpha|}{|\alpha|}.$

###### Proof.

Let us start with two auxiliary estimates that we shall exploit. Using
$1-e^{-y}\leq y$ for $y\geq 0$ we obtain $e^{-Qx^{2}}=1\pm Qx^{2}$ for all
$x\in\mathbb{R},Q>0$. Also, $\int_{0}^{\infty}e^{-Lx}dx=1/L$ for all $L>0$ and
we obtain (for $Q,L>0$)

$\left|\int_{0}^{\infty}\exp\Big{(}-Qx^{2}-Lx\Big{)}dx-\frac{1}{L}\right|=\int_{0}^{\infty}e^{-Lx}dx-\frac{1}{L}\pm
Q\int_{0}^{\infty}x^{2}e^{-Lx}dx\leq 2QL^{-3},$ (70)

where the inequality follows from integration by parts of the second integral.
This estimate will be useful when $L$ is large. On the other hand, when $L$ is
small, we will use a different bound. Indeed, noting that $|e^{-Lx}-1|\leq Lx$
for all $Lx>0$ and that $\int_{0}^{\infty}e^{-Qx^{2}}dx=\sqrt{\pi}/2\sqrt{Q}$
and $\int_{0}^{\infty}xe^{-Qx^{2}}dx=1/2Q$ for $Q>0$, we obtain

$\left|\int_{0}^{\infty}\exp\Big{(}-Qx^{2}-Lx\Big{)}dx-\frac{\sqrt{\pi}}{2\sqrt{Q}}\right|\leq\frac{L}{2Q},\quad
Q,L>0.$ (71)

With those facts at hand we continue with the proof of the corollary. From
(59) we readily obtain

$\frac{7}{4}\mathbb{E}\left[T_{\alpha}\right]=\int_{0}^{1}\int_{0}^{\infty}\exp\big{(}-Q\lambda^{2}-L\lambda\big{)}d\lambda\;du,\quad\text{where}\quad
Q=\frac{2u-u^{2}}{7},\leavevmode\nobreak\ L=\frac{8|\alpha|u}{7}.$

We will use (71) to estimate the integral when $u$ is close to zero and (70)
otherwise. More precisely, let $0<\delta<1$. Then, by (71) together with the
fact that for any $0\leq u\leq 1$

$2LQ^{-1}=\frac{16|\alpha|u}{2u-u^{2}}\leq 16|\alpha|$

we obtain

$\displaystyle\int_{0}^{\delta}\int_{0}^{\infty}\exp\big{(}-Q\lambda^{2}-L\lambda\big{)}d\lambda\;du$
$\displaystyle=\int_{0}^{\delta}\left(\frac{\sqrt{\pi}}{2\sqrt{Q}}\pm
16|\alpha|\right)du=\frac{\sqrt{7\pi}}{2}\int_{0}^{\delta}\frac{du}{\sqrt{2u-u^{2}}}\pm
16|\alpha|\delta.$

Since $u\leq 2u-u^{2}\leq 2u$ for $0\leq u\leq\delta\leq 1$, we obtain
(uniformly in $\delta,\alpha$)

$\int_{0}^{\delta}\int_{0}^{\infty}\exp\big{(}-Q\lambda^{2}-L\lambda\big{)}d\lambda\;du=O\big{(}\sqrt{\delta}+|\alpha|\delta\big{)}.$
(72)

Moreover, by (70) and $QL^{-3}\leq|\alpha|^{-3}u^{-2}$ we obtain (again
uniformly in $\delta,\alpha$)

$\begin{split}\int_{\delta}^{1}\int_{0}^{\infty}\exp\big{(}-Q\lambda^{2}-L\lambda\big{)}d\lambda\;du&=\int_{\delta}^{1}\frac{1}{L}+O(QL^{-3})du=\frac{7\ln(1/\delta)}{8|\alpha|}+O(\delta^{-1}|\alpha|^{-3}).\end{split}$

By choosing $\delta=\alpha^{-2}$ and combining the last estimate with (72) we
obtain from (59), as $\alpha\to-\infty$,

$\frac{7}{4}\mathbb{E}\left[T_{\alpha}\right]=\frac{7\ln(1/\delta)}{8|\alpha|}+O\big{(}\sqrt{\delta}+|\alpha|\delta+\delta^{-1}/|\alpha|^{3}\big{)}\sim\frac{7}{4}\frac{\ln|\alpha|}{|\alpha|},$

and the claim follows. ∎

##  7 Proof of Theorem 1.4 – Total Number of Jumps

Recall that $M=M(n)=n/2+\alpha n^{1/2}+o(n^{1/2})$ with $\alpha\in\mathbb{R}$.
Our goal is to establish that there exists a continuous random variable
$A_{\alpha}$ such that, as $n\to\infty$,

$n^{-1}\bigg{(}\sum_{t\geq 0}U_{t}-\frac{2}{7}n\ln
n\bigg{)}\overset{d}{\longrightarrow}A_{\alpha}.$ (73)

For this purpose we fix an $\epsilon>0$ and $\delta>0$ sufficiently small and
$n$ sufficiently large so that Lemma 4.1 applies. In particular, there exists
$\chi\in\mathbb{R}$ such that, with probability at least $1-\delta$,

$U_{T_{n,M,\delta}}\sim\frac{\sqrt{n}}{\delta}\quad\text{ and }\sum_{0\leq
t\leq T_{n,M,\delta}}U_{t}=\frac{2}{7}n\ln n+\frac{4}{7}n\ln\delta+\chi
n\pm\epsilon n,$ (74)

where $T_{n,M,\delta}=\inf\\{t>0:U_{t}\leq n^{1/2}/\delta\\}$. In the
following lemma we consider all $t\geq T_{n,M,\delta}$.

######  Lemma 7.1.

Let $\delta>0$. As $n\to\infty$,

$n^{-1}\sum_{t\geq
T_{n,M,\delta}}U_{t}\overset{d}{\longrightarrow}\int_{0}^{\infty}X_{s}ds,$

where $X$ satisfies (1) and thus depends on $\delta$ through the initial
condition $X_{0}=\delta^{-1}$.

###### Proof.

We use the notation from Section 5 and consider the process of unhappy
particles after $T_{n,M,\delta}$, i.e. $U^{\prime}_{s}=U_{\lfloor
s\rfloor+T_{n,M,\delta}}$ for all $s\geq 0$. Hence,

$n^{-1}\sum_{t\geq T_{n,M,\delta}}U_{t}=n^{-1}\sum_{t\geq
0}U^{\prime}_{t}=n^{-1}\int_{0}^{\infty}U^{\prime}_{s}ds=n^{-1/2}\int_{0}^{\infty}U^{\prime}_{sn^{1/2}}ds.$
(75)

Let $S>0$. For every $m\in\mathbb{N}$, let $\pi_{m}:0=s_{0}<s_{1}<...<s_{m}=S$
be a partition of the interval $[0,S]$ such that
$\lim_{m\to\infty}\sup_{i\in\\{1,...,m\\}}|s_{i}-s_{i-1}|=0$. Recall Lemma
5.1, from which we obtain that the process
$(n^{-1/2}U^{\prime}_{sn^{1/2}})_{s\geq 0}$ converges weakly to $X$ as
$n\to\infty$ in the Skorokhod space $D([0,S],\mathbb{R})$. Since, for
each$i\in\\{1,...,m\\}$, the mapping $F(f)=\sup_{s\in[s_{i-1},s_{i}]}f(s)$,
$f\in D([0,S],\mathbb{R})$, is continuous with respect to the Skorokhod
metric, this implies that as $n\to\infty$

$n^{-1/2}\sum_{i=1}^{m}(s_{i}-s_{i-1})\sup_{s\in[s_{i-1},s_{i}]}U^{\prime}_{sn^{1/2}}\overset{d}{\longrightarrow}\sum_{i=1}^{m}(s_{i}-s_{i-1})\sup_{s\in[s_{i-1},s_{i}]}X_{s}.$

Noting that

$\int_{0}^{S}U^{\prime}_{sn^{1/2}}ds\leq\sum_{i=1}^{m}(s_{i}-s_{i-1})\sup_{s\in[s_{i-1},s_{i}]}U^{\prime}_{sn^{1/2}}$

we obtain, for all $a\geq 0$,

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(n^{-1/2}\int_{0}^{S}U^{\prime}_{sn^{1/2}}ds\leq
a\right)$
$\displaystyle\geq\lim_{n\to\infty}\mathbb{P}\left(n^{-1/2}\sum_{i=1}^{m}(s_{i}-s_{i-1})\sup_{s\in[s_{i-1},s_{i}]}U^{\prime}_{sn^{1/2}}\leq
a\right)$
$\displaystyle=\mathbb{P}_{2\alpha,7/4,1,1/\delta}\left(\sum_{i=1}^{m}(s_{i}-s_{i-1})\sup_{s\in[s_{i-1},s_{i}]}X_{s}\leq
a\right).$

Analogously, we obtain

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(n^{-1/2}\int_{0}^{S}U^{\prime}_{sn^{1/2}}ds\leq
a\right)\leq\mathbb{P}_{2\alpha,7/4,1,1/\delta}\left(\sum_{i=1}^{m}(s_{i}-s_{i-1})\inf_{s\in[s_{i-1},s_{i}]}X_{s}\leq
a\right).$

As $X$ has almost surely continuous paths, $\int_{0}^{S}X_{s}ds$ is a Riemann
integral for almost every realisation and hence

$\lim_{m\to\infty}\sum_{i=1}^{m}(s_{i}-s_{i-1})\inf_{s\in[s_{i-1},s_{i}]}X_{s}=\int_{0}^{S}X_{s}ds=\lim_{m\to\infty}\sum_{i=1}^{m}(s_{i}-s_{i-1})\sup_{s\in[s_{i-1},s_{i}]}X_{s}.$

This yields the equality

$\lim_{n\to\infty}\mathbb{P}\left(n^{-1/2}\int_{0}^{S}U^{\prime}_{sn^{1/2}}ds\leq
a\right)=\mathbb{P}_{2\alpha,7/4,1,1/\delta}\left(\int_{0}^{S}X_{s}ds\leq
a\right),\quad a\geq 0.$

As $U^{\prime}\geq 0$, we readily obtain, for all $a\geq 0$,

$\begin{split}\lim_{n\to\infty}\mathbb{P}\left(n^{-1/2}\int_{0}^{\infty}U^{\prime}_{sn^{1/2}}ds\leq
a\right)&\leq\lim_{n\to\infty}\mathbb{P}\left(n^{-1/2}\int_{0}^{S}U^{\prime}_{sn^{1/2}}ds\leq
a\right)\\\ &=\mathbb{P}_{2\alpha,7/4,1,1/\delta}\left(\int_{0}^{S}X_{s}ds\leq
a\right).\end{split}$ (76)

Additionally, since $U^{\prime}_{s}=0$ for all $s\geq T^{\prime}_{n,M,\delta}$
we estimate that

$\mathbb{P}\left(n^{-1/2}\int_{0}^{\infty}U^{\prime}_{sn^{1/2}}ds\geq
a\right)\leq\mathbb{P}\left(n^{-1/2}\int_{0}^{S}U^{\prime}_{sn^{1/2}}ds\geq
a\right)+\mathbb{P}\left(n^{-1/2}T^{\prime}_{n,M,\delta}>S\right),\quad a\geq
0,$

from which we readily deduce using Lemma 5.2 that, for all $a\geq 0$,

$\lim_{n\to\infty}\mathbb{P}\left(n^{-1/2}\int_{0}^{\infty}U^{\prime}_{sn^{1/2}}ds\geq
a\right)\leq\mathbb{P}_{2\alpha,7/4,1,1/\delta}\left(\int_{0}^{S}X_{s}ds\geq
a\right)+\mathbb{P}_{2\alpha,7/4,1,1/\delta}\left(T>S\right).$

The claim is established by letting $S\to\infty$,(76) and (75). ∎

Recall Lemma 2.7, where we established that the integral
$\int_{0}^{\infty}X_{s}ds$ from the previous statement equals the hitting time
of zero of an Ornstein-Uhlenbeck process with suitable parameters depending on
$\alpha\in\mathbb{R}$ and $\delta>0$. As the distribution of such a stopping
time is well-known, see Lemma 2.8, this connection is the key element in the
proof of the convergence in distribution of
$\int_{0}^{\infty}X_{s}ds+\frac{4}{7}\ln\delta$ as $\delta\to 0$, which is
stated below.

######  Lemma 7.2.

For all $\alpha\in\mathbb{R}$ there exists a continuous random variable
$\tilde{A}_{\alpha}$ such that as $\delta\to 0$

$\int_{0}^{\infty}X_{s}ds+\frac{4}{7}\ln\delta\overset{d}{\longrightarrow}\tilde{A}_{\alpha},$

where $X$ satisfies (1) and thus depends on $\delta$ through the initial
condition $X_{0}=\delta^{-1}$. In particular, for $\alpha=0$,

$\mathbb{P}(\tilde{A}_{0}\geq
a)=\text{\emph{erf}}\left(\frac{\sqrt{7}}{2}e^{-7a/4}\right),\quad
a\in\mathbb{R}.$

###### Proof.

Let us begin with the case $\alpha=0$. Abbreviate
$\mathbb{P}_{0,7/4,1,1/\delta}$ with $\mathbb{P}_{\delta}$. From Lemmas 2.7
and 2.8 we obtain for all $a\geq 0$

$\displaystyle\mathbb{P}_{\delta}$
$\displaystyle\left(\int_{0}^{\infty}X_{s}ds\geq
a\right)=\left(\frac{7}{2}\right)^{3/2}\frac{\delta^{-1}}{\sqrt{2\pi}}\int_{a}^{\infty}\left(e^{7s/2}-1\right)^{-3/2}e^{7s/2}\exp\left(-\frac{7\delta^{-2}}{4(e^{7s/2}-1)}\right)ds.$

The substitution $u=\sqrt{7}\delta^{-1}(e^{7s/2}-1)^{-1/2}/2$ leads to

$\displaystyle\mathbb{P}_{\delta}\left(\int_{0}^{\infty}X_{s}ds\geq a\right)$
$\displaystyle=\frac{2}{\sqrt{\pi}}\int_{0}^{\sqrt{7}\delta^{-1}(e^{7a/2}-1)^{-1/2}/2}\exp(-u^{2})du=\text{erf}\left(\frac{\sqrt{7}\delta^{-1}}{2\sqrt{e^{7a/2}-1}}\right).$
(77)

As for all $a\in\mathbb{R}$ we have $a-\frac{4}{7}\ln\delta\geq 0$ when
$\delta>0$ is sufficiently small, we conclude that for all $a\in\mathbb{R}$

$\displaystyle\lim_{\delta\to
0}\mathbb{P}_{\delta}\left(\int_{0}^{\infty}X_{s}ds+\frac{4}{7}\ln\delta\geq
a\right)$ $\displaystyle=\lim_{\delta\to
0}\text{erf}\left(\frac{\sqrt{7}\delta^{-1}}{2\sqrt{\exp(7a/2-2\ln\delta)-1}}\right)=\text{erf}\left(\frac{\sqrt{7}}{2}e^{-7a/4}\right).$

We now turn to the general case with $\alpha\in\mathbb{R}$, where we
abbreviate $\mathbb{P}_{2\alpha,7/4,1,1/\delta}$ with
$\mathbb{P}_{\alpha,\delta}$. Furthermore, let $R$ be an Ornstein-Uhlenbeck
process that under $\mathbb{P}_{\alpha,\delta}$ satisfies the SDE

$dR_{s}=\left(2\alpha-\frac{7}{4}R_{s}\right)ds+dB_{s},\;s>0,\quad\text{with}\quad
R_{0}=\delta^{-1}.$

Then, the shifted process $\tilde{R}=R-8\alpha/7$ is also an O-U process under
$\mathbb{P}_{\alpha,\delta}$, since

$d\tilde{R}_{s}=-\frac{7}{4}\tilde{R}_{s}ds+dB_{s},\;s>0,\quad\text{with}\quad\tilde{R}_{0}=\delta^{-1}-8\alpha/7.$

If we define the stopping time

$\tau_{x}=\inf\\{s\geq 0:\tilde{R}_{s}=-8x/7\\},\quad x\in\mathbb{R},$

then $\tau_{\alpha}=T(R)=\inf\\{s\geq 0:R_{s}=0\\}$ under
$\mathbb{P}_{\alpha,\delta}$. So, Lemma 2.7 implies that
$\int_{0}^{\infty}X_{s}ds$ and $\tau_{\alpha}$ have the same distribution
under $\mathbb{P}_{\alpha,\delta}$. Further, we obtain analogously to (77)
that

$\mathbb{P}_{\alpha,\delta}\left(\tau_{0}+\frac{4}{7}\ln\delta\geq
a\right)=\text{erf}\left(\frac{\sqrt{7}\delta^{-1}-8\alpha/\sqrt{7}}{2\sqrt{\exp(7a/2-2\ln\delta)-1}}\right),\quad
a\in\mathbb{R}.$

Hence, for all $a\in\mathbb{R}$

$\displaystyle\mathbb{P}_{\alpha,\delta}\left(\int_{0}^{\infty}X_{s}ds+\frac{4}{7}\ln\delta\geq
a\right)$
$\displaystyle=\mathbb{E}_{\alpha,\delta}\left[\mathbb{P}_{\alpha,\delta}\left(\tau_{0}+\frac{4}{7}\ln\delta\geq
a-(\tau_{\alpha}-\tau_{0})\mid\tau_{\alpha}-\tau_{0}\right)\right]$
$\displaystyle=\mathbb{E}_{\alpha,\delta}\left[\text{erf}\left(\frac{\sqrt{7}\delta^{-1}-8\alpha/\sqrt{7}}{2\sqrt{\exp(7(a-(\tau_{\alpha}-\tau_{0}))/2-2\ln\delta)-1}}\right)\right].$

Note that $\tau_{0}-\tau_{\alpha}$ is independent of $\delta$ for $\delta$
small enough, as for $\alpha\leq 0$, the difference $\tau_{0}-\tau_{\alpha}$
represents the time the process $\tilde{R}$ started in $-8\alpha/7$ needs to
hit $0$. For $\alpha\geq 0$, this observation follows by a very similar
argument for $\tau_{\alpha}-\tau_{0}$. Together with the dominated convergence
theorem, we therefore obtain

$\displaystyle\lim_{\delta\to
0}\mathbb{E}_{\alpha,\delta}\left[\text{erf}\left(\frac{\sqrt{7}\delta^{-1}-8\alpha/\sqrt{7}}{2\sqrt{\exp(7(a-(\tau_{\alpha}-\tau_{0}))/2-2\ln\delta)-1}}\right)\right]$
$\displaystyle=$ $\displaystyle\lim_{\delta\to
0}\mathbb{E}_{\alpha,0}\left[\text{erf}\left(\frac{\sqrt{7}\delta^{-1}-8\alpha/\sqrt{7}}{2\sqrt{\exp(7(a-(\tau_{\alpha}-\tau_{0}))/2-2\ln\delta)-1}}\right)\right]=\mathbb{E}_{\alpha,0}\left[\text{erf}\left(\frac{\sqrt{7}}{2e^{7(a-(\tau_{\alpha}-\tau_{0}))/4}}\right)\right],$

from which the claim readily follows. ∎

We are now in a position to complete the proof of Theorem 1.4. Since (74)
occurs with probability at least $1-\delta$,

$\displaystyle\mathbb{P}\Bigg{(}n^{-1}\sum_{t\geq 0}U_{t}-\frac{2}{7}\ln n\leq
a\Bigg{)}\leq\mathbb{P}\Bigg{(}n^{-1}\sum_{t>T_{n,M,\delta}}U_{t}+\frac{4}{7}\ln\delta+\chi-\epsilon\leq
a\Bigg{)}+\delta,\quad a\in\mathbb{R}.$

Subsequently, we again abbreviate $\mathbb{P}_{2\alpha,7/4,1,1/\delta}$ with
$\mathbb{P}_{\alpha,\delta}$. Since
$\lim_{n\to\infty}n^{-1}U_{T_{n,M,\delta}}=0$, it follows from Lemma 7.1 that

$\lim_{n\to\infty}\mathbb{P}\Bigg{(}n^{-1}\sum_{t>T_{n,M,\delta}}U_{t}+\frac{4}{7}\ln\delta+\chi-\epsilon\leq
a\Bigg{)}=\mathbb{P}_{\alpha,\delta}\left(\int_{0}^{\infty}X_{s}ds+\frac{4}{7}\ln\delta+\chi-\epsilon\leq
a\right),\quad a\in\mathbb{R}.$

Letting $\delta\to 0$, Lemma 7.2 thus implies that

$\lim_{n\to\infty}\mathbb{P}\Bigg{(}n^{-1}\sum_{t\geq 0}U_{t}-\frac{2}{7}\ln
n\leq
a\Bigg{)}\leq\mathbb{P}_{\alpha,0}\left(\tilde{A}_{\alpha}+\chi-\epsilon\leq
a\right),\quad a\in\mathbb{R}.$

Using a very similar argument, we also estimate that

$\lim_{n\to\infty}\mathbb{P}\Bigg{(}n^{-1}\sum_{t\geq 0}U_{t}-\frac{2}{7}\ln
n\geq
a\Bigg{)}\leq\mathbb{P}_{\alpha,0}\left(\tilde{A}_{\alpha}+\chi+\epsilon\geq
a\right),\quad a\in\mathbb{R}.$

Therefore, using continuity of $\tilde{A}_{\alpha}$ and letting $\epsilon\to
0$, (73) and, by employing again Lemma 7.2 for the case $\alpha=0$, the
statement of the theorem readily follows.

## References

  * [1] L. Alili, P. Patie, and J. L. Pedersen.  Representations of the first hitting time density of an ornstein-uhlenbeck process.  Stochastic Models, 21(4):967–980, 2005.
  * [2] S. Boucheron, G. Lugosi, and O. Bousquet.  Concentration inequalities.  In Advanced Lectures on Machine Learning, pages 208–240. Springer, 2004.
  * [3] K. Bringmann, F. Kuhn, K. Panagiotou, U. Peter, and H. Thomas.  Internal DLA: Efficient simulation of a physical growth model.  In Automata, Languages, and Programming, pages 247–258, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  * [4] C. Cooper, A. McDowell, T. Radzik, N. Rivera, and T. Shiraga.  Dispersion processes.  Random Structures Algorithms, 53(4):561–585, 2018.
  * [5] U. De Ambroggio, T. Makai, and K. Panagiotou.  Dispersion on the complete graph, 2023.  arXiv:2306.02474. An extended abstract appeared in the _Proceedings of EUROCOMB ’23_.
  * [6] N. G. de Bruijn.  Asymptotic Methods in Analysis.  Bibliotheca mathematica. Dover Publications, 1981.
  * [7] P. Diaconis and W. Fulton.  A growth model, a game, an algebra, Lagrange inversion, and characteristic classes.  Rend. Sem. Mat. Univ. Politec. Torino, 49(1):95–119, 1991.
  * [8] R. Durrett.  Stochastic calculus – a practical introduction.  Probability and Stochastics Series. CRC Press, Boca Raton, FL, 1996.
  * [9] C. Foucart, P. Li, and X. Zhou.  On the entrance at infinity of Feller processes with no negative jumps.  Statist. Probab. Lett., 165:108859, 9, 2020.
  * [10] A. Frieze and W. Pegden.  A note on dispersing particles on a line.  Random Structures Algorithms, 53(4):586–591, 2018.
  * [11] Z. Fu and Z. Li.  Stochastic equations of non-negative processes with jumps.  Stochastic Processes and their Applications, 120(3):306–330, 2010\.
  * [12] J. T. Kent.  Eigenvalue expansions for diffusion hitting times.  Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 52(3):309–319, 1980.