# Many-server asymptotics for Join-the-Shortest Queue in the Super-Halfin-
Whitt Scaling Window

Zhisheng Zhao1 Debankur Mukherjee2 Ruoyu Wu3

###### Abstract

The Join-the-Shortest Queue (JSQ) is a classical benchmark for the performance
of parallel-server queueing systems due to its strong optimality properties.
Recently, there has been a significant progress in understanding its large-
system asymptotic behavior since the work of Eschenfeldt and Gamarnik (Math.
Oper. Res. 43 (2018) 867-886). In this paper, we analyze the JSQ policy in the
_super-Halfin-Whitt_ scaling window when load per server $\lambda_{N}$ scales
with the system size $N$ as
$\lim_{N\rightarrow\infty}N^{\alpha}(1-\lambda_{N})=\beta$ for
$\alpha\in(1/2,1)$ and $\beta>0$. We establish that the centered and scaled
total queue-length process converges to a certain Bessel process with negative
drift and the associated (centered and scaled) steady-state total queue
length, indexed by $N$, converges to a $\mathrm{Gamma}(2,\beta)$ distribution.
The limit laws are universal in the sense that they do not depend on the value
of $\alpha$, and exhibit fundamentally different behavior from both the
Halfin-Whitt regime ($\alpha=1/2$) and the Non-degenerate Slowdown (NDS)
regime ($\alpha=1$).

††1Georgia Institute of Technology, _Email:_<EMAIL_ADDRESS>of North Carolina at Chapel Hill, _Email:_<EMAIL_ADDRESS>Institute of Technology, _Email:_<EMAIL_ADDRESS>_Keywords and phrases_. Join-the-Shortest Queue, diffusion limit, steady state
analysis, regenerative process †† _Acknowledgements._ The work was partially
supported by the NSF grant CIF-2113027.

##  1 Introduction

###  1.1 Background and motivation.

A canonical setup for parallel-server systems consists of $N$ identical
servers, each with a dedicated queue. Tasks arrive into the system as a
Poisson process of rate $\lambda(N)$ and must be assigned to one of the queues
instantaneously upon arrival, where they wait until executed. Tasks are
assumed to have unit-mean exponentially distributed service times, and the
service discipline at each server is oblivious to the actual service
requirements (viz., FCFS). The Join-the-Shortest Queue (JSQ) policy for many-
server systems has been a classical quantity of interest and has served as a
benchmark for the quality of performance of task assignment policies. In the
above setup, JSQ exhibits several strong optimality properties among the class
of all non-anticipative task-assignment policies [12, 40]. In particular, it
minimizes the joint queue length vector (in a stochastic majorization sense)
and stochastically minimizes the total number of tasks in the system, and
hence the mean overall delay.

While the exact analysis of the JSQ policy is intractable, the research
community has made significant progress in understanding its behavior in
various asymptotic regimes, primarily when the system is close to the boundary
of its capacity region. The capacity region of the JSQ policy for the above
homogeneous system of $N$ servers consists of the arrival rates
$\lambda(N)<N$. In the _conventional heavy-traffic regime_ , for a _fixed_
$N$, the behavior of the queue lengths is characterized as $\lambda(N)\to N$.
We note that this is not an asymptotic in $N$ since $N$ is fixed. Instead, in
this regime, the system behavior is analyzed as the total arrival rate
approaches $N$. There is a huge body of literature on this heavy-traffic
analysis, which we do not attempt to review here. Interested readers may look
at [15, 14, 34, 41] and the references therein for some of the related works.
More recently, motivated by the applications in large-scale service systems,
such as data centers and cloud networks, there has been a growing interest in
understanding the behavior the JSQ policy as the number of servers
$N\to\infty$. In that case, if the load per server, defined as $\lambda(N)/N$,
is fixed, that is, if $\lambda(N)=\lambda N$ for some fixed $\lambda\in(0,1)$,
then asymptotically, the fluid-scaled steady-state occupancy process becomes
degenerate. Specifically, as $N\to\infty$, a $\lambda$ proportion of servers
have queue length 1 and the number of servers with queue length 2 or more
vanishes [32]. The behavior becomes intricate when $\lambda(N)$ scales with
$N$ in a way that $\lambda(N)/N\to 1$ as $N\to\infty$. This is known as the
_many-server heavy-traffic regime_. In a breakthrough work, Eschenfeldt and
Gamarnik [13] characterized the transient limit of the occupancy process in
the so-called Halfin-Whitt regime when $\lambda(N)=N-\beta\sqrt{N}$ for some
$\beta>0$. Since then, over the last few years, several works have been
published investigating the many-server heavy-traffic limit of the JSQ policy,
more of which we mention in Section 1.2 below.

The situation becomes more challenging when the system load is heavier than
the Halfin-Whitt regime, that is, when
$N-\lambda(N)=O(N^{\frac{1}{2}-\varepsilon})$ for some
$\varepsilon\in(0,0.5)$. This is known as the _super-Halfin-Whitt regime_ ,
which was first introduced by Liu and Ying [26]. Note that due to ergodicity
of the system and the fact that the service times are exponentially
distributed with mean 1, the expected steady-state number of busy servers
equals $\lambda(N)$, and thus, the idleness process (the process denoting the
total number of idle servers) scales as $N^{\frac{1}{2}-\varepsilon}$.
However, comparing the JSQ system with the corresponding M/M/$N$ system (with
$N$ parallel servers and a centralized queue for waiting tasks), one expects
that the total number of waiting tasks centered at $N$, scales as
$N^{\frac{1}{2}+\varepsilon}$. In other words, the idle-server process
vanishes on the scale of the centered total number of tasks. The basic
difference between the JSQ (parallel server) system and the M/M/$N$
(centralized queue) system lies in the non-idling nature of the latter. In the
JSQ dynamics, there can be idle servers in the system, while having waiting
tasks. The above observation poses an important question: _does the total
number of tasks exhibit same asymptotic behavior as the M/M/ $N$ system in the
super-Halfin-Whitt regime? If not, then what is the cost of maintaining
parallel queues instead of a centralized one?_ In this paper, we characterize
the many-server asymptotics of the JSQ policy in the super-Halfin-Whitt
regime, and answer the above questions. We discover that even though the idle-
server process is negligible in magnitude on the $N^{\frac{1}{2}+\varepsilon}$
scale, it evolves on a faster time scale and its local time accumulated at the
reflection boundary provides a non-trivial positive drift to the total number
of tasks. For this reason, asymptotically, the centered and scaled total
number of tasks in steady state is distributed as the sum of two independent
exponential random variables for the JSQ policy, as opposed to a single
exponential random variable in the M/M/$N$ case. Moreover, both the steady
state and process-level limiting behavior are universal in the sense that they
do not depend on $\varepsilon\in(0,0.5)$ and are fundamentally different from
what have been observed in the Halfin-Whitt regime ($\varepsilon=0$) and the
Non-degenerate Slowdown (NDS) regime ($\varepsilon=0.5$).

###  1.2 Literature review.

The literature on the performance analysis of the JSQ policy can be broadly
categorized into two groups: (1) _Many-server heavy-traffic regime:_ When the
number of servers, $N$, tends to infinity and the relative load per server for
the $N$-th system, $\lambda(N)/N$, tends to 1 as $N\to\infty$. (2)
_Conventional heavy-traffic regime:_ When the number of servers is fixed and
the load per server $\lambda$ tends to 1. Although the focus of the current
work lies in the former regime, we will discuss that the two regimes share
some commonality in performance if $\lambda(N)/N$, approaches 1 at a
sufficiently fast rate.

In the subcritical regime, when $\lambda(N)=\lambda N$ for some
$\lambda\in(0,1)$, Mukherjee et al. [32] characterized the transient and
stationary behavior of the fluid limit for the JSQ policy using the time-scale
separation technique by Hunt and Kurtz [18]. The study of the many-server
heavy traffic regime gained momentum since the seminal work by Eschenfeldt and
Gamarnik [13]. Here, the authors considered the limit of the system occupancy
process $(Q_{1}^{(N)}(t),Q_{2}^{(N)}(t),\ldots)$, where $Q_{i}^{(N)}(t)$ is
the number of servers with queue length $i$ or larger in the $N$-th system at
time $t$. Specifically, if $Q_{3}^{(N)}(0)=0$, then uniformly on any finite
time interval, $((N-Q_{1}^{(N)})/\sqrt{N},Q_{2}^{(N)}/\sqrt{N})$ converges
weakly to a certain two-dimensional reflected Ornstein-Uhlenbeck (OU) process
with singular noise. This convergence has been extended to steady state by
Braverman [7] using a sophisticated generator expansion framework via the
Stein’s method, enabling the interchange of $N\to\infty$ and $t\to\infty$
limits. Subsequently, the tail and bulk behavior of the stationary
distribution of the limiting diffusion have been studied by Banerjee and
Mukherjee [3, 4], although an explicit characterization of the stationary
distribution is yet unknown. Convergence to the above OU process has been
extended for a class of power-of-$d$ policies in [32] and for the Join-Idle-
Queue policy in [31].

In the sub-Halfin-Whitt regime, i.e., when
$N-\lambda(N)=O(N^{\frac{1}{2}+\varepsilon})$ for some
$\varepsilon\in(0,0.5)$, Liu and Ying [25] considered a general class of
policies, including the JSQ policy, under the assumption that each server has
a buffer size $b=o(\log N)$. They showed that in the steady state, the
expected waiting time per job is $O\left(\frac{\log N}{\sqrt{N}}\right)$. As
observed in [25], the results in [13, 7, 25] imply that a phase transition
occurs at $\varepsilon=0$ where the limit of the quantity
$\log\big{[}\mathbb{E}(\sum_{i=2}^{\infty}Q_{i}^{(N)})\big{]}/\log N$ jumps
from 0 for $\varepsilon<0$, to $1/2$ for $\varepsilon=0$. Under the finite
buffer assumption, Liu and Ying [26] further considered the JSQ policy in the
super-Halfin-Whitt regime, i.e., when
$N-\lambda(N)=O(N^{\frac{1}{2}-\varepsilon})$ for some
$\varepsilon\in(0,0.5)$. Here, the authors showed that in steady state, the
expected number of servers with queue length 2 is
$O(N^{\frac{1}{2}+\varepsilon}\log N)$ and with queue length 3 or larger is
$o(1)$ and conjectured that the true order of
$\mathbb{E}\big{(}Q_{2}^{(N)}\big{)}$ should be $N^{\frac{1}{2}+\varepsilon}$.
Our results confirm this conjecture as a corollary, without having any
restriction on the buffer capacity. To the best of our knowledge, the terms
‘sub/super-Halfin-Whitt’ regimes were first introduced in [25] and [26]
respectively. Since then the community adopted these terminologies in various
papers (including ours) to describe the scaling of the load per server
relative to the popular Halfin-Whitt regime.

When $N-\lambda(N)=O(1)$, the system load is heavier than the super-Halfin-
Whitt regime. This is known as the Non-Degenerate Slowdown (NDS) regime. This
regime was formally introduced by Atar [2]. However, as mentioned in [2],
earlier than that the regime was also considered by Mandelbaum [28],
Mandelbaum and Shaikhet, Whitt [38], and Gurvich [17], where the authors did
asymptotic analysis of the M/M/$N$ system motivated by call centers. Atar [2]
discussed related convergence under non-degenerate slowdown while analyzing
heterogeneous many-server systems. Later, this regime was also considered by
Maglaras et al. [27] from a revenue maximization perspective. Gupta and Walton
[16] analyzed the transient limit of the JSQ policy in this scaling regime and
proved that the total queue-length process, scaled by $N$, has a diffusion
limit which is similar to Bessel process with a constant drift. The
interchange of $t\to\infty$ and $N\to\infty$ limits in the NDS regime requires
establishing the tightness of the sequence of scaled total queue-lengths in
steady state indexed by $N$, which is not established in [16]. However, the
results in [16], in combination with the results in the current paper that
analyze the case $N-\lambda(N)=O(N^{\frac{1}{2}-\varepsilon})$ for
$\varepsilon\in(0,0.5)$, hint at a second phase transition at
$\varepsilon=0.5$, where for all $i\geq 3$, the value of $Q_{i}^{(N)}$ in
steady state jumps from 0 (for $\varepsilon<0.5$) to $O(N)$ (for
$\varepsilon=0.5$). In fact, if we pretend that the interchange of limits
holds for the NDS regime, then the steady-state maximum queue length
distribution has an exponential tail [16, Theorem 1], whereas for
$\varepsilon<0.5$, its value is 2 with probability tending to 1 as
$N\to\infty$.

Recently, Hurtado-Lange and Maguluri [19, 20] considered a class of power-
of-$d$ policies in the super-slowdown regime, where
$N-\lambda(N)=O(N^{1-\alpha})$ for some $\alpha>1$ and established state-space
collapse results. In this regime, the average queue length at each server
scales as $N^{\alpha-1}$, which grows with $N$. For the JSQ policy, the
results in [19, 20] imply the total queue length in steady state, scaled by
$N^{\alpha}$, converges in distribution to an exponential random variable with
mean 1 as $N\to\infty$, when $\alpha>2$. To the best of our knowledge, this is
the first heavy-traffic scaling window where the conventional heavy-traffic
behavior coincides with the many-server heavy-traffic. For a general many-
server heavy-traffic regime ($\lambda(N)/N\rightarrow 1$), Budhiraja et al.
[10] established a large deviation principle for the occupancy process which
states that for large $N$ and $T$, starting from the state $Q^{(N)}_{1}(0)=N$
and $Q^{(N)}_{j}(0)=0$ for all $j\geq 2$, $\mathbb{P}(\sup_{0\leq t\leq
T}Q^{(N)}_{i}(t)\geq 1)\approx\exp(-\frac{N(i-2)^{2}}{4T})$ for $i\geq 3$. The
works in various regimes mentioned above, have been summarized in Table 1,
which is an expanded version of the one presented in [19] (associated
notations are described in Section 1.4). Also, see [37] for a recent survey on
load balancing algorithms and their performance in various asymptotic regimes.

Value of $\alpha$ |  Regime |  Asymptotic behavior |  References
---|---|---|---
$0$ |  Meanfield |  $Q_{1}^{(N)}=N\lambda_{N}\pm\Theta_{\scriptscriptstyle\mathbb{P}}(\sqrt{N\lambda_{N}}),$ $Q_{i}^{(N)}=o_{\scriptscriptstyle\mathbb{P}}(1)$ for $i\geq 2$ |  [32]
$(0,\frac{1}{2})$ |  Sub-Halfin-Whitt |  $\sum_{i=1}^{b}Q_{i}^{(N)}=N\lambda_{N}+O_{\scriptscriptstyle\mathbb{P}}(\sqrt{N}\log N)$ |  [25]
$\frac{1}{2}$ |  Halfin-Whitt |  $Q_{1}^{(N)}=N-\Theta_{\scriptscriptstyle\mathbb{P}}(\sqrt{N}),$ $Q_{2}^{(N)}=\Theta(\sqrt{N})$, $Q_{i}^{(N)}=o_{\scriptscriptstyle\mathbb{P}}(1)$ for $i\geq 3$ |  [7, 13, 3, 4]
$(\frac{1}{2},1)$ |  Super-Halfin-Whitt |  $Q_{1}^{(N)}=N-\Theta(N^{1-\alpha}),$ $Q_{2}^{(N)}=\Theta_{\scriptscriptstyle\mathbb{P}}(N^{\alpha})$, $Q_{i}^{(N)}=o_{\scriptscriptstyle\mathbb{P}}(1)$ for $i\geq 3$ |  [26], current paper
$1$ |  Non-Degenerate Slowdown (NDS) |  $Q_{i}=\Theta_{\scriptscriptstyle\mathbb{P}}(N)$ for all $i\geq 1$ |  [16]
$(1,\infty)$ |  Super Slowdown |  Unknown for $\alpha\in(1,2]$. For $\alpha>2$, $\sum_{i=1}^{\infty}Q_{i}^{(N)}=\Theta_{\scriptscriptstyle\mathbb{P}}\big{(}N^{\alpha}\big{)}$ |  [19, 20]
Table 1: Analysis of JSQ in various regimes: Load per server is
$\lambda_{N}=1-\frac{\beta}{N^{\alpha}}$ with $\beta\in(0,1)$ for $\alpha=0$
and $\beta>0$ for $\alpha>0$. The random variables in the third column are
steady state random variables. $b\in[1,\infty)$ denotes the buffer size, when
it is assumed to be finite.

###  1.3 Our contributions.

In this paper, we obtain the diffusion limit for the centered and scaled total
number of tasks in the system $S^{(N)}(t)=\sum_{i=1}^{\infty}Q_{i}^{(N)}(t)$
under the super-Halfin-Whitt regime and characterize the limit of its
stationary distribution as $N\rightarrow\infty$. Specifically, we assume that
the total arrival rate is $\lambda(N)=N-\beta N^{\frac{1}{2}-\varepsilon}$ for
$\varepsilon\in(0,0.5)$ and the service times are exponentially distributed
with mean 1. Our main contributions are two-fold:

#### (a) Process-level convergence.

In Theorem 5.1, we show that
$X^{(N)}(t)=N^{-(\frac{1}{2}+\varepsilon)}(S^{(N)}(N^{2\varepsilon}t)-N)$
converges to a certain Bessel process with negative drift, uniformly on
compact intervals. Since the difference between the total arrival rate and the
maximum departure rate is $O\big{(}N^{\frac{1}{2}-\varepsilon}\big{)}$ and
$S^{(N)}(t)$ is scaled by $N^{\frac{1}{2}+\varepsilon}$, we need the time-
scaling of $N^{2\varepsilon}$ to obtain the process-level convergence. From a
high-level perspective, we follow the same broad approach used in [16] to
prove the transient limit result. However, our technique differs significantly
in several places as some of the estimates in [16] only apply for
$\varepsilon$ values close to $0.5$, but we need estimates that uniformly
apply for $\varepsilon\in(0,0.5)$ (for example, the proof of Lemma 6.5
requires the estimate (E.25)). The proof also involves some characteristics of
pre-limit systems in the super-Halfin-Whitt regime (for example, with certain
initial state, for any $0<t<\infty$, $\sup_{0\leq s\leq t}Q^{(N)}_{2}(s)$ will
be less than $N$ with probability tending to 1 as $N\rightarrow\infty$, which
is very different from the scenario in [16]).

The key challenge in establishing the diffusion limit is to obtain precise
asymptotics of the following integral of the idleness process $I^{(N)}(\cdot)$
(which equals $N-Q_{1}^{(N)}(\cdot)$):
$N^{-(\frac{1}{2}+\varepsilon)}\int_{0}^{N^{2\varepsilon}t}I^{(N)}(s)ds$,
uniformly for $t$ in an appropriate (random) compact interval. As it turns
out, starting from suitable states, the process $I^{(N)}$ is negligible in
magnitude, on the scale $N^{\frac{1}{2}+\varepsilon}$ (Lemma 5.2). However,
the above integral is not negligible. In fact, we show that it is
asymptotically close to $\int_{0}^{t}\frac{1}{X^{(N)}(s)}ds$ (Proposition
5.6). We note that for a fixed $N$, $X^{(N)}(s)$ can hit 0, in which case,
$\frac{1}{X^{(N)}(s)}$ will be undefined. However, under some assumptions on
the initial state $X^{(N)}(0)$, it can be shown that for any $0<t<\infty$,
$X^{(N)}(s)$ will not hit 0 in the interval $[0,t]$ with probability tending
to 1 as $N\rightarrow\infty$. Thus, without loss of generality, we can take
$\frac{1}{X^{(N)}(s)}$ to be zero if $X^{(N)}(s)=0$. The analysis of the
aforementioned integral relies on the fact that $I^{(N)}(t)$ evolves on a
faster time scale compared to $X^{(N)}$ and achieves a local stationarity for
any fixed value of $X^{(N)}$. The (local) steady-state expectation of
$I^{(N)}(s)$ is approximately $\frac{1}{X^{(N)}(s)}$. Other parts of the
evolution equation of the limiting diffusion in Theorem 5.1 are obtained by
standard martingale decomposition and their convergence. We then show that
this limiting process is ergodic and has $\mathrm{Gamma}(2,\beta)$ as the
unique stationary distribution (Proposition 2.2).

#### (b) Tightness of the sequence of diffusion-scaled pre-limit stationary
distributions.

The next major challenge, proving the interchange of $t\to\infty$ and
$N\to\infty$ limits, requires establishing the tightness of the sequence of
steady-state random variables
$\\{X^{(N)}(\infty),N^{-\frac{1}{2}+\varepsilon}I^{(N)}(\infty),N^{-\frac{1}{2}-\varepsilon}Q^{(N)}_{2}(\infty)\\}_{N=1}^{\infty}$
as well as showing $\sum_{i=3}^{\infty}Q^{(N)}_{3}(\infty)\xrightarrow{P}0$ as
$N\rightarrow\infty$. This is provided by Theorem 2.4. In fact, Theorem 2.4
tells us much more about the prelimit stationary distribution than tightness.
We use the theory of regenerative processes to obtain tail probability bounds
on $X^{(N)}(\infty)$ for all large but fixed $N$. More precisely, we identify
renewal times along the path of the Markov process
$(I^{(N)}(\cdot),\\{Q^{(N)}_{i}(\cdot)\\}_{i\geq 2})$ and use them to obtain a
representation (2.7) of the stationary measure of the process. Tail behavior
of $X^{(N)}(\infty)$ is then studied by carefully analyzing these renewal
times and fluctuations of the process between these times. This renewal
representation also gives the other tightness and convergence results stated
above.

Two key technical steps in the renewal time analysis are to obtain sharp
asymptotics for the following: (i)  _Down-crossing estimates_ : Tail-
probability bounds on the time $Q_{2}^{(N)}$ takes to hit
$BN^{\frac{1}{2}+\varepsilon}$ starting from $2BN^{\frac{1}{2}+\varepsilon}$
(Proposition 3.4), where $B$ is a large fixed constant that does not depend on
$N$. (ii)  _Up-crossing estimates_ : Tail-probability bounds on the time
$Q_{2}^{(N)}$ takes to hit $2BN^{\frac{1}{2}+\varepsilon}$ starting from
$BN^{\frac{1}{2}+\varepsilon}$ (Proposition 3.6).

Analyzing the tail behavior of $X^{(N)}(\infty)$ for fixed large $N$ requires
very different techniques than ones required to prove the process level
convergence. First, _there is no ‘state space collapse’ in the pre-limit_ , in
the sense that one cannot directly relate the idleness process
$I^{(N)}(\cdot)$ to $X^{(N)}(\cdot)$ as in Proposition 5.6. Therefore, we take
an excursion-theoretic approach where one performs a piece-wise analysis of
excursions of the joint process
$(I^{(N)}(\cdot),\\{Q^{(N)}_{i}(\cdot)\\}_{i\geq 2})$ in different parts of
the state space. This, along with some novel concentration inequalities (Lemma
A.2), leads to quantitative probability bounds on the supremum and time
integral of $I^{(N)}(\cdot)$ (Lemma 3.1). This is a crucial step in proving
Theorem 2.4.

Second, note that, for the process level limit, one can ‘ignore’ the
contributions of $Q^{(N)}_{i}(\cdot)$ for $i\geq 3$. This is because, if
$Q^{(N)}_{3}(0)=0$, for fixed $T>0$, the probability that $Q^{(N)}_{3}(t)>0$
for any $t\in[0,N^{2\varepsilon}T]$ becomes small as $N\rightarrow\infty$ (see
(E)). However, for fixed $N$, the processes $\\{Q^{(N)}_{i}(\cdot)\\}_{i\geq
3}$ eventually become non-zero, and for obtaining probabilistic bounds on the
renewal times discussed above (see Lemma 4.2 and Proposition 4.3), one needs
precise quantitative control on $\sum_{i=3}^{\infty}Q^{(N)}_{i}(\cdot)$ (eg.
Lemma 3.3).

Finally, we briefly explain why the existing methods in the literature on
proving tightness of the diffusion-scaled pre-limit stationary distributions
fail to apply in our case. The celebrated method of [11] involves analyzing
stability properties of the associated ‘noiseless’ system to construct
suitable Lyapunov functions in terms of hitting times of certain compact sets
in the state space. Unlike Jackson networks, the stability analysis of the
noiseless system in the JSQ setting is quite involved and obtaining Lyapunov
functions based on this approach thus becomes very intricate, even in the
conventional Halfin-Whitt setting (see [8]). Moreover, the ‘singular’ nature
of the dynamics (arrivals only increase $Q_{1}^{(N)}(\cdot)$ when there are
idle servers) makes the ‘small set’ coupling analysis (characteristic of the
[30] approach used in [11]) very challenging. This motivates a more pathwise
analysis taken in this article. But the above discussion also sheds light on
why analyzing suitable hitting times lies at the heart of our methods.

###  1.4 Notation and organization.

For a metric space $S$, denote by $D=D([0,\infty),S)$ the space of functions
from $[0,\infty)$ to $S$ that are right continuous and have left limits
everywhere. For $x,y\in\mathbb{R}$, $x\vee y$ and $x\wedge y$ denote
$\max(x,y)$ and $\min(x,y)$, respectively. $x^{+}=\max(x,0)$. For a positive
deterministic sequence $(f(N))_{N\geq 1}$, a sequence of random variables
$(X(N))_{N\geq 1}$ is said to be $O_{\scriptscriptstyle\mathbb{P}}(f(N))$,
$o_{\scriptscriptstyle\mathbb{P}}(f(N))$, respectively if the sequence
$(X(N)/f(N))_{N\geq 1}$ is tight, and
$X(N)/f(N)\xrightarrow{\scriptscriptstyle\mathbb{P}}0$, as $N\to\infty$. Also,
$(X(N))_{N\geq 1}$ is said to be $\Theta_{\scriptscriptstyle\mathbb{P}}(f(N))$
if it is $O_{\scriptscriptstyle\mathbb{P}}(f(N))$ and there is a constant
$c>0$ such that $\liminf_{N\to\infty}(f(N))^{-1}\mathbb{E}(X(N))\geq c$. We
will use the symbol ‘$\ \xrightarrow{d}\ $’ to denote convergence in
distribution of random variables and ‘$\Rightarrow$’ to denote weak
convergence of stochastic processes uniformly on any compact time interval.

The rest of the sections are organized as follows: In Section 2 we present the
model, main results, and discuss their ramifications. Section 3 contains a
sample-path analysis of the process and several hitting time estimates. These
estimates will be used in Section 4 to establish the tightness of the sequence
of random variables corresponding to appropriately centered and scaled steady-
state total number of tasks, in the number of servers $N$. In Section 5, we
prove the process-level convergence. Proofs of some results are moved to the
appendix for better readability.

##  2 Model Description and main results

Consider a system with $N$ parallel single-server queues and one dispatcher.
Tasks with independent unit-mean exponentially distributed service
requirements arrive at the dispatcher as a Poisson process of rate
$\lambda(N)$. Denote the per-server load by $\lambda_{N}:=\lambda(N)/N$. Each
arriving task is assigned instantaneously and irrevocably to the shortest
queue at the time of arrival. Ties are broken arbitrarily. The service
discipline at each server is oblivious to the actual service requirements
(viz., FCFS). We will analyze the system in the so-called _super-Halfin-Whitt_
heavy-traffic regime, where

$\lambda_{N}=1-\frac{\beta}{N^{\frac{1}{2}+\varepsilon}}$ (2.1)

with fixed parameters $\beta>0$ and $\varepsilon\in(0,\frac{1}{2})$. Our goal
is to characterize the behavior of the queue-length process as $N\to\infty$.
At time $t$, $S^{(N)}(t)$ denotes the total number of tasks in the system,
$I^{(N)}(t)$ denotes the number of idle servers, and $Q^{(N)}_{i}(t)$ denotes
the number of servers of queue length at least $i$, $i\geq 1$. Note that
$\big{(}Q_{1}^{(N)},Q_{2}^{(N)},\ldots\big{)}$ provides a Markovian
description of the system state and $I^{(N)}=N-Q_{1}^{(N)}$, which we call the
idleness process. In the following, we will often consider
$\big{(}I^{(N)},Q_{2}^{(N)},\ldots\big{)}$ as the Markovian state descriptor
instead. For integers $x\in[0,N]$, $y\in[0,N-x]$ and a vector of non-negative
integers $\underline{z}=(z_{1},z_{2},\dots)\in\mathbb{N}_{0}^{\infty}$ with
$y\geq z_{1}\geq z_{2}\geq\dots$, we will denote the system state by
$(x,y,\underline{z})$ to mean that $I^{(N)}=x$, $Q_{2}^{(N)}=y$, and
$(Q_{3}^{(N)},Q_{4}^{(N)},\ldots)=\underline{z}$.

Let $A(\cdot)$ and $D(\cdot)$ be two independent unit-rate Poisson processes.
We will write the arrival and departure processes as random time change of $A$
and $D$ respectively; see [33, Section 2.1]. Hence, the cumulative number of
arrivals up to time $t$ can be written as $A(N\lambda_{N}t)$ and
$D\left(\int_{0}^{t}(N-I^{(N)}(s))ds\right)$, respectively. We introduce the
scaled process $\big{\\{}X^{(N)}(t),t\geq 0\big{\\}}$ as

$X^{(N)}(t):=\frac{S^{(N)}(N^{2\varepsilon}t)-N}{N^{\frac{1}{2}+\varepsilon}},$

and thus,

$X^{(N)}(t)=X^{(N)}(0)+N^{-\frac{1}{2}-\varepsilon}\left[A(N^{1+2\varepsilon}\lambda_{N}t)-D\Big{(}\int_{0}^{N^{2\varepsilon}t}(N-I^{(N)}(s))ds\Big{)}\right].$
(2.2)

Note that the process $X^{(N)}$ is not Markovian. However, we can view it as a
function of the irreducible Markov process
$\big{(}Q_{1}^{(N)},Q_{2}^{(N)},\ldots\big{)}$. Moreover, since the aggregate
arrival rate $N\lambda_{N}$ is less than $N$, the system is _subcritical_
according to the definition given in [6]. Further, since the arrivals occur as
a Poisson process and the service times are i.i.d. exponential, one can verify
that the conditions of [6, Theorem 1.2] are satisfied. Thus, the process is
$\big{(}Q_{1}^{(N)},Q_{2}^{(N)},\ldots\big{)}$ is positive recurrent (e.g.,
the hitting time of the state $(0,0,\ldots)$ starting from any state has
finite expectation), and hence ergodic for any fixed $N$. Denote by
$X^{(N)}(\infty)$ a random variable distributed as the centered and scaled
total number of tasks in the $N$-th system in steady state. We will
characterize the weak-limit of $X^{(N)}(\infty)$ and convergence of its
moments by establishing the process-level limit, ergodicity of the limiting
process, and the tightness of the random variables
$\\{X^{(N)}(\infty)\\}_{N\geq 1}$. The next result states that the sequence of
processes $\big{\\{}X^{(N)}(t),t\geq 0\big{\\}}_{N=1}^{\infty}$ converges
weakly to the process $X$, uniformly on compact time intervals, where
$\big{\\{}X(t),t\geq 0\big{\\}}$ is a certain Bessel process with negative
drift.

######  Theorem 2.1.

Fix $\beta>0$ and $\varepsilon\in(0,\frac{1}{2})$. Assume the sequence of
initial states $(X^{(N)}(0),I^{(N)}(0),Q^{(N)}_{2}(0),Q^{(N)}_{3}(0),\ldots)$
satisfy the following:

  1. (i)

$X^{(N)}(0)\ \xrightarrow{d}\ X^{*}$ as $N\to\infty$, where $X^{*}$ is a
positive random variable.

  2. (ii)

$\big{(}I^{(N)}(0)/N^{\frac{1}{2}-\varepsilon}\big{)}_{N}$ is a tight sequence
of random variables.

  3. (iii)

$\big{(}Q^{(N)}_{2}(0)/N^{\frac{1}{2}+\varepsilon}\big{)}_{N}$ is a tight
sequence of random variables.

  4. (iv)

$Q_{3}^{(N)}(0)\xrightarrow{\ \mathbb{P}\ }0$ as $N\to\infty$.

Then, for any fixed $T>0$, the scaled process $X^{(N)}$ converges weakly to
the path-wise unique solution of the following stochastic differential
equation, uniformly on $[0,T]$:

$dX(t)=\Big{(}\frac{1}{X(t)}-\beta\Big{)}dt+\sqrt{2}dW(t),$ (2.3)

with $X(0)\stackrel{{\scriptstyle\mathclap{\mbox{d}}}}{{=\joinrel=}}X^{*}$,
where $W=\big{(}W(t),t\geq 0\big{)}$ is the standard Brownian motion
independent of $X^{*}$.

Theorem 2.1 is proved in Section 5.

Observe that the SDE in (2.3) is a certain Langevin diffusion (see [35,
Section 1.2] for a discussion on Langevin diffusions) and is ergodic. Its
stationary distribution can be explicitly characterized as follows.

######  Proposition 2.2.

The SDE in (2.3) has a unique stationary distribution $\pi$ with probability
density function $\frac{d\pi}{dx}=\beta^{2}xe^{-\beta x},\ x>0,$ i.e.,
$\mathrm{Gamma}(2,\beta)$, having $p$-th moment $\Gamma(p+2)/\beta^{p}$.

The proof of Proposition 2.2 is given in Section 5.

######  Remark 2.3.

The limiting diffusion in (2.3) behaves like a Bessel process of dimension $2$
for small values of $X$ and a Brownian motion with negative drift for large
values of $X$. In particular, this diffusion almost surely never hits zero
(see Lemma 5.7). This is a consequence of the fact that the idleness process
in the prelimit moves in scale $N^{\frac{1}{2}-\varepsilon}$ and thus vanishes
under the scaling $N^{\frac{1}{2}+\varepsilon}$ appearing in $X^{(N)}$.
Moreover, the drift of the above diffusion process is smooth on $(0,\infty)$,
unlike the diffusion limit in the NDS regime [16]. This results in the
stationary density of the diffusion in [16] being $C^{1}$ but not $C^{2}$ on
$(0,\infty)$, whereas our stationary density is smooth on $(0,\infty)$.

The following theorem gives tail estimates for $X^{(N)}(\infty)$ for all fixed
large $N$ and shows that any subsequential weak-limit of $X^{(N)}(\infty)$
must have a strictly positive support. It also partially characterizes the
steady state behavior of the individual coordinates in
$(I^{(N)},Q^{(N)}_{2},\sum_{i=3}^{\infty}Q^{(N)}_{i})$ required for the
application of Theorem 5.1 in the limit interchange argument of Theorem 2.7.

######  Theorem 2.4.

Fix $\beta>0$ and $\varepsilon\in[0,\frac{1}{2})$.

  1. (i)

There exist positive constants $N_{0},B,C_{1},C_{2}$ such that for any $N\geq
N_{0}$,

$\begin{split}\mathbb{P}\big{(}X^{(N)}(\infty)\geq
x\big{)}&\leq\begin{cases}C_{1}\exp\big{\\{}-C_{2}x^{1/5}\big{\\}},\quad
4B\leq x\leq 2N^{\frac{1}{2}-\varepsilon},\\\
C_{1}\exp\big{\\{}-C_{2}x^{1/44}\big{\\}},\quad x\geq
2N^{\frac{1}{2}-\varepsilon}.\end{cases}\end{split}$ (2.4)

  2. (ii)

$\lim_{\delta\downarrow
0}\varliminf_{N\rightarrow\infty}\mathbb{P}\big{(}X^{(N)}(\infty)\geq\delta\big{)}=1.$
(2.5)

  3. (iii)

$\sup_{N\geq
1}\mathbb{E}\left[N^{-\frac{1}{2}-\varepsilon}Q^{(N)}_{2}(\infty)\right]<\infty$,

  4. (iv)

$\mathbb{E}\left[N^{-\frac{1}{2}+\varepsilon}I^{(N)}(\infty)\right]=\beta$ for
any $N\geq 1$, and

  5. (v)

$\sum_{i=3}^{\infty}Q^{(N)}_{i}(\infty)\xrightarrow{P}0$ as
$N\rightarrow\infty$.

Theorem 2.4 is proved in Section 4.

######  Remark 2.5.

The analysis of the steady-state tail behavior is based on a renewal theoretic
representation of the stationary measure. We consider the continuous time
Markov process $(I^{(N)}(\cdot),\\{Q^{(N)}_{i}(\cdot)\\}_{i\geq 2})$ starting
from $(0,\lfloor 2BN^{\frac{1}{2}+\varepsilon}\rfloor,\underline{0})$ (that
is, $I^{(N)}(0)=0$, $Q_{2}^{(N)}(0)=\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$ and
$Q_{3}^{(N)}(0)=Q_{4}^{(N)}(0)=\dots=0$) for a suitably large $B>0$. We then
wait for $Q_{2}^{(N)}$ to fall to $\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor$, then for
$\sum_{i=3}^{\infty}Q^{(N)}_{i}$ to drop to zero, and subsequently for
$Q_{2}^{(N)}$ to climb back to $\lfloor 2BN^{\frac{1}{2}+\varepsilon}\rfloor$.
More formally, define the stopping times $\sigma^{(N)}_{0}=0$, and for $i\geq
0$,

$\begin{split}\sigma^{(N)}_{2i+1}&\coloneqq\inf\\{t\geq\sigma^{(N)}_{2i}:Q^{(N)}_{2}(t)\leq\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor\\},\\\
\sigma^{(N)}_{2i+2}&\coloneqq\inf\\{t\geq\sigma^{(N)}_{2i+1}:Q^{(N)}_{2}(t)\geq\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor\\},\\\
\bar{K}^{(N)}&\coloneqq\inf\\{k\geq
1:\bar{Q}^{(N)}_{3}(\sigma^{(N)}_{2k})=0\\}\quad\text{and}\quad\Theta^{(N)}\coloneqq\sigma^{(N)}_{2\bar{K}^{(N)}}.\end{split}$
(2.6)

Note that $I^{(N)}(\Theta^{(N)})=0$, $Q_{2}^{(N)}(\Theta^{(N)})=\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$ and $\bar{Q}^{(N)}_{3}(\Theta^{(N)})=0$.
Therefore, $\Theta^{(N)}$ is a renewal time point. Therefore, the process
observed from time $\Theta^{(N)}$ onward has the same distribution as the one
starting from time $0$. On showing that $\Theta^{(N)}$ has finite expectation,
the stationary distribution of
$(I^{(N)}(\cdot),\\{Q^{(N)}_{i}(\cdot)\\}_{i\geq 2})$ admits the following
representation:

$\pi\left((I^{(N)}(\infty),Q^{(N)}_{2}(\infty),\dots)\in
A\right)=\frac{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\int_{0}^{\Theta^{(N)}}\mathds{1}\left((I^{(N)}(s),Q^{(N)}_{2}(s),\dots)\in
A\right)ds\right)}{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\Theta^{(N)}\right)}$
(2.7)

for any Borel set $A\subseteq\\{0,1,2,\ldots\\}^{\infty}$, where
$\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}(\cdot)$ refers to the
expectation given the starting state is $(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})$. Showing this is
standard renewal theory (see, for example, proof of Theorem 3.3 in [3]): one
expresses the stationary distribution in terms of the long time average
occupancy measure which, in turn, can be expressed in terms of the i.i.d.
regenerative cycles of the process between successive renewal times.
Application of the strong law of large numbers yields (2.7).

Hence, obtaining tail behavior of the stationary distribution reduces to
quantifying the extremal behavior of the process path before time
$\Theta^{(N)}$. The exponents in the tail bounds above arise from applying a
concentration result (Lemma A.2) for sums of random variables with stretched-
exponential tails that stochastically dominate the integral of the idleness
process (see Lemma B.4). We do not believe that these exponents are optimal.
However, they show that the steady-state tails are sufficiently light to have
finiteness of all moments.

######  Remark 2.6.

Note that Theorem 2.4 also applies to $\varepsilon=0$ (the Halfin-Whitt
regime). Tightness of the diffusion-scaled steady state occupancy measures in
the Halfin-Whitt regime was shown by [7] using a generator expansion method in
conjunction with Stein’s method. However, this requires apriori knowledge of
the diffusion limit and an elaborate construction of Lyapunov functions based
on the dynamics of the noiseless system associated with this diffusion limit.
Moreover, the results in [7] provide tightness by bounding the expected values
of $Q^{(N)}_{i}(\infty),\,i\geq 1$, but finiteness of higher moments remained
open. Further, the analysis is highly tied to the Halfin-Whitt regime as the
diffusion limit behavior drastically changes as one moves to the super-Halfin-
Whitt regime. In contrast, the renewal theoretic method for studying
stationary distributions developed in the current paper can be applied
directly to the pre-limit process without knowledge of its diffusion limit. In
addition to giving a much more detailed picture of the tail behavior of the
steady state, it can be applied universally for all
$\varepsilon\in[0,\frac{1}{2})$ as the above phase transition does not appear
in the pre-limit behavior. Recently, the sample path approach in the current
paper has been utilized in [9] to obtain rates of convergence of the JSQ
system in Halfin-Whitt regime to its diffusion limit by directly analyzing the
generator of the pre-limit process.

Theorem 2.4 implies that $\big{\\{}X^{(N)}(\infty)\big{\\}}_{N=1}^{\infty}$ is
tight in $\mathbb{R}$. By Theorem 5.1, Proposition 2.2, and Theorem 2.4, the
interchangeability of the $t\to\infty$ and $N\to\infty$ limits in Theorem 2.7
can be established using routine arguments. The proof of Theorem 2.7 is given
at the end of this section.

######  Theorem 2.7.

Fix $\beta>0$ and $\varepsilon\in(0,\frac{1}{2})$. The sequence of random
variables $\big{\\{}X^{(N)}(\infty)\big{\\}}_{N\geq 1}$ converges weakly to
the $\mathrm{Gamma}\left(2,\beta\right)$ distribution as $N\rightarrow\infty$,
where the probability density function of $\mathrm{Gamma}\left(2,\beta\right)$
is given by $f(x)=\beta^{2}xe^{-\beta x},\ x\in(0,\infty).$ Moreover, for any
$p>0$,
$\mathbb{E}\Big{[}X^{(N)}(\infty)\Big{]}^{p}\rightarrow\frac{\Gamma(p+2)}{\beta^{p}}$
as $N\to\infty$, where $\Gamma$ denotes the standard Gamma function.

Let $W^{(N)}$ be a random variable denoting the waiting time of a typical task
in steady state for the $N$-th system. By Little’s law [23, $\S$ 6.4 (a)],
note that
$\mathbb{E}\big{(}W^{(N)}\big{)}=\big{(}N\lambda_{N}\big{)}^{-1}\sum_{i=2}^{\infty}\mathbb{E}\big{(}Q_{i}^{(N)}(\infty)\big{)}=\big{(}N\lambda_{N}\big{)}^{-1}\mathbb{E}\big{(}S^{(N)}(\infty)+I^{(N)}(\infty)-N\big{)}.$
Now, since in steady state, expected total arrival rate equals expected total
service rate, we have $\mathbb{E}(I^{(N)}(\infty))=N(1-\lambda_{N})=\beta
N^{\frac{1}{2}-\varepsilon}$. Therefore, we have the following immediate
corollary of Theorem 2.7.

######  Corollary 2.8.

$\lim_{N\to\infty}N^{\frac{1}{2}-\varepsilon}\mathbb{E}\big{(}W^{(N)}\big{)}=\frac{2}{\beta}.$

######  Remark 2.9 (Contrast with centralized systems).

An interesting aspect of the many-server limit of the JSQ policy is revealed
as we compare it with the corresponding M/M/$N$ system with the same load per
server. As briefly mentioned in the introduction, the key difference between
the JSQ dynamics and the M/M/$N$ dynamics lies in the non-idling nature of the
latter. In the JSQ dynamics, there can be idle servers in the system, while
having waiting tasks. However, as the system load becomes closer to 1, one may
expect that most of the servers must remain busy to keep the system stable.
Consequently, JSQ should behave similarly to the centralized queueing system.
Theorem 2.7 shows that this is not the case even in the super-Halfin-Whitt
regime. The centered and scaled total number of tasks for JSQ converges to
$\mathrm{Gamma}\left(2,\beta\right)$ with mean $2/\beta$, instead of
$\mathrm{Exponential}(\beta)$ with mean $1/\beta$ for the corresponding
M/M/$N$ system. Interestingly, indeed, if the load is much heavier, that is,
$\lambda_{N}=1-O(N^{-\alpha})$ with $\alpha>2$, then the result in [20]
implies that the appropriately scaled total number of tasks under the JSQ
policy has the same limiting distribution as the centralized system. It will
be an interesting future direction to identify the precise scaling of the
system load where this transition of behavior occurs.

###### Proof of Theorem 2.7..

For brevity of notation, we will use the following notation in this proof:

$\mathbf{X}^{(N)}:=\Big{(}X^{(N)}(0),\frac{I^{(N)}(0)}{N^{\frac{1}{2}-\varepsilon}},\frac{Q^{(N)}_{2}(0)}{N^{\frac{1}{2}+\varepsilon}},\sum_{i=3}^{\infty}Q^{(N)}_{i}(0)\Big{)}.$

Now assume that the system is initiated at the steady state, that is,

$\Big{(}X^{(N)}(0),I^{(N)}(0),Q_{2}^{(N)}(0),\sum_{i=3}^{\infty}Q^{(N)}_{i}(0)\Big{)}\stackrel{{\scriptstyle\mathclap{\mbox{d}}}}{{=\joinrel=}}\Big{(}X^{(N)}(\infty),I^{(N)}(\infty),Q_{2}^{(N)}(\infty),\sum_{i=3}^{\infty}Q^{(N)}_{i}(\infty)\Big{)}.$

Note that by Theorem 2.4 the sequence of random variables
$\\{\mathbf{X}^{(N)}\\}_{N\geq 1}$ is tight and moreover,
$\sum_{i=3}^{\infty}Q^{(N)}_{i}(\infty)\xrightarrow{P}0$ as
$N\rightarrow\infty$. Hence, we can extract a subsequence $(\hat{N})$ of $(N)$
for which $X^{(\hat{N})}(0)\xrightarrow{d}X^{*}$ for some finite random
variable. Furthermore, Theorem 2.4 (ii) implies that $\mathbb{P}(X^{*}>0)=1$
and thus, the conditions of Theorem 2.1 hold. Thus, by Theorem 2.1 applied to
this subsequence, the process $X^{(\hat{N})}(\cdot)$ converges weakly to the
path-wise unique solution of (2.3), uniformly on $[0,T]$ with
$X(0)\stackrel{{\scriptstyle\mathclap{\mbox{d}}}}{{=\joinrel=}}X^{*}$. Note
that since $X^{(\hat{N})}(t)$ is also distributed as $X^{(\hat{N})}(\infty)$
for all $t\geq 0$, by Theorem 2.1 and Proposition 2.2, $X^{*}$ must be
distributed as the unique stationary distribution of the diffusion (2.3). This
proves the weak convergence of $X^{(N)}(\infty)$ in $\mathbb{R}$.

For the convergence of the $p$-th moment, note that $X^{(N)}(\infty)$’s are
nonnegative random variables and hence,
$\mathbb{E}\Big{[}(X^{(N)}(\infty))^{p}\Big{]}=p\int_{0}^{\infty}x^{p-1}\mathbb{P}(X^{(N)}(\infty)>x)dx.$
Take $B,N_{0}$ as in Theorem 2.4. From the tail-probability bound in Theorem
2.4, we have that for any $p>0$ and $\tilde{\varepsilon}>0$,

$\begin{split}\sup_{N\geq
N_{0}}\mathbb{E}\Big{[}(X^{(N)}(\infty))^{p+\tilde{\varepsilon}}\Big{]}&\leq\sup_{N\geq
N_{0}}\Big{(}(4B\vee
1)^{p+\tilde{\varepsilon}}+(p+\tilde{\varepsilon})\int_{(4B\vee
1)}^{\infty}x^{p+\tilde{\varepsilon}-1}\mathbb{P}(X^{(N)}(\infty)>x)dx\Big{)}\\\
&\leq\Big{(}(4B\vee
1)^{p+\tilde{\varepsilon}}+(p+\tilde{\varepsilon})\int_{(4B\vee
1)}^{\infty}x^{p+\tilde{\varepsilon}-1}C_{1}\exp\big{\\{}-C_{2}x^{1/44}\big{\\}}dx\Big{)}<\infty.\end{split}$
(2.8)

Since $X^{(N)}(\infty)\xrightarrow{d}\mathrm{Gamma}\left(2,\beta\right)$ and
(2.8) holds, by [5, Corollary of Theorem 25.12], for any $p>0$,
$\mathbb{E}\big{[}X^{(N)}(\infty)\big{]}^{p}\rightarrow\Gamma(p+2)/\beta^{p}$
as $N\to\infty$. ∎

##  3 Sample-path analysis of the pre-limit process.

In this section, we will obtain quantitative estimates on the sample path
behavior of the pre-limit process that will be useful in Sections 4 and 5. A
significant part of our work, especially studying the steady-state behavior,
involves a detailed pathwise analysis of the pre-limit process. Recall the
discussion in Remark 2.5 in this regard. The key quantity to analyze is
$\Theta^{(N)}$ and, in the interval $[0,\Theta^{(N)}]$, how much time the
process spends in different parts of the state space. Such estimates are
obtained in this section. The challenge in this analysis comes from the fact
that this process behaves very differently in different parts of the state
space (no _state space collapse_). Loosely speaking, the behavior of the
process can be categorized into two qualitatively different phases:

(a) Heavily-loaded phase. Loosely speaking, when the system is heavily loaded,
i.e., $Q^{(N)}_{2}$ is large, the evolution of $Q^{(N)}_{2}$ is qualitatively
similar to that of $X^{(N)}$. Thus, (2.2) hints that for $Q^{(N)}_{2}$ to fall
below a certain threshold (we call this a ‘down-crossing’), the integral of
the idleness process has to grow at a small enough rate with time so as to
create a ‘negative drift’ for $Q^{(N)}_{2}$ (see (3.3)). Quantifying this
takes significant work and is the content of Section 3.1. Also, note that the
true evolution of $Q^{(N)}_{2}$ is more complicated than that of $X^{(N)}$
given in (2.2). This is because the evolution of $Q^{(N)}_{2}$ is governed by
two very different types of effects. When $I^{(N)}>0$, $Q^{(N)}_{2}$ can only
decrease and this happens when a customer is served at a busy server (with two
or more customers). In contrast, the increase in $Q^{(N)}_{2}$ happens only
when $I^{(N)}=0$ and additional arrivals take place. This is a more ‘local
time like’ effect. This leads to added technical challenges. In Section 3.2,
this drift is exploited to bound the supremum and estimate the decay rate of
$S^{(N)}$ and $\sum_{i=3}^{\infty}Q^{(N)}_{i}$ in the heavily loaded phase. In
Section 3.3, a probability bound is obtained for the time taken for the down-
crossing.

(b) Lightly-loaded phase. On the other hand, in the lightly loaded phase, when
$Q^{(N)}_{2}$ is small, the fluctuations in the arrival and departure
processes for the system eventually push $Q^{(N)}_{2}$ above a certain level
(see (3.4)). This is what we call an ‘up-crossing’ and quantify it in Section
3.4.

Later, in Section 4, the above two phases are combined to create a renewal
structure which sheds light on the tail behavior of the stationary
distribution of $X^{(N)}$ for fixed large $N$. An overview of how various
results of Section 3 are used in Section 4 is schematically presented in
Figure 1.

Figure 1: Interdependence of various results of Sections 3 and 4.

In Section 3.5, we estimate the probability of $Q^{(N)}_{2}$ crossing large
values on large compact time intervals. This is crucially used in the process-
level convergence proofs in Sections 5 and 6 (in particular, Proposition 5.6).

The general technique to achieve the above involves decomposing the process
sample path into excursions between suitably chosen stopping times. Between
successive stopping times, the behavior is more uniform, and comparable to
some process that is easier to analyze.

Now, we set up some notation. Throughout this article, we fix an
$\varepsilon\in[0,1/2)$. Define
$\bar{Q}^{(N)}_{3}(t):=\sum_{i=3}^{\infty}Q^{(N)}_{i}(t)$ and, for $x,y,z\geq
0$, define the stopping times

$\begin{split}\tau^{(N)}_{1}(x)&:=\inf\big{\\{}t\geq 0:I^{(N)}(t)=\lfloor
xN^{\frac{1}{2}-\varepsilon}\rfloor\big{\\}},\\\
\tau^{(N)}_{2}(y)&:=\inf\big{\\{}t\geq 0:Q^{(N)}_{2}(t)=\lfloor
yN^{\frac{1}{2}+\varepsilon}\rfloor\big{\\}},\\\
\tau^{(N)}_{s}(z)&:=\inf\big{\\{}t\geq 0:S^{(N)}(t)=\lfloor
zN^{\frac{1}{2}+\varepsilon}\rfloor\big{\\}}.\end{split}$ (3.1)

###  3.1 Upper bound for idleness process in heavily loaded phase.

Intuitively speaking, when $Q_{2}^{(N)}$ is large, the process denoting the
number of idle servers, $I^{(N)}(t)$, can be upper bounded by a birth-death
process. In particular, if $Q_{2}^{(N)}\geq BN^{\frac{1}{2}+\varepsilon}$,
then the rate of decrease of $I^{(N)}$ when it is positive, is $N-\beta
N^{\frac{1}{2}-\varepsilon}$ (whenever there is an arrival), and the rate of
increase is $Q_{1}^{(N)}-Q_{2}^{(N)}$, which is at most
$N-BN^{\frac{1}{2}+\varepsilon}$. For any fixed $B>0$, let us define such a
birth-death process $\bar{I}^{(N)}_{B}$, with increase rate
$N-BN^{\frac{1}{2}+\varepsilon}$ and decrease rate $N-\beta
N^{\frac{1}{2}-\varepsilon}$. We will assume that $N$ is large enough so that
$N>BN^{\frac{1}{2}+\varepsilon}>\beta N^{\frac{1}{2}-\varepsilon}$. From the
above discussion, if $Q^{(N)}_{2}(0)>BN^{\frac{1}{2}+\varepsilon}$, then there
exists a natural coupling such that
$I^{(N)}(t\wedge\tau^{(N)}_{2}(B))\leq\bar{I}^{(N)}_{B}(t\wedge\tau^{(N)}_{2}(B)),$
for all $t\geq 0$. Thus, in the analysis of $I^{(N)}$, a key ingredient is to
study this upper-bounding birth death process. In particular, as can be
understood from the evolution equation of $X^{(N)}(t)$ in (2.2), two
quantities involving $I^{(N)}$ that will be pivotal in successive analysis are
its integral and supremum over appropriately scaled time intervals. For that,
the following lemma will be crucial in quantifying the ‘negative drift’
created due to the integral of $I^{(N)}$ being ‘small’ in the heavily loaded
phase (when $Q^{(N)}_{2}>BN^{\frac{1}{2}+\varepsilon}$).

######  Lemma 3.1.

Assume $\bar{I}^{(N)}_{B}(0)=0$. There exist $t_{0}>0,B_{1}\geq 1$ such that
for all $B\geq B_{1}$, there exists $\tilde{N}_{B}$ such that for all
$N\geq\tilde{N}_{B}$ and $t\geq t_{0}$, the following hold:

  1. (i)

$\mathbb{P}\big{(}\int_{0}^{N^{2\varepsilon}s}\bar{I}_{B}^{(N)}(u)du\geq\frac{\beta}{2}N^{\frac{1}{2}+\varepsilon}s\text{
for some }s\geq t\big{)}\leq
c_{1}\exp\\{-c_{2}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}t^{\frac{1}{5}}\\}$;

  2. (ii)

$\mathbb{P}\big{(}\sup_{s\leq
t}\bar{I}_{B}^{(N)}(N^{2\varepsilon}s)\geq\frac{\beta}{4}N^{\frac{1}{2}-\varepsilon}t\big{)}\leq\exp\\{-\tilde{c}_{1}BN^{4\varepsilon}t\\}+\tilde{c}_{2}N^{4\varepsilon}t\exp\\{-\tilde{c}_{3}\sqrt{B}t\\}$.

The above constants $c_{i},\tilde{c}_{i}$ may depend on $\beta$, but not on
$B,N,t$.

The proof of Lemma 3.1 is given in Appendix B. Here we provide a brief outline
of the proof idea. We will estimate
$\int_{0}^{N^{2\varepsilon}t}\bar{I}_{B}^{(N)}(s)ds$ for large $B,N$ and $t$
by identifying certain excursions in the path of the process
$\bar{I}^{(N)}_{B}$. The integral will then be estimated by controlling the
duration of each such excursion and the supremum of the process
$\bar{I}^{(N)}_{B}$ on this excursion. Let $\bar{I}^{(N)}_{B}(0)=0$. Given
$\eta>0$, define the following stopping times:
$\bar{\sigma}^{(N)}_{0}\coloneqq 0$, and for $i\geq 0$,

$\displaystyle\bar{\sigma}^{(N)}_{2i+1}$
$\displaystyle\coloneqq\inf\big{\\{}t\geq\bar{\sigma}^{(N)}_{2i}:\bar{I}^{(N)}_{B}(t)\geq\lfloor\eta
N^{\frac{1}{2}-\varepsilon}\rfloor\big{\\}},\text{ and }$
$\displaystyle\bar{\sigma}^{(N)}_{2i+2}$
$\displaystyle\coloneqq\inf\big{\\{}t\geq\bar{\sigma}^{(N)}_{2i+1}:\bar{I}^{(N)}_{B}(t)\leq\big{\lfloor}\frac{\eta}{2}N^{\frac{1}{2}-\varepsilon}\big{\rfloor}\big{\\}}.$

Also define:

$\bar{\xi}^{(N)}_{i}:=\bar{\sigma}^{(N)}_{2i}-\bar{\sigma}^{(N)}_{2i-1},\ \ \
\bar{u}^{(N)}_{i}:=\sup_{s\in[\bar{\sigma}^{(N)}_{2i-1},\bar{\sigma}^{(N)}_{2i}]}(\bar{I}_{B}^{(N)}(s)-\lfloor\eta
N^{\frac{1}{2}-\varepsilon}\rfloor),\ i\geq 1,$

and $\bar{K}^{(N)}_{t}:=\inf\big{\\{}k:\bar{\sigma}^{(N)}_{2k}\geq
N^{2\varepsilon}t\big{\\}}$. Note that

$\int_{0}^{N^{2\varepsilon}t}\bar{I}_{B}^{(N)}(s)ds\leq\eta
N^{\frac{1}{2}+\varepsilon}t+\sum_{i=1}^{\bar{K}^{(N)}_{t}}\bar{u}^{(N)}_{i}\bar{\xi}^{(N)}_{i}.$
(3.2)

Therefore, the proof of Lemma 3.1 will rely on analyzing the behavior of
$\bar{u}^{(N)}_{i}\bar{\xi}^{(N)}_{i}$ (Lemma B.2), that of
$\bar{K}^{(N)}_{t}$ (Lemma B.3), and of the random sum
$\sum_{i=1}^{\bar{K}^{(N)}_{t}}\bar{u}^{(N)}_{i}\bar{\xi}^{(N)}_{i}$ (Lemma
B.4). To analyze the random sum, we will use the concentration inequality for
independent random variables with stretched exponential tails stated in Lemma
A.2. The form of exponents of $N,B,$ and $t$ appearing on the right hand side
of Lemma 3.1 (i) and (ii) is an artifact of using Lemma A.2 along with the
tail estimates for $\bar{u}^{(N)}_{i}\bar{\xi}^{(N)}_{i}$ from Lemma B.2. We
do not expect these exponents to be optimal, but they will serve our purpose
of showing that the integral has sufficiently light tail.

###  3.2 Controlling long queues in heavily loaded phase.

Recall that for any $t\geq 0$, $S^{(N)}(t)$ denotes the total number of tasks
in the system at time $t$, and
$\bar{Q}^{(N)}_{3}(t):=\sum_{i=3}^{\infty}Q^{(N)}_{i}(t)$ denotes the number
of tasks waiting behind at least two other tasks at time $t$. Also recall that
$\tau_{2}^{(N)}(B)$ denotes the first time $Q_{2}^{(N)}$ hits $\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor$. As described in Remark 2.5, the renewal
time $\Theta^{(N)}$ is crucial to the steady-state analysis. For this, we need
to have sharp control on how large the quantities $S^{(N)}$ and
$\bar{Q}^{(N)}_{3}$ can become during the phase when $Q_{2}^{(N)}$ hits
$\lfloor BN^{\frac{1}{2}+\varepsilon}\rfloor$ starting from $\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$. This is achieved in Lemma 3.2 and Lemma
3.3 in this section. They will be used in the subsequent sections.

First, let us introduce the following notation. For integers $x\in[0,N]$,
$y\in[0,N-x]$ and a vector of non-negative integers
$\underline{z}=(z_{1},z_{2},\dots)\in\mathbb{N}_{0}^{\infty}$ with $y\geq
z_{1}\geq z_{2}\geq\dots$, denote

$\displaystyle\mathbb{P}_{(x,y,\underline{z})}(\cdot)$
$\displaystyle:=\mathbb{P}(\ \cdot\ |\
I^{(N)}(0)=x,Q^{(N)}_{2}(0)=y,Q^{(N)}_{i}(0)=z_{i-2}\text{ for }i\geq
3)\quad\text{and}$
$\displaystyle\sup_{\underline{z}}\mathbb{P}_{(x,y,\underline{z})}(\cdot)$
$\displaystyle:=\sup\Big{\\{}\mathbb{P}_{(x,y,\underline{z})}(\cdot):\underline{z}\in\mathbb{N}_{0}^{\infty},\,z_{1}\geq
z_{2}\geq\dots,\,z_{1}\leq y\Big{\\}}.$

The following lemma quantifies the probability of the total queue length
becoming large in the heavily loaded phase. The negative drift created on
account of Lemma 3.1 ensures that this probability is small.

######  Lemma 3.2.

There exist $t_{0},B_{1},$ such that for all $B\geq B_{1},N\geq\tilde{N}_{B}$,
and $x\geq t_{0}$,

$\displaystyle\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}S^{(N)}\text{
hits }S^{(N)}(0)+x\beta N^{\frac{1}{2}+\varepsilon}\text{ before time
}\tau_{2}^{(N)}(B)\big{)}$ $\displaystyle\leq$
$\displaystyle\hat{c}_{1}\exp\\{-\hat{c}_{2}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}x^{\frac{1}{5}}\\}+\hat{c}_{3}\exp\\{-\hat{c}_{4}x\\},$

where constants $\hat{c}_{i}$, $i\in\\{1,2,3,4\\}$ do not depend on $B$ and
$N$.

The first term in the above bound arises from the control on the integral of
the idleness process achieved in Lemma 3.1 (i), while the second term arises
from hitting probabilities of processes that are martingales plus a negative
drift (which approximates $S^{(N)}$ in this phase).

###### Proof.

Proof of Lemma 3.2. Note that there is a natural coupling between $I^{(N)}(t)$
and $\bar{I}^{(N)}_{B}(t)$, such that for all $t\leq\tau_{2}^{(N)}(B)$,
$I^{(N)}(t)\leq\bar{I}^{(N)}_{B}(t)$. Thus, for all $t\leq\tau_{2}^{(N)}(B)$,

$\displaystyle S^{(N)}(t)$ $\displaystyle\leq S^{(N)}(0)+A((N-\beta
N^{\frac{1}{2}-\varepsilon})t)-D\Big{(}\int_{0}^{t}(N-\bar{I}^{(N)}_{B}(s))ds\Big{)}$
$\displaystyle=S^{(N)}(0)+\hat{A}((N-\beta
N^{\frac{1}{2}-\varepsilon})t)-\hat{D}\Big{(}\int_{0}^{t}(N-\bar{I}^{(N)}_{B}(s))ds\Big{)}+\int_{0}^{t}\bar{I}_{B}^{(N)}(s)ds-\beta
N^{\frac{1}{2}-\varepsilon}t,$

where recall $A(\cdot)$ and $D(\cdot)$ are independent unit-rate Poisson
processes representing arrivals and departures respectively, and
$\hat{A}(s)=A(s)-s$ and $\hat{D}(s)=D(s)-s$. Therefore,

$\displaystyle\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}S^{(N)}\text{
hits }S^{(N)}(0)+x\beta N^{\frac{1}{2}+\varepsilon}\text{ before
}\tau^{(N)}_{2}(B))\big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\int_{0}^{N^{2\varepsilon}s}\bar{I}_{B}^{(N)}(u)du\geq\frac{\beta
x}{4}N^{\frac{1}{2}+\varepsilon}+\frac{\beta
s}{2}N^{\frac{1}{2}+\varepsilon}\text{ for some }s\geq 0\Big{)}$ (3.3)
$\displaystyle\hskip 56.9055pt+\mathbb{P}\Big{(}\mathcal{M}^{*}(t)-\frac{\beta
t}{2}N^{\frac{1}{2}-\varepsilon}\text{ hits }\frac{3\beta
x}{4}N^{\frac{1}{2}+\varepsilon}\text{ for some }t\geq 0\Big{)},$

where $\mathcal{M}^{*}(t)=\hat{A}((N-\beta
N^{\frac{1}{2}-\varepsilon})t)-\hat{D}(\int_{0}^{t}(N-\bar{I}_{B}(s))ds)$.
Recall $t_{0},B_{1}$ from Lemma 3.1. For $x\geq t_{0}$, $B\geq B_{1}$,
$N\geq\tilde{N}_{B}$,

$\begin{split}&\mathbb{P}\Big{(}\int_{0}^{N^{2\varepsilon}s}\bar{I}_{B}^{(N)}(u)du\geq\frac{\beta
x}{4}N^{\frac{1}{2}+\varepsilon}+\frac{\beta
s}{2}N^{\frac{1}{2}+\varepsilon}\text{ for some }s\geq 0\Big{)}\\\
&\leq\mathbb{P}\Big{(}\int_{0}^{N^{2\varepsilon}x}\bar{I}_{B}^{(N)}(u)du\geq\frac{\beta
x}{4}N^{\frac{1}{2}+\varepsilon}\Big{)}+\mathbb{P}\Big{(}\int_{0}^{N^{2\varepsilon}s}\bar{I}_{B}^{(N)}(u)du\geq\frac{\beta
s}{2}N^{\frac{1}{2}+\varepsilon}\text{ for some }s\geq x\Big{)}\\\
&\leq\hat{c}\exp\\{-\hat{c}^{\prime}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}x^{\frac{1}{5}}\\},\end{split}$
(3.4)

for some constants $\hat{c},\hat{c}^{\prime}>0$, where the last inequality
follows by (B) and Lemma 3.1 (i). For the second term on the right-hand-side
of (3.2), denote $\bar{s}_{k}=kN^{2\varepsilon}x$, $k\geq 0$. For any $k\geq
0$,

$\displaystyle\mathbb{P}\Big{(}\sup_{s\in[\bar{s}_{k},\bar{s}_{k+1}]}\Big{(}\mathcal{M}^{*}(s)-\frac{\beta
s}{2}N^{\frac{1}{2}-\varepsilon}\Big{)}\geq\frac{3\beta
x}{4}N^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\sup_{s\in[0,\bar{s}_{k+1}]}\mathcal{M}^{*}(s)\geq\frac{2N^{-2\varepsilon}\bar{s}_{k}+3x}{4}\beta
N^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\sup_{s\in[0,\bar{s}_{k+1}]}\mathcal{M}^{*}(s)\geq\frac{2k+5}{4}x\beta
N^{\frac{1}{2}+\varepsilon}\Big{)}\leq
c^{\prime\prime}e^{-\bar{c}^{\prime\prime}(k+1)x},$

for some constants $c^{\prime\prime},\bar{c}^{\prime\prime}>0$, where the last
inequality follows from Lemma A.1. Summing over $k$, we obtain

$\mathbb{P}\Big{(}\mathcal{M}^{*}(t)-\frac{\beta
t}{2}N^{\frac{1}{2}-\varepsilon}\text{ hits
}\frac{x}{2}N^{\frac{1}{2}+\varepsilon}\text{ for some }t\geq 0\Big{)}\leq
c^{\prime\prime}e^{-\bar{c}^{\prime\prime}x}.$ (3.5)

Plugging (3.4) and (3.5) into (3.2) and choosing appropriate constants
complete the proof. ∎

Now recall that
$\bar{Q}^{(N)}_{3}(t)=\sum_{i=3}^{\infty}Q^{(N)}_{i}(t),\,t\geq 0$ and the
renewal time $\Theta^{(N)}$. Note that for such a renewal event to occur, all
the following three things need to happen: Starting from $(0,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\underline{0})$,

(a) $Q_{2}^{(N)}$ falls to $\lfloor BN^{\frac{1}{2}+\varepsilon}\rfloor$, then

(b) $\bar{Q}^{(N)}_{3}$ drops to zero, and subsequently,

(c) $Q_{2}^{(N)}$ climbs back to $\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$.

Part (b) requires special care as, although the probability of
$\bar{Q}^{(N)}_{3}$ becoming positive before time $\tau_{2}^{(N)}(B)$ is small
for large $N$, on the event that this happens, it takes a potentially long
time for $\bar{Q}^{(N)}_{3}$ to fall back to zero. This is quantified in Lemma
3.3, which gives tail estimates on the supremum of $\bar{Q}^{(N)}_{3}$ on
$[0,\tau_{2}^{(N)}(B)]$ and shows that with probability at least $1/2$,
$\bar{Q}^{(N)}_{3}$ falls by
$\bar{Q}^{(N)}_{3}(0)\wedge\frac{B}{4\beta}N^{2\varepsilon}$ on this time
interval. Define

$\bar{Z}^{(N)}_{*}=\sup_{s\in[0,\tau^{(N)}_{2}(B)]}\big{(}\bar{Q}^{(N)}_{3}(s)-\bar{Q}^{(N)}_{3}(0)\big{)}_{+},\quad\text{and}\quad\bar{Z}^{(N)}=\bar{Q}^{(N)}_{3}(\tau^{(N)}_{2}(B))-\bar{Q}^{(N)}_{3}(0).$
(3.6)

######  Lemma 3.3.

There exists $B_{2}>0$, such that for all $B\geq B_{2}$, we can obtain
$\tilde{N}^{*}_{B}\in\mathbb{N}$ for which the following hold for all
$N\geq\tilde{N}^{*}_{B}$ and $x>0$.

  1. (i)

There exist constants $\bar{c}_{i}$, $i\in\\{1,2,3,4\\}$, not depending on
$N,x$, such that

$\begin{split}\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}&\big{(}\bar{Z}^{(N)}_{*}\geq
x\beta N^{\frac{1}{2}+\varepsilon}\big{)}\\\
&\leq\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}\big{(}\exp\\{-\bar{c}_{3}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}x^{\frac{1}{5}}\\}+\exp\\{-\bar{c}_{4}x\\}\big{)}.\end{split}$
(3.7)

  2. (ii)

$\inf_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\Big{(}\bar{Z}^{(N)}\leq-\big{[}\bar{Q}^{(N)}_{3}(0)\wedge\frac{B}{4\beta}N^{2\varepsilon}\big{]}\Big{)}\geq\frac{1}{2}$.

As we will see in the proof of Lemma 3.3 below, the exponents in the right
hand side of (3.7) are inherited from those in Lemma 3.2 as we will relate the
hitting probabilities of $\bar{Z}^{(N)}_{*}$ with that of $S^{(N)}$.

###### Proof.

Proof of Lemma 3.3. (i) Recall $t_{0}$ from Lemma 3.2. Let
$\bar{N}_{B}\in\mathbb{N}$ be such that
$N-2BN^{\frac{1}{2}+\varepsilon}\geq\frac{N}{2}$ and
$N^{\frac{1}{2}-\varepsilon}/(2\beta)>t_{0}$ for all $N\geq\bar{N}_{B}$. If
$\bar{Z}^{(N)}_{*}\geq x\beta N^{\frac{1}{2}+\varepsilon}$, then there exists
$s\in[0,\tau^{(N)}_{2}(B)]$ such that
$Q^{(N)}_{2}(s)=N,\bar{Q}^{(N)}_{3}(s)=\bar{Q}^{(N)}_{3}(0)+x\beta
N^{\frac{1}{2}+\varepsilon},$ and $I^{(N)}(0)=0$. Hence, for all
$N\geq\bar{N}_{B}$,

$\displaystyle S^{(N)}(s)=$ $\displaystyle N+N+\bar{Q}^{(N)}_{3}(0)+x\beta
N^{\frac{1}{2}+\varepsilon}$
$\displaystyle\geq(N-I^{(N)}(0)+Q_{2}^{(N)}(0)+\bar{Q}^{(N)}_{3}(0))+(N-2BN^{\frac{1}{2}+\varepsilon}+x\beta
N^{\frac{1}{2}+\varepsilon})$
$\displaystyle=S^{(N)}(0)+(N-2BN^{\frac{1}{2}+\varepsilon}+x\beta
N^{\frac{1}{2}+\varepsilon})$ $\displaystyle\geq
S^{(N)}(0)+\Big{(}\frac{N}{2}+x\beta N^{\frac{1}{2}+\varepsilon}\Big{)}.$

Take $B_{1}$, $\tilde{N}_{B}$ as in Lemma 3.2 and define
$\tilde{N}^{\prime}_{B}:=\tilde{N}_{B}\vee\bar{N}_{B}$. Thus, for $B\geq
B_{1}$, $N\geq\tilde{N}^{\prime}_{B}$, $x>0$,

$\displaystyle\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\bar{Z}^{(N)}_{*}\geq
x\beta N^{\frac{1}{2}+\varepsilon}\big{)}$
$\displaystyle\leq\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}S^{(N)}\text{
hits }S^{(N)}(0)+\frac{N}{2}+x\beta N^{\frac{1}{2}+\varepsilon}\text{ before
time }\tau^{(N)}_{2}(B)\big{)}$
$\displaystyle\leq\hat{c}_{1}\exp\big{\\{}-\hat{c}_{2}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}(N^{\frac{1}{2}-\varepsilon}/(2\beta)+x)^{\frac{1}{5}}\big{\\}}+\hat{c}_{3}\exp\\{-\hat{c}_{4}(N^{\frac{1}{2}-\varepsilon}/(2\beta)+x)\\}$
$\displaystyle\leq\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}\big{(}\exp\\{-\bar{c}_{3}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}x^{\frac{1}{5}}\\}+\exp\\{-\bar{c}_{4}x\\}\big{)},$

where the second inequality is due to Lemma 3.2 upon recalling
$N^{\frac{1}{2}-\varepsilon}/(2\beta)+x>t_{0}$ by the definition of
$\bar{N}_{B}$. The last inequality is due to $(a+b)^{\frac{1}{5}}\leq
a^{\frac{1}{5}}+b^{\frac{1}{5}}$, for all $a,b\geq 0$, and $B_{1}\geq 1$.

(ii) From part (i), for $B\geq B_{1}$ and $N\geq\tilde{N}^{\prime}_{B}$,

$\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\bar{Z}^{(N)}_{*}>0\big{)}\leq
2\bar{c}_{1}\exp\big{(}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{)}.$
(3.8)

Starting from $I^{(N)}(0)=0,Q_{2}^{(N)}(0)=\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$ and any $\bar{Q}^{(N)}_{3}(0)$, on the
event $\bar{Z}^{(N)}_{*}=0$,
$\bar{Q}^{(N)}_{3}(\tau^{(N)}_{2}(B))\leq\bar{Q}^{(N)}_{3}(0)$ and
$Q_{2}^{(N)}(\tau^{(N)}_{2}(B))\leq
Q_{2}^{(N)}(0)-BN^{\frac{1}{2}+\varepsilon}+1$. Thus, we have
$S^{(N)}(\tau^{(N)}_{2}(B))\leq S^{(N)}(0)-BN^{\frac{1}{2}+\varepsilon}+1.$
Also, for all $t\geq 0$,

$\displaystyle S^{(N)}(t)\geq$ $\displaystyle S^{(N)}(0)+A((N-\beta
N^{\frac{1}{2}-\varepsilon})t)-D(Nt)$
$\displaystyle=S^{(N)}(0)+\hat{A}((N-\beta
N^{\frac{1}{2}-\varepsilon})t)-\hat{D}(Nt)-\beta
N^{\frac{1}{2}-\varepsilon}t,$

where $\hat{A}(s)=A(s)-s$ and $\hat{D}(s)=D(s)-s$. Let
$\hat{M}(s)=\hat{A}((N-\beta N^{\frac{1}{2}-\varepsilon})s)-\hat{D}(Ns)$.
Thus, by Lemma A.1, there exists a constant $\tilde{c}>0$, such that

$\begin{split}&\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(B)<\frac{B}{2\beta}N^{2\varepsilon},\bar{Z}^{(N)}_{*}=0\big{)}\\\
&\leq\mathbb{P}\big{(}\inf_{s\leq(B/2\beta)N^{2\varepsilon}}\big{(}\hat{M}(s)-\beta
N^{\frac{1}{2}-\varepsilon}s\big{)}\leq-
BN^{\frac{1}{2}+\varepsilon}+1\big{)}\\\
&\leq\mathbb{P}\big{(}\inf_{s\leq(B/2\beta)N^{2\varepsilon}}\hat{M}(s)\leq-\frac{B}{2}N^{\frac{1}{2}+\varepsilon}+1\big{)}\leq
4\exp\\{-\tilde{c}B\\}.\end{split}$ (3.9)

Furthermore, since the instantaneous rate of decrease of $\bar{Q}^{(N)}_{3}$
is at least 1 when $\bar{Q}^{(N)}_{3}$ is positive, and that
$\bar{Q}^{(N)}_{3}$ can only decrease when $\bar{Z}^{(N)}_{*}=0$, observe
that, using Lemma A.1 for Poisson processes,

$\displaystyle\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\Big{(}\bar{Q}^{(N)}_{3}(\tau^{(N)}_{2}(B))>\big{(}\bar{Q}^{(N)}_{3}(0)-\frac{B}{4\beta}N^{2\varepsilon}\big{)}_{+},\bar{Z}^{(N)}_{*}=0,\tau^{(N)}_{2}(B)\geq\frac{B}{2\beta}N^{2\varepsilon}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\mathrm{Po}\big{(}\frac{B}{2\beta}N^{2\varepsilon}\big{)}<\frac{B}{4\beta}N^{2\varepsilon}\Big{)}\leq
2e^{-c^{\prime}BN^{2\varepsilon}},\text{ for some constant }c^{\prime}>0\text{
dependent on }\beta,$ (3.10)

where $\mathrm{Po}(\frac{B}{2\beta}N^{2\varepsilon})$ is a Poisson random
variable with parameter $\frac{B}{2\beta}N^{2\varepsilon}$. Inequalities
(3.8), (3.9) and (3.2), yield

$\displaystyle\inf_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\bar{Z}^{(N)}\leq-\big{[}\bar{Q}^{(N)}_{3}(0)\wedge\frac{B}{4\beta}N^{2\varepsilon}\big{]}\big{)}$
$\displaystyle=\inf_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\bar{Q}^{(N)}_{3}(\tau^{(N)}_{2}(B))\leq\big{(}\bar{Q}^{(N)}_{3}(0)-\frac{B}{4\beta}N^{2\varepsilon}\big{)}_{+}\big{)}$
$\displaystyle\geq 1-\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\bar{Z}^{(N)}_{*}>0\big{)}-\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(B)<\frac{B}{2\beta}N^{2\varepsilon},\bar{Z}^{(N)}_{*}=0\big{)}$
$\displaystyle\qquad-\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\bar{Q}^{(N)}_{3}(\tau^{(N)}_{2}(B))>\big{(}\bar{Q}^{(N)}_{3}(0)-\frac{B}{4\beta}N^{2\varepsilon}\big{)}_{+},\bar{Z}^{(N)}_{*}=0,\tau^{(N)}_{2}(B)\geq\frac{B}{2\beta}N^{2\varepsilon}\big{)}$
$\displaystyle\geq
1-2\bar{c}_{1}\exp\big{(}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{)}-4\exp\\{-\tilde{c}B\\}-2\exp\\{-c^{\prime}BN^{2\varepsilon}\\}.$

Let $B_{2}\geq B_{1}$ such that $4\exp\\{-\tilde{c}B\\}\leq 1/4$ for all
$B\geq B_{2}$. For $B\geq B_{2}$, we can obtain
$\tilde{N}^{*}_{B}\geq\tilde{N}^{\prime}_{B}$ such that the lower bound above
is at least $1/2$. This completes the proof of the lemma. ∎

###  3.3 Down-crossing estimate.

The goal of this section is to obtain a probability bound on
$\tau^{(N)}_{2}(B)$, that is, starting from $Q^{(N)}_{2}(0)=\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$, the time taken for $Q^{(N)}_{2}$ to hit
$\lfloor BN^{\frac{1}{2}+\varepsilon}\rfloor$.

######  Proposition 3.4.

Recall $B_{1}\geq 1$ and $\tilde{N}_{B}$ for $B\geq B_{1}$ from Lemma 3.1.
There exist constants $t_{0},c^{\prime}_{i}>0$ , $i\in\\{0,1,2,3,4\\}$, such
that for any $B\geq B_{1},N\geq\tilde{N}_{B}$, and $x\geq 0$,

$\begin{split}&\sup_{\underline{z}:\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(B)\geq
N^{2\varepsilon}t\big{)}\\\ &\leq
4e^{-c^{\prime}_{0}t}+c^{\prime}_{1}\exp\\{-c^{\prime}_{2}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}t^{\frac{1}{5}}\\}+c^{\prime}_{3}N^{4\varepsilon}t\exp\\{-c^{\prime}_{4}\sqrt{B}N^{2\varepsilon}t\\},\quad\forall
t\geq t_{0}\vee\frac{8}{\beta}(B+x).\end{split}$ (3.11)

Recall the upper bounding birth-death process $\bar{I}_{B}^{(N)}$ from Section
3.1. As we will see in the proof below, the exponents in the right hand side
of (3.11) are inherited from Lemma 3.1 as we will require control over the
integral and supremum of $\bar{I}_{B}^{(N)}$ in bounding the tail probability
for $\tau^{(N)}_{2}(B)$.

###### Proof.

Proof of Proposition 3.4. Starting from
$I^{(N)}(0)=0,Q^{(N)}_{2}(0)=2BN^{\frac{1}{2}+\varepsilon},\sum_{i=3}^{\infty}Q^{(N)}_{i}(0))\leq
xN^{\frac{1}{2}+\varepsilon}$, for $t\leq\tau_{2}^{(N)}(B)$,

$\displaystyle Q_{2}^{(N)}(t)\leq$ $\displaystyle
S^{(N)}(t)-Q^{(N)}_{1}(t)=S^{(N)}(t)-(N-I^{(N)}(t))$ $\displaystyle=$
$\displaystyle S^{(N)}(0)+A\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})t\big{)}-D\big{(}Nt-\int_{0}^{t}I^{(N)}(s)ds\big{)}-N+I^{(N)}(t)$
$\displaystyle\leq$ $\displaystyle
S^{(N)}(0)-N+\bar{I}_{B}^{(N)}(t)+A\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})t\big{)}-D\big{(}Nt-\int_{0}^{t}\bar{I}_{B}^{(N)}(s)ds\big{)}$
$\displaystyle\leq$
$\displaystyle(2B+x)N^{\frac{1}{2}+\varepsilon}+\bar{I}_{B}^{(N)}(t)+\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})t\big{)}-\hat{D}\big{(}Nt-\int_{0}^{t}\bar{I}_{B}^{(N)}(s)ds\big{)}$
$\displaystyle\hskip 227.62204pt+\int_{0}^{t}\bar{I}_{B}^{(N)}(s)ds-\beta
N^{\frac{1}{2}-\varepsilon}t,$ (3.12)

where $\hat{A}(s)=A(s)-s$ and $\hat{D}(s)=D(s)-s$. Recall

$\mathcal{M}^{*}(t)=\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})t\big{)}-\hat{D}\big{(}Nt-\int_{0}^{t}\bar{I}_{B}^{(N)}(s)ds\big{)}.$

Thus, using the above upper bound for $Q_{2}^{(N)}$, we obtain

$\displaystyle\sup_{\underline{z}:\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(B)\geq
N^{2\varepsilon}t\big{)}$ $\displaystyle=$
$\displaystyle\sup_{\underline{z}:\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}Q^{(N)}_{2}(N^{2\varepsilon}t)\geq\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor\ \text{and}\ \tau^{(N)}_{2}(B)\geq
N^{2\varepsilon}t\big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\Big{(}\int_{0}^{N^{2\varepsilon}t}\bar{I}_{B}^{(N)}(s)ds\geq\frac{\beta}{2}N^{\frac{1}{2}+\varepsilon}t\Big{)}+\mathbb{P}\Big{(}\bar{I}_{B}^{(N)}(N^{2\varepsilon}t)\geq\frac{\beta}{4}N^{\frac{1}{2}+\varepsilon}t\Big{)}$
(3.13)
$\displaystyle+\mathbb{P}\Big{(}(2B+x)N^{\frac{1}{2}+\varepsilon}+\big{(}\mathcal{M}^{*}(N^{2\varepsilon}t)-\frac{\beta}{2}N^{\frac{1}{2}+\varepsilon}t\big{)}+\frac{\beta}{4}N^{\frac{1}{2}+\varepsilon}t\geq
BN^{\frac{1}{2}+\varepsilon}\Big{)}.$

Then, for $B\geq B_{1},N\geq\tilde{N}_{B},t\geq t_{0}$, by Lemma 3.1i,

$\mathbb{P}\Big{(}\int_{0}^{N^{2\varepsilon}t}\bar{I}_{B}^{(N)}(s)ds>\frac{\beta}{2}N^{\frac{1}{2}+\varepsilon}t\Big{)}\leq
c_{1}\exp\\{-c_{2}B^{\frac{1}{5}}N^{\frac{4\varepsilon}{5}}t^{\frac{1}{5}}\\},$
(3.14)

and moreover, by Lemma 3.1ii,

$\mathbb{P}\big{(}\bar{I}_{B}^{(N)}(N^{2\varepsilon}t)\geq\frac{\beta}{4}N^{\frac{1}{2}+\varepsilon}t\big{)}\leq\exp\\{-\tilde{c}_{1}BN^{4\varepsilon}t\\}+\tilde{c}_{2}N^{4\varepsilon}t\exp\\{-\tilde{c}_{3}\sqrt{B}N^{2\varepsilon}t\\}.$
(3.15)

For $t\geq\frac{8}{\beta}(B+x)$, by Lemma A.1,

$\displaystyle\mathbb{P}\Big{(}(2B+x)N^{\frac{1}{2}+\varepsilon}+\big{(}\mathcal{M}^{*}(N^{2\varepsilon}t)-\frac{\beta}{2}N^{\frac{1}{2}+\varepsilon}t\big{)}+\frac{\beta}{4}N^{\frac{1}{2}+\varepsilon}t\geq
BN^{\frac{1}{2}+\varepsilon}\Big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}\big{(}\mathcal{M}^{*}(N^{2\varepsilon}t)\geq\frac{\beta}{4}N^{\frac{1}{2}+\varepsilon}t-(B+x)N^{\frac{1}{2}+\varepsilon}\big{)}\leq\mathbb{P}\big{(}\mathcal{M}^{*}(N^{2\varepsilon}t)\geq\frac{\beta}{8}N^{\frac{1}{2}+\varepsilon}t\big{)}\leq
4e^{-c^{\prime}t},$ (3.16)

where $c^{\prime}$ is a positive constant not depending on $N$. Plugging
(3.14), (3.15) and (3.3) into (3.3) and choosing appropriate constants
complete the proof. ∎

###  3.4 Up-crossing estimate.

In this subsection, we estimate the time taken for $Q^{(N)}_{2}$ to cross the
level $2BN^{\frac{1}{2}+\varepsilon}$, starting from $(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})$, uniformly in
$x,\underline{z}$. The proof involves identifying excursions in the process
path based on the $I^{(N)}$ process falling below a certain threshold (see
(3.18)). The length of each excursion is controlled using Lemma 3.5. During
each excursion, it is shown that $Q_{2}^{(N)}$ hits the level
$2BN^{\frac{1}{2}+\varepsilon}$ with a positive probability that does not
depend on $N$. This leads to a geometric number of such excursions required
for $Q_{2}^{(N)}$ to hit the level $2BN^{\frac{1}{2}+\varepsilon}$. These
estimates are combined to prove Proposition 3.6, the main result of this
subsection.

Recall $\tau^{(N)}_{1}(2\beta)=\inf\\{t\geq 0:I^{(N)}(t)=\lfloor 2\beta
N^{\frac{1}{2}-\varepsilon}\rfloor\\}$. We will write
$\underline{Q}^{(N)}_{3}:=(Q_{3}^{(N)},Q_{4}^{(N)},\dots)$.

######  Lemma 3.5.

Assume $I^{(N)}(0)=x$, $Q^{(N)}_{2}(0)=y$, and
$\underline{Q}^{(N)}_{3}(0)=\underline{z}$. For any $N$ such that $\lfloor
2\beta N^{\frac{1}{2}-\varepsilon}\rfloor\geq 1$ and any $x\geq 2\beta
N^{\frac{1}{2}-\varepsilon}$,

$\sup_{y,\underline{z}}\mathbb{E}_{(x,y,\underline{z})}\big{(}e^{\tau^{(N)}_{1}(2\beta)/2}\big{)}\leq\frac{x}{\lfloor
2\beta N^{\frac{1}{2}-\varepsilon}\rfloor},$

where
$\mathbb{E}_{(x,y,\underline{z})}(\cdot)=\mathbb{E}(\cdot|I^{(N)}(0)=x,Q^{(N)}_{2}(0)=y,\underline{Q}^{(N)}_{3}(0)=\underline{z})$.

###### Proof.

Proof. Define $W^{(N)}(t)=e^{\frac{t}{2}}I^{(N)}(t)$. Since the rate of
increase of $I^{(N)}(t)$ is at most $N-I^{(N)}(t)$ and the rate of decrease is
$N-\beta N^{\frac{1}{2}-\varepsilon}$ if $I^{(N)}(t)>0$, therefore

$\displaystyle\mathcal{L}W^{(N)}(t)$
$\displaystyle\leq\frac{1}{2}W^{(N)}(t)+e^{\frac{t}{2}}\big{[}(N-I^{(N)}(t))-(N-\beta
N^{\frac{1}{2}-\varepsilon})\big{]}$
$\displaystyle=e^{\frac{t}{2}}\big{(}-\frac{1}{2}I^{(N)}(t)+\beta
N^{\frac{1}{2}-\varepsilon}\big{)},$

where $\mathcal{L}(\cdot)$ is the infinitesimal generator. For
$t<\tau^{(N)}_{1}(2\beta)$, $\beta
N^{\frac{1}{2}-\varepsilon}\leq\frac{I^{(N)}(t)}{2}$, and so
$\mathcal{L}W^{(N)}(t)\mathds{1}\big{[}t<\tau^{(N)}_{1}(2\beta)\big{]}\leq 0.$
This implies that for all $y,\underline{z}\geq 0$,

$\mathbb{E}_{(x,y,\underline{z})}(W^{(N)}(t\wedge\tau^{(N)}_{1}(2\beta)))\leq\mathbb{E}_{(x,y,\underline{z})}(W^{(N)}(0))=x,\quad\forall
t\geq 0.$

By Fatou’s lemma and the observation that, almost surely,
$(t\wedge\tau^{(N)}_{1}(2\beta))=\tau^{(N)}_{1}(2\beta)$ for sufficiently
large $t$, we have that for all $y,\underline{z}\geq 0$,

$\mathbb{E}_{(x,y,\underline{z})}(W^{(N)}(\tau^{(N)}_{1}(2\beta)))\leq\liminf_{t\rightarrow\infty}\mathbb{E}(W^{(N)}(t\wedge\tau^{(N)}_{1}(2\beta)))\leq
x,$ (3.17)

and therefore,
$\sup_{y,\underline{z}}\mathbb{E}_{(x,y,\underline{z})}\big{(}e^{\tau^{(N)}_{1}(2\beta)/2}\big{)}\leq\frac{x}{\lfloor
2\beta N^{\frac{1}{2}-\varepsilon}\rfloor}.$ ∎

######  Proposition 3.6.

For any fixed $B>0$, there exist $p_{B},t^{\prime}_{B},N^{\prime}_{B}>0$ such
that $\forall t\geq t^{\prime}_{B},N\geq N^{\prime}_{B}$,

${\color[rgb]{0,0,0}\sup_{x,\underline{z}}\mathbb{P}_{(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(2B)>N^{2\varepsilon}t\big{)}\leq\frac{\sqrt{t}N^{\frac{1}{2}+\varepsilon}}{2\beta}\exp\\{-N^{2\varepsilon}\sqrt{t}/2\\}+(1-p_{B})^{\lfloor\sqrt{t}/2\rfloor}.}$

We outline the idea of the proof here. For $Q_{2}^{(N)}$ to exceed level
$\lfloor 2BN^{\frac{1}{2}+\varepsilon}\rfloor$, $I^{(N)}$ has to first become
small (fall below $\lfloor 2\beta N^{\frac{1}{2}-\varepsilon}\rfloor$). The
time taken for this is quantified by Lemma 3.5. The first term in the right
hand side above arises from bounding the probability of less than
$\lfloor\sqrt{t}/2\rfloor$ many such ‘returns’ of $I^{(N)}$ to $\lfloor 2\beta
N^{\frac{1}{2}-\varepsilon}\rfloor$ before time $N^{2\varepsilon}t$. Each time
$I^{(N)}$ becomes small, the fluctuation in the arrival and departure
processes ensures that with at least positive probability $p_{B}$, the total
queue length $S^{(N)}$ (and hence $Q_{2}^{(N)}$) exceeds $\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$ within the next $N^{2\varepsilon}$ time
units. Thus, if there are at least $\lfloor\sqrt{t}/2\rfloor$ returns of
$I^{(N)}$ by time $N^{2\varepsilon}t$, the probability of $Q_{2}^{(N)}$ not
hitting $\lfloor 2BN^{\frac{1}{2}+\varepsilon}\rfloor$ in any of the time
intervals of length $N^{2\varepsilon}$ following such returns is at least
$(1-p_{B})^{\lfloor\sqrt{t}/2\rfloor}$, giving the second term in the above
bound.

###### Proof.

Proof of Proposition 3.6. Define the stopping times:
$\theta^{(N)}_{0}\coloneqq 0$ and for $k\geq 0$,

$\displaystyle\theta^{(N)}_{2k+1}\coloneqq\inf\\{t\geq\theta^{(N)}_{2k}:I^{(N)}(t)\leq\lfloor
2\beta N^{\frac{1}{2}-\varepsilon}\rfloor\\},$ (3.18)
$\displaystyle\theta^{(N)}_{2k+2}\coloneqq\theta^{(N)}_{2k+1}+N^{2\varepsilon}.$
(3.19)

Note that if $I^{(N)}(\theta^{(N)}_{2k})\leq\lfloor 2\beta
N^{\frac{1}{2}-\varepsilon}\rfloor$, then
$\theta^{(N)}_{2k+1}=\theta^{(N)}_{2k}$; equivalently, if
$\theta^{(N)}_{2k+1}-\theta^{(N)}_{2k}>0$, then
$I^{(N)}(\theta^{(N)}_{2k})>\lfloor 2\beta
N^{\frac{1}{2}-\varepsilon}\rfloor$. Thus, for any $k\geq 0$ and $t\geq 0$,
any $N$ such that $\lfloor 2\beta N^{\frac{1}{2}-\varepsilon}\rfloor\geq 1$,

$\begin{split}\mathbb{P}\big{(}\theta^{(N)}_{2k+1}-\theta^{(N)}_{2k}>N^{2\varepsilon}t\big{)}&\leq\sup_{x>\lfloor
2\beta
N^{\frac{1}{2}-\varepsilon}\rfloor,y,\underline{z}}\mathbb{P}_{(x,y,\underline{z})}\big{(}\tau^{(N)}_{1}(2\beta)>N^{2\varepsilon}t\big{)}\\\
&\leq
e^{-N^{2\varepsilon}t/2}\sup_{x}\sup_{y,\underline{z}}\mathbb{E}_{(x,y,\underline{z})}\big{(}e^{\tau_{1}(2\beta)/2}\big{)}\leq\frac{N}{\lfloor
2\beta
N^{\frac{1}{2}-\varepsilon}\rfloor}\exp\\{-N^{2\varepsilon}t/2\\},\end{split}$
(3.20)

where the last inequality is due to Lemma 3.5 and $x\leq N$. Next, we claim
the following:

######  Claim 3.7.

Fix any
$N>\max\\{(5B)^{-(\frac{1}{2}-\varepsilon)},(2\beta/B)^{\frac{1}{2\varepsilon}}\\}$.
For any $k\geq 0$, the following inclusion relation holds on the event
$\sup_{s\in[0,\theta^{(N)}_{2k+1}]}Q^{(N)}_{2}(s)<2BN^{\frac{1}{2}+\varepsilon}:$

$\displaystyle\Big{\\{}\sup_{s\in[\theta^{(N)}_{2k+1},\theta^{(N)}_{2k+2}]}S^{(N)}(s)\geq
3BN^{\frac{1}{2}+\varepsilon}+S^{(N)}(\theta^{(N)}_{2k+1})\Big{\\}}\subseteq\Big{\\{}\sup_{s\in[\theta^{(N)}_{2k+1},\theta^{(N)}_{2k+2}]}Q^{(N)}_{2}(s)\geq
2BN^{\frac{1}{2}+\varepsilon}\Big{\\}},$ (3.21)

_Proof._ Suppose that for some $k\geq 0$,
$\sup_{s\in[0,\theta^{(N)}_{2k+1}]}Q^{(N)}_{2}(s)<2BN^{\frac{1}{2}+\varepsilon}$
and $\exists s\in[\theta^{(N)}_{2k+1},\theta^{(N)}_{2k+2}]$ such that
$S^{(N)}(s)\geq 3BN^{\frac{1}{2}+\varepsilon}+S^{(N)}(\theta^{(N)}_{2k+1})$.
Let
$\bar{s}\coloneqq\inf\\{s\in[\theta^{(N)}_{2k+1},\theta^{(N)}_{2k+2}]:S^{(N)}(s)\geq
3BN^{\frac{1}{2}+\varepsilon}+S^{(N)}(\theta^{(N)}_{2k+1})\\}.$ Since
$N>5BN^{\frac{1}{2}+\varepsilon}$, we claim that
$\bar{Q}^{(N)}_{3}(\bar{s})\leq\bar{Q}^{(N)}_{3}(\theta^{(N)}_{2k+1})$. If
this was not the case, $\bar{s}>\theta^{(N)}_{2k+1}$ and there would be
$\tilde{s}\in[\theta_{2k+1},\bar{s})$ such that $\tilde{s}$ is a ‘point of
increase’ of $\bar{Q}_{3}^{(N)}$, that is, $Q_{2}^{(N)}(\tilde{s})=N$,
$\bar{Q}_{3}^{(N)}(\tilde{s})=\bar{Q}_{3}^{(N)}(\theta^{(N)}_{2k+1})$ and
$I^{(N)}(\tilde{s})=0$. Hence, recalling that
$\sup_{s\in[0,\theta^{(N)}_{2k+1}]}Q^{(N)}_{2}(s)<2BN^{\frac{1}{2}+\varepsilon}$,

$\displaystyle S^{(N)}(\tilde{s})$
$\displaystyle=N+\bar{Q}_{3}^{(N)}(\theta^{(N)}_{2k+1})+N\geq
N-2BN^{\frac{1}{2}+\varepsilon}+Q^{(N)}_{2}(s)+\bar{Q}_{3}^{(N)}(\theta^{(N)}_{2k+1})+(N-I^{(N)}(\theta^{(N)}_{2k+1}))$
$\displaystyle=N-2BN^{\frac{1}{2}+\varepsilon}+S^{(N)}(\theta^{(N)}_{2k+1})>3BN^{\frac{1}{2}+\varepsilon}+S^{(N)}(\theta^{(N)}_{2k+1}),$

which is a contradiction to the fact that $\tilde{s}<\bar{s}$. Hence, we
conclude that $N>5BN^{\frac{1}{2}+\varepsilon}$ implies
$\bar{Q}^{(N)}_{3}(\bar{s})\leq\bar{Q}^{(N)}_{3}(\theta^{(N)}_{2k+1})$. Using
this observation and the definition of $\bar{s}$, we obtain

$\displaystyle 3BN^{\frac{1}{2}+\varepsilon}=$ $\displaystyle
S^{(N)}(\bar{s})-S^{(N)}(\theta^{(N)}_{2k+1})$ $\displaystyle=$
$\displaystyle\big{(}Q^{(N)}_{2}(\bar{s})+\bar{Q}^{(N)}_{3}(\bar{s})+N-I^{(N)}(\bar{s})\big{)}-\big{(}Q^{(N)}_{2}(\theta^{(N)}_{2k+1})+\bar{Q}^{(N)}_{3}(\theta^{(N)}_{2k+1})+N-I^{(N)}(\theta^{(N)}_{2k+1})\big{)}$
$\displaystyle\leq$ $\displaystyle
Q_{2}^{(N)}(\bar{s})-Q_{2}^{(N)}(\theta^{(N)}_{2k+1})+I^{(N)}(\theta^{(N)}_{2k+1})\leq
Q_{2}^{(N)}(\bar{s})-Q_{2}^{(N)}(\theta^{(N)}_{2k+1})+2\beta
N^{\frac{1}{2}-\varepsilon}.$

Further, note that $2\beta
N^{\frac{1}{2}-\varepsilon}<BN^{\frac{1}{2}+\varepsilon}$, due to the choice
of $N$. Thus, the above yields $Q^{(N)}_{2}(\bar{s})\geq
Q^{(N)}_{2}(\theta^{(N)}_{2k+1})+2BN^{\frac{1}{2}+\varepsilon}\geq
2BN^{\frac{1}{2}+\varepsilon}.$ This completes the proof of Claim 3.7.

Therefore, due to Claim 3.7,

$\displaystyle\inf_{x,\underline{z}}\mathbb{P}_{(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\Big{(}\sup_{s\in[\theta^{(N)}_{2k+1},\theta^{(N)}_{2k+2}]}Q^{(N)}_{2}(s)\geq
2BN^{\frac{1}{2}+\varepsilon}\,|\,Q^{(N)}_{2}(\theta^{(N)}_{2k+1})<2BN^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle\geq\inf_{x,\underline{z}}\mathbb{P}_{(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\Big{(}\sup_{s\in[\theta^{(N)}_{2k+1},\theta^{(N)}_{2k+2}]}(S^{(N)}(s)-S^{(N)}(\theta^{(N)}_{2k+1}))\geq
3BN^{\frac{1}{2}+\varepsilon}\,|\,Q^{(N)}_{2}(\theta^{(N)}_{2k+1})<2BN^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle\geq\mathbb{P}\Big{(}\sup_{s\in[0,N^{2\varepsilon}]}A\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})s\big{)}-D\big{(}Ns\big{)}\geq
3BN^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\sup_{s\in[0,N^{2\varepsilon}]}\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})s\big{)}-\hat{D}\big{(}Ns\big{)}-\beta
N^{\frac{1}{2}-\varepsilon}s\geq 3BN^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle\geq\mathbb{P}\Big{(}\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})N^{2\varepsilon}\big{)}-\hat{D}\big{(}N^{1+2\varepsilon}\big{)}-\beta
N^{\frac{1}{2}+\varepsilon}\geq 3BN^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}N^{-\frac{1}{2}-\varepsilon}\big{(}\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})N^{2\varepsilon}\big{)}-\hat{D}\big{(}N^{1+2\varepsilon}\big{)}\big{)}-\beta\geq
3B\Big{)}$ $\displaystyle\geq p_{B}>0,\text{ for sufficient large }N.$ (3.22)

Observe that $p_{B}$ does not depend on $N$ since
$N^{-\frac{1}{2}-\varepsilon}\big{(}\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})N^{2\varepsilon}\big{)}-\hat{D}\big{(}N^{1+2\varepsilon}\big{)}\big{)}\xrightarrow{\
\mathbb{P}\ }N(0,2)$ by the Martingale FCLT. Therefore, for sufficiently large
$N,t$,

$\displaystyle\sup_{x,\underline{z}}\mathbb{P}_{(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(2B)>N^{2\varepsilon}t\big{)}\leq\sum_{k=0}^{\lfloor\sqrt{t}/2\rfloor}\sup_{x,\underline{z}}\mathbb{P}_{(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\theta^{(N)}_{2k+1}-\theta^{(N)}_{2k}>N^{2\varepsilon}\sqrt{t}\big{)}$
$\displaystyle+\sup_{x,\underline{z}}\mathbb{P}_{(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\sup_{s\in[\theta^{(N)}_{2k+1},\theta^{(N)}_{2k+2}]}Q^{(N)}_{2}(s)<2BN^{\frac{1}{2}+\varepsilon},Q^{(N)}_{2}(\theta^{(N)}_{2k+1})<2BN^{\frac{1}{2}+\varepsilon},\forall\
k\leq\lfloor\sqrt{t}/2\rfloor\big{)}$ $\displaystyle\leq$
$\displaystyle\frac{\sqrt{t}N^{\frac{1}{2}+\varepsilon}}{2\beta}\exp\\{-N^{2\varepsilon}\sqrt{t}/2\\}+(1-p_{B})^{\lfloor\sqrt{t}/2\rfloor},$

where the last inequality is due to (3.20) and (3.4). ∎

###  3.5 Supremum of $Q^{(N)}_{2}$.

In this section, we will give bounds on the supremum of the process
$Q^{(N)}_{2}(\cdot)$ on a time interval $[0,N^{2\varepsilon}T]$ for fixed
$T>0$. This bound will be used in Section 4 to show that,
$\bar{Q}^{(N)}_{3}(\infty)\xrightarrow{P}0$ as $N\rightarrow\infty$. It will
also be used for the process-level convergence proofs in Sections 5 and 6. In
particular, it is a key tool in proving Proposition 5.6. Let $I^{(N)}(0)=0$,
$Q^{(N)}_{2}(0)=\lfloor 2BN^{\frac{1}{2}+\varepsilon}\rfloor$, and
$Q^{(N)}_{3}(0)=0$. Recall $\sigma^{(N)}_{i}$ and $K^{(N)}_{T}$ from (2.6) and
fix $B\geq(B_{1}\vee 2\beta\vee 5)$, where $B_{1}$ was introduced in Lemma
3.1. The next lemma bounds the supremum of $Q^{(N)}$ on
$[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]$ for $i\geq 0$. Proof is given in
Appendix C.

######  Lemma 3.8.

Recall $\tilde{N}_{B}$ from Lemma 3.1. There exist $x_{B}\geq 2B$ such that
for all $i\geq 0$, $N\geq\tilde{N}_{B}$, $N^{\frac{1}{2}-\varepsilon}\geq
x\geq x_{B}$,

$\mathbb{P}\Big{(}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{2}(s)\geq
xN^{\frac{1}{2}+\varepsilon}\ \Big{|}\
Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}\leq
c^{*}_{1}\exp\\{-c^{*}_{2}x\\}+c^{*}_{3}\exp\\{-c^{*}_{4}N^{\frac{4\varepsilon}{5}}x^{\frac{1}{5}}\\},$

where $c^{*}_{j}$, $j\in\\{1,2,3,4\\}$, are constants that do not depend on
$i,N,x$.

######  Proposition 3.9.

There exist constants $x^{\prime}$, $N^{\prime}>0$, $\bar{c}^{\prime}$,
$\bar{c}_{1}$, $\bar{c}_{2}$ and $c^{*}_{i},i=\\{1,2,3,4\\}$, depending only
on $B$, such that for all $N\geq N_{B}$, $x\geq x^{\prime}_{B}$, $T\geq
x^{-1}$,

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sup_{s\in[0,N^{2\varepsilon}T]}Q^{(N)}_{2}(s)\geq
xN^{\frac{1}{2}+\varepsilon}\Big{)}$ $\displaystyle\leq$
$\displaystyle\exp\\{-\bar{c}^{\prime}Tx\\}+Tx\big{(}\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}+c^{*}_{1}\exp\\{-c^{*}_{2}x\\}+c^{*}_{3}\exp\\{-c^{*}_{4}N^{\frac{4\varepsilon}{5}}x^{\frac{1}{5}}\\}\big{)}.$

###### Proof.

Proof of Proposition 3.9. Define
$\phi^{(N)}_{i}=\mathds{1}[\sigma^{(N)}_{2i+1}-\sigma^{(N)}_{2i}\geq
N^{2\varepsilon}]$, $i\geq 1$. For $i\geq 1$, $s\geq 0$,

$\begin{split}&S^{(N)}(s+\sigma^{(N)}_{2i})=N+\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor+\bar{Q}^{(N)}_{3}(\sigma^{(N)}_{2i})\\\
&\quad+\left[A\left((N-\beta
N^{\frac{1}{2}-\varepsilon})(s+\sigma^{(N)}_{2i})\right)-A\left((N-\beta
N^{\frac{1}{2}-\varepsilon})\sigma^{(N)}_{2i}\right)\right]-D\left(\int_{\sigma^{(N)}_{2i}}^{\sigma^{(N)}_{2i}+s}(N-I^{(N)}(u))du\right)\\\
&=N+\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor+\bar{Q}^{(N)}_{3}(\sigma^{(N)}_{2i})+\int_{\sigma^{(N)}_{2i}}^{\sigma^{(N)}_{2i}+s}I^{(N)}(u)du-\beta
N^{\frac{1}{2}-\varepsilon}s\\\ &+\left[\hat{A}\left((N-\beta
N^{\frac{1}{2}-\varepsilon})(s+\sigma^{(N)}_{2i})\right)-\hat{A}\left((N-\beta
N^{\frac{1}{2}-\varepsilon})\sigma^{(N)}_{2i}\right)\right]-\hat{D}\left(\int_{\sigma^{(N)}_{2i}}^{\sigma^{(N)}_{2i}+s}(N-I^{(N)}(u))du\right).\end{split}$
(3.23)

where $\hat{A}(s)=A(s)-s$ and $\hat{D}(s)=D(s)-s$. Recall that
$\hat{\mathcal{M}}(s)=\hat{A}\left((N-\beta
N^{\frac{1}{2}-\varepsilon})s\right)-\hat{D}\left(\int_{0}^{s}(N-I^{(N)}(u))du\right)$
for $s\geq 0.$ For $i\geq 1$, $B\geq(2\beta\vee 5)$,

$\displaystyle\mathbb{P}\Big{(}\phi^{(N)}_{i}=0\ \Big{|}\
Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}\leq\mathbb{P}\Big{(}\inf_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i}+N^{2\varepsilon}]}Q^{(N)}_{2}(s)\leq\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor\ \Big{|}\
Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\inf_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i}+N^{2\varepsilon}]}Q_{2}^{(N)}(s)\leq\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{3}(s)=0\
\Big{|}\ Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}$ $\displaystyle\hskip
113.81102pt+\mathbb{P}\Big{(}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{3}(s)>0\
\Big{|}\ Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\inf_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i}+N^{2\varepsilon}]}S^{(N)}(s)\leq
N+\lfloor BN^{\frac{1}{2}+\varepsilon}\rfloor\ \Big{|}\
Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}$ $\displaystyle\hskip
113.81102pt+\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sup_{s\in[0,\tau_{2}^{(N)}(B)]}\bar{Q}^{(N)}_{3}(s)>0\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\inf_{s\in[0,N^{2\varepsilon}]}(\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor+\hat{\mathcal{M}}(s)-\beta
N^{\frac{1}{2}-\varepsilon}s)\leq\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor\Big{)}+\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}$
$\displaystyle\leq\mathbb{P}\Big{(}\inf_{s\in[0,N^{2\varepsilon}]}\hat{\mathcal{M}}(s)\leq-\frac{B}{2}N^{\frac{1}{2}+\varepsilon}\Big{)}+\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}$
$\displaystyle\leq\frac{8N^{1+2\varepsilon}}{B^{2}N^{1+2\varepsilon}}+\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}\leq\frac{1}{2},\text{
for sufficient large }N,$

where the third inequality uses the strong Markov property for the second term
and the observation that $S^{(N)}(s)\leq N+Q_{2}^{(N)}(s)$ if
$Q_{3}^{(N)}(s)=0$ for the first term. The fourth inequality is due to the
strong Markov property, (3.23) and Lemma 3.3 (on taking a limit as
$x\downarrow 0$), and the last inequality follows from Doob’s $L^{2}$-maximal
inequality. Thus, $\mathbb{E}(\phi^{(N)}_{i}\ |\
Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0)\geq 1/2$ for sufficiently large $N$. Now,
for $T>0$, recall $K^{(N)}_{T}=\inf\big{\\{}k:\bar{\sigma}^{(N)}_{2k}\geq
N^{2\varepsilon}T\big{\\}}$. By Azuma’s inequality and Lemma 3.3, taking
$a\geq 8$, $T\geq a^{-1}$, for sufficiently large $N$,

$\begin{split}&\mathbb{P}\Big{(}K^{(N)}_{T}\geq aT\Big{)}\\\
&\leq\mathbb{P}\Big{(}\sum_{i=1}^{\lfloor
aT\rfloor}(\sigma^{(N)}_{2i+1}-\sigma^{(N)}_{2i})\leq
N^{2\varepsilon}T\Big{)}\\\ &\leq\mathbb{P}\Big{(}\sum_{i=1}^{\lfloor
aT\rfloor}\phi^{(N)}_{i}\leq T\ \ \text{and}\
\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{3}(s)=0,\forall
1\leq i\leq\lfloor aT\rfloor\Big{)}\\\ &\hskip
227.62204pt+\mathbb{P}\Big{(}\exists 1\leq i\leq\lfloor
aT\rfloor,\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{3}(s)>0\Big{)}\end{split}$
$\begin{split}&\leq\mathbb{P}\bigg{(}\sum_{i=1}^{\lfloor
aT\rfloor}\Big{(}\phi^{(N)}_{i}-\mathbb{E}(\phi^{(N)}_{i}\ |\
Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0)\Big{)}\leq-\frac{aT}{8}\\\ &\hskip
142.26378pt\text{and}\
\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{3}(s)=0,\ \forall
1\leq i\leq\lfloor aT\rfloor\bigg{)}\\\ &\hskip
142.26378pt+aT\cdot\sup_{i}\mathbb{P}\Big{(}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{3}(s)>0\,\Big{|}\,Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}\\\
&\leq
e^{-\bar{c}^{\prime}aT}+aT\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}.\end{split}$
(3.24)

Take $a=x$. Then, using (3.5), Lemma 3.8, and union bound, for
$N\geq\tilde{N}_{B}$, $N^{\frac{1}{2}-\varepsilon}\geq x\geq(x_{B}\vee 8)$,
$T\geq x^{-1}$,

$\displaystyle\mathbb{P}\Big{(}\sup_{s\in[0,N^{2\varepsilon}T]}Q^{(N)}_{2}(s)\geq
xN^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}K^{(N)}_{T}\geq
xT\Big{)}+Tx\cdot\sup_{i}\mathbb{P}\Big{(}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+1}]}Q^{(N)}_{2}\geq
xN^{\frac{1}{2}+\varepsilon}\ \Big{|}\
Q^{(N)}_{3}(\sigma^{(N)}_{2i})=0\Big{)}$
$\displaystyle\leq\exp\\{-\bar{c}^{\prime}Tx\\}+Tx\Big{(}\bar{c}_{1}\exp\big{\\{}-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}}+c^{*}_{1}\exp\\{-c^{*}_{2}x\\}+c^{*}_{3}\exp\\{-c^{*}_{4}N^{\frac{4\varepsilon}{5}}x^{\frac{1}{5}}\\}\Big{)}.$

This proves the proposition.

∎

##  4 Steady state analysis.

Our goal is to identify points in the state space which are hit infinitely
often by the process and the length between successive hitting times has a
finite expectation. This will provide a renewal-theoretic representation of
the stationary measure.

Fix $\varepsilon\in[0,1/2)$. Throughout this section, we will choose and fix a
number $B=B_{0}$ as the maximum of the lower bounds on $B$ given in the
results in Section 3. In Section 4.1, we will formally define certain renewal
times in the process path and obtain estimates on their first and second
moments (Proposition 4.3). In Section 4.2, these estimates will be used to
obtain a renewal representation (2.7) for the stationary measure of
$(I^{(N)}(\cdot),\\{Q^{(N)}_{i}(\cdot)\\}_{i\geq 2})$ and will be combined
with the sample path analysis of Section 3 to prove Theorem 2.4.

###  4.1 Renewal times and their moment bounds.

Recall $\sigma^{(N)}_{i},\bar{K}^{(N)}$ and $\Theta^{(N)}$ from (2.6). The
next lemma gives a probability bound on $\bar{K}^{(N)}$. Starting from
$(0,\lfloor 2BN^{\frac{1}{2}+\varepsilon}\rfloor,\underline{0})$, if
$Q^{(N)}_{2}$ hits $\lfloor BN^{\frac{1}{2}+\varepsilon}\rfloor$ without
making $\bar{Q}^{(N)}_{3}$ positive, then $\bar{K}^{(N)}=1$. In fact, as
discussed in Section 3.2, this trajectory occurs with high probability for
large $N$. However, on the event where $\bar{K}^{(N)}>1$ (implying
$\bar{Q}^{(N)}_{3}$ becomes positive before time $\sigma^{(N)}_{1}$), it could
take a potentially large number of ‘toggles’ of $Q^{(N)}_{2}$ between the
levels $\lfloor BN^{\frac{1}{2}+\varepsilon}\rfloor$ and $\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor$ for $\bar{Q}^{(N)}_{3}$ to drop back to
zero. This is reflected in the statement of the lemma; note the additive
$k+k^{2}N^{\frac{1}{2}-\varepsilon}$ term within the probability statement.

######  Lemma 4.1.

There exist $N_{0},c^{*}_{1},c^{*}_{2}>0$, such that for all $N\geq
N_{0},k\geq 1$,

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\bar{K}^{(N)}\geq
1+k+k^{2}N^{\frac{1}{2}-\varepsilon}\big{)}\leq
kc^{*}_{1}\exp\big{\\{}-c^{*}_{2}N^{(\frac{1}{2}-\varepsilon)/11}\big{\\}}\exp\Big{\\{}-c^{*}_{2}\big{(}k/N^{\frac{1}{2}-\varepsilon}\big{)}^{\frac{1}{11}}\Big{\\}}+2^{-k}.$

Lemma 4.1 is proved in Appendix D. At the heart of the proof is Lemma 3.3
which quantifies the increments of $\bar{Q}^{(N)}_{3}$ on the excursion
intervals $[\sigma_{2i}^{(N)},\sigma_{2i+2}^{(N)}]$. In particular, it shows
that with probability at least $1/2$, $\bar{Q}^{(N)}_{3}$ decreases by
$\frac{B}{4\beta}N^{2\varepsilon}$ or more during each such excursion until
$\bar{Q}^{(N)}_{3}$ is $O(N^{2\varepsilon})$. This is the content of Lemma
D.1. Using this observation, it is shown that over a sufficiently large number
of such excursion intervals, $\bar{Q}^{(N)}_{3}$ drops to zero with high
probability. From Lemma 3.3, note that the supremum of $\bar{Q}^{(N)}_{3}$ on
$[\sigma_{2i}^{(N)},\sigma_{2i+2}^{(N)}]$ has a stretched-exponential tail.
The constant $1/11$ in the exponent above thus appears due to the use of
concentration inequality for sums of independent random variables with
stretched-exponential tails (Lemma A.2) in this setup.

Recall $\Theta^{(N)}=\sigma^{(N)}_{2\bar{K}^{(N)}}$. To obtain bounds on the
first and second moments of $\Theta^{(N)}$, we will first establish a tail
bound for $\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}>N^{2\varepsilon}t\big{)}$.
The next lemma combines the bound on the number of excursions obtained in
Lemma 4.1 with the sample path estimates from Section 3 to provide the
necessary tail estimates.

######  Lemma 4.2.

There exist constants $\bar{c}_{1},\bar{c}_{2},N_{0},t_{0}>0$, such that for
all $N\geq N_{0},t\geq t_{0}$,

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}>N^{2\varepsilon}t\big{)}\leq\bar{c}_{1}e^{-\bar{c}_{2}t^{1/5}}+\bar{c}_{1}e^{-\bar{c}_{2}N^{(\frac{1}{2}-\varepsilon)/11}}e^{-\bar{c}_{2}\big{(}\frac{t}{N^{4(1/2-\varepsilon)}}\big{)}^{1/44}}.$

###### Proof.

Proof. Note that for any $k\geq 1$,

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}>N^{2\varepsilon}t\big{)}$
$\displaystyle\leq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2}>N^{2\varepsilon}t/2\big{)}+\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\bar{K}^{(N)}>1+k+k^{2}N^{\frac{1}{2}-\varepsilon}\big{)}$
(4.1) $\displaystyle\quad+\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2\bar{K}^{(N)}}-\sigma^{(N)}_{2}>N^{2\varepsilon}t/2,1<\bar{K}^{(N)}\leq
1+k+k^{2}N^{\frac{1}{2}-\varepsilon}\big{)}.$

We will upper bound each of the terms on the RHS above. Note that there exist
$t_{0},N_{0}>0$, such that for all $N\geq N_{0},x>0$ and $t\geq t_{0}\vee
8\beta^{-1}(B+x)$,

$\displaystyle\sup_{\underline{z}:\,\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\sigma^{(N)}_{2}>N^{2\varepsilon}t/2\big{)}$
$\displaystyle\leq\sup_{\underline{z}:\,\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\sigma^{(N)}_{1}>N^{2\varepsilon}t/4\big{)}$
$\displaystyle\qquad+\sup_{\underline{z}:\,\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\sigma^{(N)}_{2}>N^{2\varepsilon}t/2,\sigma^{(N)}_{1}\leq
N^{2\varepsilon}t/4\big{)}$ (4.2)
$\displaystyle\leq\sup_{\underline{z}:\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(B)\geq
N^{2\varepsilon}t/4\big{)}+\sup_{x,\underline{z}}\mathbb{P}_{(x,\,\lfloor
BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\tau^{(N)}_{2}(2B)>N^{2\varepsilon}t/4\big{)}$
$\displaystyle\leq
ce^{-c^{\prime}\sqrt{t}}+ce^{-c^{\prime}N^{\frac{4\varepsilon}{5}}t^{1/5}},$

where the last inequality is from Proposition 3.4 and Proposition 3.6 and by
collecting the leading order terms. Write
$l(k,N)=1+k+k^{2}N^{\frac{1}{2}-\varepsilon}$ and recall
$\bar{Z}^{(N)}_{j}=\bar{Q}^{(N)}_{3}(\sigma_{2j+2})-\bar{Q}^{(N)}_{3}(\sigma_{2j})$.
Then we have for any $x>0$,

$\begin{split}&\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2\bar{K}^{(N)}}-\sigma^{(N)}_{2}>N^{2\varepsilon}t/2,1<\bar{K}^{(N)}\leq
l(k,N)\big{)}\\\ \leq&\sum_{j=1}^{l(k,N)}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2j+2}-\sigma^{(N)}_{2j}>\frac{N^{2\varepsilon}t}{2l(k,N)},\bar{Z}^{(N)}_{0}>0\big{)}\\\
\leq&\sum_{j=1}^{l(k,N)}\left(\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\bar{Z}^{(N)}_{j}>xN^{\frac{1}{2}+\varepsilon}\big{)}\right.\\\
&\qquad\quad\left.+\,\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2j+2}-\sigma^{(N)}_{2j}>\frac{N^{2\varepsilon}t}{2l(k,N)},\bar{Z}^{(N)}_{0}>0,\bar{Z}^{(N)}_{j}\leq
xN^{\frac{1}{2}+\varepsilon}\big{)}\right).\end{split}$ (4.3)

By Lemma 3.3 (i), for all large enough $N$,

$\sum_{j=1}^{l(k,N)}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\bar{Z}^{(N)}_{j}>xN^{\frac{1}{2}+\varepsilon}\big{)}\leq
c_{1}l(k,N)e^{-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}}e^{-c_{2}x^{1/5}}.$ (4.4)

Also, for all $N$ large enough, $1\leq j\leq l(k,N)$, $x>0$ and
$t\geq[t_{0}\vee 8\beta^{-1}(B+x)]l(k,N)$,

$\begin{split}&\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2j+2}-\sigma^{(N)}_{2j}>\frac{N^{2\varepsilon}t}{2l(k,N)},\bar{Z}^{(N)}_{0}>0,\bar{Z}^{(N)}_{j}\leq
xN^{\frac{1}{2}+\varepsilon}\big{)}\\\ &\quad\leq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\bar{Z}^{(N)}_{0}>0\big{)}\cdot\sup_{\underline{z}:\,\sum_{i}z_{i}\leq
xN^{\frac{1}{2}+\varepsilon}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\big{(}\sigma^{(N)}_{2}>\frac{N^{2\varepsilon}t}{2l(k,N)}\big{)}\\\
&\quad\leq
c_{1}e^{-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}}\big{[}ce^{-c^{\prime}\big{(}\frac{t}{l(k,N)}\big{)}^{1/2}}+ce^{-c^{\prime}N^{\frac{4\varepsilon}{5}}\big{(}\frac{t}{l(k,N)}\big{)}^{1/5}}\big{]},\end{split}$
(4.5)

where the first inequality is due to the strong Markov property and the last
inequality is due to Lemma 3.3 (on taking a limit as $x\downarrow 0$) and
(4.1). Hence, taking $x=\frac{t}{2l(k,N)}$ and using (4.4) and (4.5) in (4.3),
we have for $t\geq 2(t_{0}+8\beta^{-1}B)l(k,N),$

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2\bar{K}^{(N)}}-\sigma^{(N)}_{2}>N^{2\varepsilon}t/2,1<\bar{K}^{(N)}\leq
l(k,N)\big{)}\leq
c_{1}l(k,N)e^{-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}}e^{-c_{3}\big{(}\frac{t}{l(k,N)}\big{)}^{1/5}}.$
(4.6)

Also, for $t_{0}\leq t\leq 2(t_{0}+8\beta^{-1}B)l(k,N)$,

$\begin{split}&\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2\bar{K}^{(N)}}-\sigma^{(N)}_{2}>N^{2\varepsilon}t/2,1<\bar{K}^{(N)}\leq
l(k,N)\big{)}\\\ &\hskip 85.35826pt\leq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\bar{Z}^{(N)}_{0}>0\big{)}\leq
c_{1}e^{-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}},\end{split}$ (4.7)

where the last inequality from Lemma 3.3. Combining (4.6) and (4.7), we have
for all $t\geq t_{0}$,

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\sigma^{(N)}_{2\bar{K}^{(N)}}-\sigma^{(N)}_{2}>N^{2\varepsilon}t/2,1<\bar{K}^{(N)}\leq
l(k,N)\big{)}\leq
c^{\prime}_{1}l(k,N)e^{-c^{\prime}_{2}N^{(\frac{1}{2}-\varepsilon)/5}}e^{-c^{\prime}_{3}\big{(}\frac{t}{l(k,N)}\big{)}^{1/5}}.$
(4.8)

Finally, taking $k=t^{1/4}$ and
$l(k,N)=1+t^{1/4}+\sqrt{t}N^{\frac{1}{2}-\varepsilon}$, we obtain the
proposition by plugging (4.1), (4.8), and the bound on
$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\bar{K}^{(N)}\geq
l(k,N)\big{)}$ from Lemma 4.1 into (4.1). ∎

Now we come to the main result of this subsection which shows that the renewal
time $\Theta^{(N)}$ has finite second moment and gives bounds for the first
and second moments.

######  Proposition 4.3.

There exist $N_{0},c,c^{\prime}>0$ such that for all $N\geq N_{0}$,

$\displaystyle\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}(\Theta^{(N)})^{2}\big{)}$
$\displaystyle\leq cN^{4\varepsilon},$ $\displaystyle\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}\big{)}$
$\displaystyle\geq c^{\prime}N^{2\varepsilon}.$

In particular, $c^{\prime}N^{2\varepsilon}\leq\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}\big{)}\leq\sqrt{c}N^{2\varepsilon}$
for all $N\geq N_{0}$.

###### Proof.

Proof. Take $t_{0}$ as in Lemma 4.2. Then

$\begin{split}\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}(\Theta^{(N)})^{2}/N^{4\varepsilon}\big{)}&\leq
t_{0}^{2}+\int_{t_{0}}^{\infty}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}(\Theta^{(N)})^{2}/N^{4\varepsilon}>t\big{)}dt\\\
&\leq t_{0}^{2}+\int_{t_{0}}^{\infty}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}>N^{2\varepsilon}\sqrt{t}\big{)}dt.\end{split}$

The upper bound on $\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}(\Theta^{(N)})^{2}\big{)}$
now follows from Lemma 4.2 with replacing $t$ by $\sqrt{t}$ and integrating
the RHS. To obtain the lower bound on $\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}\big{)}$,
recall $\tau_{s}^{(N)}$ from (3.1) and note that

$\displaystyle\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}\big{)}$
$\displaystyle\geq\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\tau^{(N)}_{2}(B)\big{)}$
$\displaystyle\geq\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\tau^{(N)}_{2}(B)\mathds{1}\big{[}\tau^{(N)}_{2}(B)<\tau^{(N)}_{2}(N^{\frac{1}{2}-\varepsilon}))\big{]}\big{)}$
$\displaystyle=\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\tau^{(N)}_{2}(B)\mathds{1}\big{[}\tau^{(N)}_{2}(B)<\tau^{(N)}_{s}(2N^{\frac{1}{2}-\varepsilon}))\big{]}\big{)}$
$\displaystyle\geq\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\tau^{(N)}_{s}(B+N^{\frac{1}{2}-\varepsilon})\mathds{1}\big{[}\tau^{(N)}_{2}(B)<\tau^{(N)}_{s}(2N^{\frac{1}{2}-\varepsilon}))\big{]}\big{)}$
$\displaystyle=\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\tau^{(N)}_{s}(B+N^{\frac{1}{2}-\varepsilon})\big{)}$
$\displaystyle\ \ \ \ -\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\tau_{s}^{(N)}(B+N^{\frac{1}{2}-\varepsilon})\mathds{1}\big{[}\tau_{s}^{(N)}(2N^{\frac{1}{2}-\varepsilon})<\tau_{2}^{(N)}(B)\big{]}\big{)}.$
(4.9)

Now, for any $t\geq 0$,

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\tau^{(N)}_{s}(B+N^{\frac{1}{2}-\varepsilon})\geq
N^{2\varepsilon}t\big{)}$ $\displaystyle=\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\inf_{s\leq
t}S^{(N)}(N^{2\varepsilon}s)\geq\lfloor
N+BN^{\frac{1}{2}+\varepsilon}\rfloor\big{)}$
$\displaystyle=\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\inf_{s\leq
t}\big{(}S^{(N)}(N^{2\varepsilon}s)-S^{(N)}(0)\big{)}\geq\lfloor
N+BN^{\frac{1}{2}+\varepsilon}\rfloor-\lfloor
N+2BN^{\frac{1}{2}+\varepsilon}\rfloor\big{)}$
$\displaystyle\geq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\inf_{s\leq
t}\big{(}A((N-\beta
N^{\frac{1}{2}-\varepsilon})N^{2\varepsilon}s\big{)}-D\big{(}\int_{0}^{N^{2\varepsilon}s}(N-I^{(N)}(u))du\big{)}\big{)}\geq-
BN^{\frac{1}{2}+\varepsilon}+1\Big{)}$
$\displaystyle\geq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\inf_{s\leq
t}\big{(}\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})N^{2\varepsilon}s\big{)}-\hat{D}\big{(}\int_{0}^{N^{2\varepsilon}s}(N-I^{(N)}(u))du\big{)}$
$\displaystyle\hskip 312.9803pt-\beta N^{\frac{1}{2}+\varepsilon}s\big{)}\geq-
BN^{\frac{1}{2}+\varepsilon}+1\big{)}$
$\displaystyle\geq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\inf_{s\leq
t}\big{(}\hat{A}\big{(}(N-\beta
N^{\frac{1}{2}-\varepsilon})N^{2\varepsilon}s\big{)}-\hat{D}\big{(}\int_{0}^{N^{2\varepsilon}s}(N-I^{(N)}(u))du\big{)}$
$\displaystyle\hskip 284.52756pt-\beta
N^{\frac{1}{2}+\varepsilon}s\big{)}\geq(\beta
t-B)N^{\frac{1}{2}+\varepsilon}+1\big{)},$

where $\hat{A}(s)=A(s)-s$ and $\hat{D}(s)=D(s)-s$. Using Lemma A.1 in the
above lower bound, there exist $\underline{t}>0,\underline{N}>0$ such that for
all $t\leq\underline{t},N\geq\underline{N}$,

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}\left(B+N^{\frac{1}{2}-\varepsilon}\right)>N^{2\varepsilon}t\right)\geq\frac{1}{2},$

and consequently,

$\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}\left(B+N^{\frac{1}{2}-\varepsilon}\right)\right)\geq\frac{1}{2}\underline{t}N^{2\varepsilon}.$
(4.10)

Next, we will show that the second term in the bound (4.1) is much smaller
than the first term. To show this, recall the stopping times
$\\{\sigma^{(N)}_{j}\\}$ from (2.6) and define
$\hat{K}^{(N)}\coloneqq\inf\\{k\geq
0:\bar{Q}^{(N)}_{3}(\sigma^{(N)}_{2k+1})=0\\}.$ Lemma 4.1 and Lemma 4.2
readily extend to $\hat{K}^{(N)}$ in place of $\bar{K}^{(N)}$ and
$\sigma^{(N)}_{2\hat{K}^{(N)}+1}$ in place of $\Theta^{(N)}$. To elaborate,
the estimates in Lemma 3.3 can be used exactly as in the geometric trials
based argument in the proof of Lemma 4.1 to obtain tail bounds for
$\hat{K}^{(N)}$. Using these bounds along the same lines as in the proof of
Lemma 4.2, one obtains tail bounds for $\sigma^{(N)}_{2\hat{K}^{(N)}+1}$
similar to those for $\Theta^{(N)}$. Hence, using the same argument used to
bound the second moment of $(\Theta^{(N)})^{2}/N^{4\epsilon}$, we obtain
$\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left[\left(\sigma_{2\hat{K}^{(N)}+1}^{(N)}\right)^{2}\right]\leq
cN^{4\epsilon}.$ Now, observe that
$\tau^{(N)}_{s}\big{(}B+N^{\frac{1}{2}-\varepsilon}\big{)}\leq\sigma^{(N)}_{2\hat{K}^{(N)}+1}.$
Using this observation along with Lemma 3.2,

$\displaystyle\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(B+N^{\frac{1}{2}-\varepsilon})\mathds{1}\big{[}\tau^{(N)}_{s}(2N^{\frac{1}{2}-\varepsilon})<\tau^{(N)}_{2}(B)\big{]}\right)$
$\displaystyle\leq\sqrt{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left[\left(\sigma_{2\hat{K}^{(N)}+1}^{(N)}\right)^{2}\right]}\sqrt{\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(2N^{\frac{1}{2}-\varepsilon})<\tau^{(N)}_{2}(B)\right)}$
$\displaystyle\leq
cN^{2\varepsilon}\left(c\exp\left(-c^{\prime}N^{4\varepsilon/5}N^{(\frac{1}{2}-\varepsilon)/5}\right)+c\exp\left(-c^{\prime}N^{\frac{1}{2}-\varepsilon}\right)\right),$
(4.11)

where the last inequality is from Lemma 3.2. Finally, the lower bound on
$\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\big{(}\Theta^{(N)}\big{)}$
claimed in the corollary is established by plugging (4.10) and (4.1) into
(4.1). ∎

###  4.2 Renewal representation of stationary measure.

The finiteness of expectation of the renewal time $\Theta^{(N)}$ implies the
representation of the stationary measure as stated in (2.7). This
representation is useful as it gives a tractable handle on a highly implicit
stationary measure by expressing it in terms of the sample paths observed
until a finite random (renewal) time. Upon combining this with the sample path
analysis of Section 3, we now prove Theorem 2.4.

###### Proof.

Proof of Theorem 2.4. Recall the stopping time $\tau^{(N)}_{s}$ from (3.1).
Note that due to (2.7),

$\displaystyle\pi\left({\color[rgb]{0,0,0}S^{(N)}(\infty)}\geq
N+xN^{\frac{1}{2}+\varepsilon}\right)$
$\displaystyle\leq\frac{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\mathds{1}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)\Theta^{(N)}\right)}{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\Theta^{(N)}\right)}$
$\displaystyle\leq\frac{\sqrt{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left((\Theta^{(N)})^{2}\right)}\sqrt{\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)}}{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\Theta^{(N)}\right)}.$
(4.12)

The bounds on $\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\Theta^{(N)}\right)$
and $\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left((\Theta^{(N)})^{2}\right)$
will be used from Proposition 4.3. In the following, we will derive upper
bound on $\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)$.
This upper bound depends on the magnitude of $x$ and that is why we will
consider three cases: (a) $x\in[4B,N^{\frac{1}{2}-\varepsilon}]$, (b)
$x\in(N^{\frac{1}{2}-\epsilon},2N^{\frac{1}{2}-\epsilon}]$, and (c) $x\geq
2N^{\frac{1}{2}-\varepsilon}$.

Case 1: $x\in[4B,N^{\frac{1}{2}-\varepsilon}]$. Recall $t_{0}$ from Lemma 3.2.
For $x\in[t_{0}\beta+2B,N^{\frac{1}{2}-\varepsilon}]$,

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)=\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\tau^{(N)}_{2}(B)\right)$
$\displaystyle=\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(S^{(N)}\text{ hits
}S^{(N)}(0)+(x-2B)N^{\frac{1}{2}+\varepsilon}\text{ before time
}\tau^{(N)}_{2}(B)\right)$ $\displaystyle\leq
c\exp\big{\\{}-c^{\prime}x\big{\\}}+c\exp\big{\\{}-c^{\prime}N^{4\varepsilon/5}x^{1/5}\big{\\}},$
(4.13)

where the second equality is due to the fact that
$S^{(N)}(0)=N+2BN^{\frac{1}{2}+\varepsilon}$, the inequality is due to Lemma
3.2, and $c^{\prime}$ is a fixed positive constant that depends on $B$ but not
on $N$ and $x$. The bound of (4.2) can be extended to
$x\in[4B,N^{\frac{1}{2}-\varepsilon}]$ by adjusting the constants.

Case 2: For $x\in(N^{\frac{1}{2}-\epsilon},2N^{\frac{1}{2}-\epsilon}]$, note
that at $t=\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})$, $S^{(N)}(t)>2N$ and
thus $\bar{Q}^{(N)}_{3}(t)>0$. Therefore, by Lemma 3.3 (i),

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)$
$\displaystyle\leq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\bigg{(}\sup_{s\in[0,\tau^{(N)}_{2}(B)]}\big{(}\bar{Q}^{(N)}_{3}(s)-\bar{Q}^{(N)}_{3}(0)\big{)}>0\bigg{)}$
$\displaystyle\leq
c_{1}\exp\left\\{-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}\right\\}\leq
c_{1}\exp\left\\{-c_{2}^{\prime}x^{1/5}\right\\},$ (4.14)

for positive constants $c_{1},c_{2},c_{2}^{\prime}$ that can depend on $B$ but
not on $N$ and $x$.

Case 3: $x\geq 2N^{\frac{1}{2}-\varepsilon}$. Values of $S^{(N)}$ in the
associated range result from $\bar{Q}^{(N)}_{3}$ hitting large values (see
(4.15)) and hence need a different treatment from those in the above cases.

Recall from (2.6) the stopping times $\sigma^{(N)}_{2i}$ and
$\sigma^{(N)}_{2i+1}$ for $i\geq 0$ and $\bar{K}^{(N)}=\inf\\{k\geq
1:\bar{Q}^{(N)}_{3}(\sigma^{(N)}_{2k})=0\\}$. In this case, write
$\bar{Z}^{(N)}_{*i}\coloneqq\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+2}]}\big{(}\bar{Q}^{(N)}_{3}(s)-\bar{Q}^{(N)}_{3}(\sigma^{(N)}_{2i})\big{)}_{+},\,i\geq
0.$ Take any $k\geq 1$ and recall
$l(k,N)=1+k+k^{2}N^{\frac{1}{2}-\varepsilon}$. Now observe the following:
Since $x\geq 2N^{\frac{1}{2}-\varepsilon}$, at
$t=\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})$,
$S^{(N)}(t)>N+xN^{\frac{1}{2}+\varepsilon}$ and thus

$\bar{Q}^{(N)}_{3}(t)\geq
S^{(N)}(t)-2N>xN^{\frac{1}{2}+\varepsilon}-N\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2}>0.$
(4.15)

Also, note that starting from $(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})$, if
$\bar{Z}^{(N)}_{*0}=0$, then $\Theta^{(N)}$ must be smaller than
$\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})$, otherwise it will contradict
(4.15). From the above, we can write

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)$
$\displaystyle\quad\leq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\bar{K}^{(N)}\geq
l(k,N)\right)+\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sup_{0\leq i\leq
l(k,N)}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+2}]}S^{(N)}(s)>N+xN^{\frac{1}{2}+\varepsilon}\Big{)}$
$\displaystyle\quad\leq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\bar{K}^{(N)}\geq
l(k,N)\right)$ (4.16) $\displaystyle\qquad+\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sup_{0\leq i\leq
l(k,N)}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+2}]}\bar{Q}^{(N)}_{3}(s)\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2},\bar{Z}^{(N)}_{*0}>0\Big{)},$

where the last inequality follows from (4.15). By Lemma 4.1, for sufficiently
large $N$, for all $k\geq 1$,

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\bar{K}^{(N)}\geq
l(k,N)\right)\leq
c_{1}ke^{-c_{2}N^{(\frac{1}{2}-\varepsilon)/11}}e^{-c_{2}\left(\frac{k}{N^{\frac{1}{2}-\varepsilon}}\right)^{1/11}}+2^{-k}.$
(4.17)

Next, we will upper-bound the second term on the RHS of (4.2). Note that since
$\bar{Q}_{3}^{(N)}(0)=0$,

$\displaystyle\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+2}]}\bar{Q}_{3}^{(N)}(s)$
$\displaystyle\leq\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+2}]}\left(\bar{Q}_{3}^{(N)}(s)-\bar{Q}_{3}^{(N)}(\sigma^{(N)}_{2i})\right)+\sum_{j=0}^{i-1}\left(\bar{Q}_{3}^{(N)}(\sigma^{(N)}_{2j+2})-\bar{Q}_{3}^{(N)}(\sigma^{(N)}_{2j})\right)$
$\displaystyle\leq\sum_{j=0}^{i}\sup_{s\in[\sigma^{(N)}_{2j},\sigma^{(N)}_{2j+2}]}\left(\bar{Q}_{3}^{(N)}(s)-\bar{Q}_{3}^{(N)}(\sigma^{(N)}_{2j})\right)\leq\sum_{j=0}^{i}\bar{Z}^{(N)}_{*j}.$

Since $\sum_{j=0}^{i}\bar{Z}^{(N)}_{*j}$ is non-decreasing in $i$, we can
write

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sup_{0\leq i\leq
l(k,N)}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+2}]}\bar{Q}_{3}^{(N)}(s)\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2},\bar{Z}^{(N)}_{*0}>0\Big{)}$
$\displaystyle\leq\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sum_{j=0}^{l(k,N)}\bar{Z}^{(N)}_{*j}\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2}\Big{)}=\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sum_{j=0}^{l(k,N)}\frac{\bar{Z}^{(N)}_{*j}}{N^{\frac{1}{2}+\varepsilon}}\geq\frac{x}{2}\Big{)}.$
(4.18)

To upper bound the RHS of (4.2), we will use Lemma A.2. For that, first we
need to have appropriate tail bounds on
$\frac{\bar{Z}^{(N)}_{*j}}{N^{\frac{1}{2}+\varepsilon}}$, which is given by
Lemma 3.3 (i) as follows: Letting $k=k(x)=\lfloor\sqrt{x}\rfloor$, we have
$l^{\prime}(x,N):=l(k(x),N)=1+\lfloor\sqrt{x}\rfloor+\lfloor\sqrt{x}\rfloor^{2}N^{\frac{1}{2}-\varepsilon}$.
Therefore, by Lemma 3.3 (i), for any $j\geq 1,x>0$, and sufficient large $N$,

$\mathbb{P}\Big{(}\frac{\bar{Z}^{(N)}_{*j}}{N^{\frac{1}{2}+\varepsilon}}\geq
x\ \big{|}\ \mathcal{F}_{\sigma^{(N)}_{2j}}\Big{)}\leq
c_{1}e^{-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}}e^{-c_{3}x^{1/5}},$ (4.19)

where $c_{1},c_{2},c_{3}>0$ are constants. Also, there exists an
$N^{\prime\prime}$ such that for all $N\geq N^{\prime\prime}$,
$\int_{0}^{\infty}c_{1}e^{-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}}e^{-c_{3}y^{1/5}}dy\leq\frac{x}{4\times
2(l^{\prime}(x,N)+1)}.$ Take any $N\geq N^{\prime\prime}$. We will use Lemma
A.2 with trivial indexing set $R$ and
$\theta=\frac{1}{5},a=\frac{x}{2(l^{\prime}(x,N)+1)},n=l^{\prime}(x,N)+1,\
\text{and}\
\hat{\Phi}_{j}=\frac{\bar{Z}^{(N)}_{*(j-1)}}{N^{\frac{1}{2}+\varepsilon}},\,j\geq
1,$ with starting configuration
$(I^{(N)}(0),Q_{2}^{(N)}(0),\bar{Q}^{(N)}_{3}(0))=(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})$, and associated
filtration $\big{\\{}\mathcal{F}_{j}:j\geq 1\big{\\}}$ being the natural
filtration generated by the above random variables. Thus, we get

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sum_{j=0}^{l^{\prime}(x,N)}\bar{Z}^{(N)}_{*j}\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\sum_{j=1}^{n}\hat{\Phi}_{j}\geq an\Big{)}\leq
c^{\prime}_{1}\Big{(}1+\frac{\big{(}l^{\prime}(x,N)+1\big{)}^{5/11}}{\big{(}\frac{x}{2(l^{\prime}(x,N)+1)}\big{)}^{\frac{1}{11}}}\Big{)}\exp\Big{[}-c^{\prime}_{2}\Big{(}\frac{x^{2}}{4(l^{\prime}(x,N)+1)}\Big{)}^{1/11}\Big{]}$
(4.20)
$\displaystyle\leq\hat{c}_{1}^{\prime}N^{\frac{1}{2}-\varepsilon}\exp\big{\\{}-\hat{c}^{\prime}_{2}\Big{(}\frac{x}{N^{\frac{1}{2}-\varepsilon}}\Big{)}^{1/11}\big{\\}}.$

Moreover, for all large enough $N$, for any $k\geq 1$,

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sum_{j=0}^{l^{\prime}(x,N)}\bar{Z}^{(N)}_{*j}\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2}\Big{)}$
$\displaystyle\leq(l^{\prime}(x,N)+1)\sup_{\underline{z}}\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{z})}\Big{(}\bar{Z}^{(N)}_{*0}\geq
1\Big{)}$ $\displaystyle\leq
c_{1}xN^{\frac{1}{2}-\varepsilon}\exp\big{\\{}-c_{2}N^{(\frac{1}{2}-\varepsilon)/5}\big{\\}},$
(4.21)

where the first inequality follows from union bound and the fact that
$l^{\prime}(x,N)+1\leq xN^{\frac{1}{2}+\varepsilon}/2$ for all $N$ large
enough, and the last inequality follows from Lemma 3.3 (i). Using (4.2) and
(4.2) and proceeding exactly as in deriving (D.9) from (D), we obtain

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sum_{j=0}^{l^{\prime}(x,N)}\bar{Z}^{(N)}_{*j}\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2}\Big{)}\leq
c_{1}^{\prime\prime}\exp\big{\\{}-c_{2}^{\prime\prime}N^{(\frac{1}{2}-\varepsilon)/11}\big{\\}}\exp\big{\\{}-c^{\prime\prime}_{2}\Big{(}\frac{x}{N^{\frac{1}{2}-\varepsilon}}\Big{)}^{1/11}\big{\\}},$
(4.22)

for positive constants $c_{1}^{\prime\prime},c_{2}^{\prime\prime}$. Plugging
(4.22) into (4.2), we obtain $N^{\prime\prime\prime}$ large enough such that
for all $N\geq N^{\prime\prime\prime},\,x\geq 2N^{\frac{1}{2}-\varepsilon}$,

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\Big{(}\sup_{0\leq i\leq
l(k,N)}\sup_{s\in[\sigma^{(N)}_{2i},\sigma^{(N)}_{2i+2}]}\bar{Q}_{3}^{(N)}(s)\geq\frac{xN^{\frac{1}{2}+\varepsilon}}{2},\bar{Z}^{(N)}_{*0}>0\Big{)}\\\
\leq
c_{1}^{\prime\prime}\exp\big{\\{}-c_{2}^{\prime\prime}N^{(\frac{1}{2}-\varepsilon)/11}\big{\\}}\exp\big{\\{}-c^{\prime\prime}_{2}\Big{(}\frac{x}{N^{\frac{1}{2}-\varepsilon}}\Big{)}^{1/11}\big{\\}}.$
(4.23)

Moreover, plugging (4.23) and (4.17) (with $k=\lfloor\sqrt{x}\rfloor$) into
(4.2), we have that for sufficiently large $N$, for $x\geq
2N^{\frac{1}{2}-\varepsilon}$,

$\displaystyle\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)$
$\displaystyle\leq$
$\displaystyle\bar{c}\exp\Big{\\{}-\bar{c}^{\prime}\Big{(}N^{(\frac{1}{2}-\varepsilon)/11}+\Big{(}\frac{\sqrt{x}}{N^{\frac{1}{2}-\varepsilon}}\Big{)}^{1/11}\Big{)}\Big{\\}}+\bar{c}e^{-\bar{c}^{\prime}\sqrt{x}}$
$\displaystyle\leq$
$\displaystyle\bar{c}\exp\big{\\{}-2\bar{c}^{\prime}x^{1/44}\big{\\}}+\bar{c}e^{-\bar{c}^{\prime}\sqrt{x}}.$
(4.24)

Equations (4.2), (4.2) and (4.2) imply that there exist $N_{0}\in\mathbb{N}$
and positive constants $C^{\prime}_{1},C^{\prime}_{2}$ such that for all
$N\geq N_{0}$,

$\mathbb{P}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\tau^{(N)}_{s}(x+N^{\frac{1}{2}-\varepsilon})<\Theta^{(N)}\right)\leq\begin{cases}C^{\prime}_{1}\exp\big{\\{}-C^{\prime}_{2}x^{1/5}\big{\\}},\quad
4B\leq x\leq 2N^{\frac{1}{2}-\varepsilon},\\\
C^{\prime}_{1}\exp\big{\\{}-C^{\prime}_{2}x^{1/44}\big{\\}},\quad x\geq
2N^{\frac{1}{2}-\varepsilon}.\end{cases}$ (4.25)

Thus, the tail estimate on $X^{(N)}(\infty)$ in the theorem follows upon using
(4.25) and Proposition 4.3 in (4.2).

(ii) Next, we will use the $M/M/N$ system to lower bound a JSQ system.
Specifically, consider an $M/M/N$ queue with total arrival rate
$N\lambda_{N}=N-\beta N^{\frac{1}{2}-\varepsilon}$ and unit-mean exponential
service times, and denote by $\underline{S}^{(N)}(t)$ the total number of
tasks in the system at time $t$. Let
$\underline{X}^{(N)}(t):=\frac{\underline{S}^{(N)}(t)-N}{N^{\frac{1}{2}+\varepsilon}}$.
By a natural coupling, if $X^{(N)}(0)=\underline{X}^{(N)}(0)$,
$X^{(N)}(t)\geq\underline{X}^{(N)}(t)$, $\forall\ t\geq 0$, which implies that
$X^{(N)}(\infty)$ stochastically dominates $\underline{X}^{(N)}(\infty)$.
Hence, it is sufficient to show that

$\lim_{\delta\downarrow
0}\varliminf_{N\rightarrow\infty}\mathbb{P}\big{(}\underline{X}^{(N)}(\infty)\geq\delta\big{)}=1.$
(4.26)

Denote $\pi^{(N)}_{k}=\mathbb{P}\big{(}\underline{X}^{(N)}(\infty)=k\big{)}$,
$k\in\mathbb{N}_{0}$. In the following, $c_{i}(N),\,i\in\mathbb{N},$ are
positive constants depending only on $N$ (not $k$) such that
$c_{i}(N)\xrightarrow{N\rightarrow\infty}1,\,i\in\mathbb{N}$. By the explicit
formula of the stationary distribution of an $M/M/N$ queue ([22, Section
3.5]), we have that

$\pi^{(N)}_{0}=\Big{[}\sum_{k=0}^{N-1}\frac{N^{k}(1-\beta/N^{\frac{1}{2}+\varepsilon})^{k}}{k!}+\frac{N^{N}(1-\beta/N^{\frac{1}{2}+\varepsilon)^{N}}}{N!}\frac{N^{\frac{1}{2}+\varepsilon}}{\beta}\Big{]}^{-1},$
(4.27)

and for all $k\geq N$,

$\pi^{(N)}_{k}=\pi^{(N)}_{0}\frac{(N\lambda_{N})^{k}N^{N-k}}{N!}=\pi^{(N)}_{0}\frac{(1-\beta/N^{\frac{1}{2}+\varepsilon})^{k}N^{N}}{N!}.$
(4.28)

By Stirling’s formula ([5, Section 27]), we get that for all large enough $N$,

$\begin{split}\pi^{(N)}_{0}&\geq\Big{[}e^{N}+c_{0}(N)\frac{e^{N}N^{\varepsilon}}{\sqrt{2\pi}\beta}(1-\beta/N^{\frac{1}{2}+\varepsilon})^{N}\Big{]}^{-1}\\\
&\geq c_{1}(N)\sqrt{2\pi}\beta
N^{-\varepsilon}e^{-N}(1-\beta/N^{\frac{1}{2}+\varepsilon})^{-N},\end{split}$
(4.29)

and for all $k\geq N$,

$\begin{split}\pi^{(N)}_{k}&\geq c_{2}(N)\beta
N^{-\frac{1}{2}-\varepsilon}\big{(}1-\frac{\beta}{N^{\frac{1}{2}+\varepsilon}}\big{)}^{k-N}\\\
&\geq c_{2}(N)\beta
N^{-\frac{1}{2}-\varepsilon}\exp\big{(}-\frac{(k-N)\beta}{N^{\frac{1}{2}+\varepsilon}}c_{3}(N)\big{)}.\end{split}$
(4.30)

For any fixed $\delta>0$, denote $N_{\delta}=N+\delta
N^{\frac{1}{2}+\varepsilon}$. By (4.30), we have that for large enough $N$,

$\begin{split}\mathbb{P}\big{(}\underline{X}^{(N)}(\infty)\geq\delta\big{)}&=\sum_{k\geq\lceil
N_{\delta}\rceil}c_{2}(N)\beta
N^{-\frac{1}{2}-\varepsilon}\exp\big{(}-\frac{(k-N)\beta}{N^{\frac{1}{2}+\varepsilon}}c_{3}(N)\big{)}\\\
&\geq c_{2}(N)\int_{\beta\delta c_{4}(N)}^{\infty}\exp(-xc_{3}(N))dx\\\
&=(c_{2}(N)/c_{3}(N))\exp(-\beta\delta c_{3}(N)c_{4}(N))\\\ &\geq
1-2\beta\delta,\end{split}$ (4.31)

where the first inequality comes from approximating the sum by an integral
and, for the last inequality, we have used $\exp(-x)\geq(1-x)$, $\forall
x\in\mathbb{R}$. Since (4.31) holds for all fixed $\delta>0$, we conclude that
(4.26) holds.

(iii) To obtain the expression for expectation of $I^{(N)}(\infty)$, observe
that, if we start the process at stationarity, then by (2.2), for any $t>0$,

$\displaystyle 0$
$\displaystyle=N^{\frac{1}{2}+\varepsilon}\mathbb{E}[X^{(N)}(t)-X^{(N)}(0)]=\mathbb{E}\left[A(N^{1+2\varepsilon}\lambda_{N}t)-D\Big{(}\int_{0}^{N^{2\varepsilon}t}(N-I^{(N)}(s))ds\Big{)}\right]$
$\displaystyle=-\beta
N^{\frac{1}{2}+\varepsilon}t+\int_{0}^{N^{2\varepsilon}t}\mathbb{E}[I^{(N)}(s)]ds=-\beta
N^{\frac{1}{2}+\varepsilon}t+N^{2\varepsilon}t\mathbb{E}[I^{(N)}(\infty)],$

from which we conclude $\mathbb{E}\left[I^{(N)}(\infty)\right]=\beta
N^{\frac{1}{2}-\varepsilon}$.

(iv) The observation $\sup_{N\geq
1}\mathbb{E}\left[N^{-\frac{1}{2}-\varepsilon}Q^{(N)}_{2}(\infty)\right]<\infty$
follows upon noting that $N^{-\frac{1}{2}-\varepsilon}Q^{(N)}_{2}(\infty)\leq
X^{(N)}(\infty)+N^{-\frac{1}{2}-\varepsilon}I^{(N)}(\infty)$ and using the
tail estimate on $X^{(N)}(\infty)$ in (2.4) and the above explicit expectation
for $I^{(N)}(\infty)$.

(v) Now we show that

$\bar{Q}^{(N)}_{3}(\infty)\xrightarrow{P}0\ \mbox{ as }\ N\rightarrow\infty.$
(4.32)

By the renewal representation (2.7), note that for any fixed $T>0$,

$\displaystyle\pi(\bar{Q}^{(N)}_{3}(\infty)>0)=\frac{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\int_{0}^{\Theta^{(N)}}\mathds{1}\left(\bar{Q}^{(N)}_{3}(s)>0\right)ds\right)}{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\Theta^{(N)}\right)}$
$\displaystyle\leq\frac{\mathbb{E}_{(0,\,\lfloor
2BN^{\frac{1}{2}+\varepsilon}\rfloor,\,\underline{0})}\left(\Theta^{(N)}\mathds{1}(\Theta^{(N)}\geq
N^{2\varepsilon}T)\right)}{\mathbb{E}_{(0,\,\lfloor