1. Introduction
Mathematical models of disease spread are widely used in epidemiology, to assist in preventing and managing epidemic outbreaks. One well-studied epidemic model is the logistic susceptible–infected–susceptible (SIS) model on the complete graph with N vertices, which is a continuous-time birth-and-death Markov chain
$X^*_N=(X^*_N(t))_{t\geq0}$
with state space
$\{0, 1, \ldots, N\}$
and transitions given by
\begin{align*} &x^*\mapsto x^*+1\quad\text{at rate }\lambda x^*(1-x^*/N),\\ &x^*\mapsto x^*-1\quad\text{at rate }\mu x^*,\end{align*}
where
$x^*\in\{0,1, \ldots, N\}$
and
$\lambda, \mu>0$
. The model describes an epidemic spreading in a closed population with N individuals, with the number of infected people at time t represented by
$X^*_N(t)$
. To explain the dynamics, each infected person encounters a random member of the population at rate
$\lambda$
, and if the other individual is currently susceptible to infection, that individual then becomes infected. Each infected individual recovers at rate
$\mu$
, and once they are recovered, they immediately become susceptible again. If, at any time, the number of infected people becomes zero, we say that the epidemic outbreak is extinct. This model was first formulated and studied by Feller [Reference Feller18] in the 1930s, but was not extensively studied until the 1970s, when it was popularised by Weiss and Dishon [Reference Weiss and Dishon33].
We are interested in asymptotics as
$N \to \infty$
, with
$\lambda$
and
$\mu$
being fixed positive constants. We use the phrase ‘with high probability’ to mean ‘with probability tending to 1 as
$N \to \infty$
’. A key quantity in the SIS model is the so-called basic reproduction ratio
$\mathcal{R}_0\,:\!=\,\lambda/\mu$
. The epidemic is said to be supercritical if
$\mathcal{R}_0>1$
and subcritical if
$\mathcal{R}_0<1$
. It is well known that for the supercritical SIS model, if there are a large number of infected individuals at time 0, then with high probability
$X_N^*(t)/N$
heads rapidly towards the stable fixed point of a corresponding deterministic model given by a (logistic) differential equation, and then spends most of its time before extinction in the neighbourhood of that fixed point. The time to extinction is exponential in N (in mean and with high probability) as
$N\to\infty$
; see, for example, [Reference Nåsell25]. For more detailed aspects of the supercritical logistic SIS model such as quasi-stationarity, see, for example, [Reference Andersson and Djehiche4, Reference Barbour5, Reference Nåsell26].
In the subcritical case where
$\lambda<\mu$
, Doering et al. [Reference Doering, Sargsyan and Sander16] showed in 2005 that if the initial state
$X_N^*(0)$
is of order N, then the expected extinction time is
$\frac{1}{\mu-\lambda} (\log N + O(1))$
.
Brightwell et al. [Reference Brightwell, House and Luczak10] obtained a formula for the asymptotic distribution of the extinction time in the subcritical case and, in particular, proved that if the starting state is of order N, then for any large enough constant
$c>0$
, the probability of extinction by time
$\frac{1}{\mu-\lambda}\log(N)-c$
is nearly zero, while by time
$\frac{1}{\mu-\lambda}\log(N)+c$
it is nearly 1. To be precise, an asymptotic formula for the extinction time, where the randomness has a Gumbel distribution, is given in [Reference Brightwell, House and Luczak10] in the case where
$\mu > \lambda$
and both are fixed constants. The authors also considered the case where
$\lambda$
and
$\mu$
are allowed to vary with N, and
$\mu (N) - \lambda (N) \to 0^+$
suitably slowly (the ‘barely subcritical’ case), and showed that the same formula for the extinction time holds in this regime.
Recent work of Foxall [Reference Foxall19] summarises and derives further results on the asymptotic behaviour of the extinction time under different asymptotic regimes for the initial infection size and reproduction ratio (also allowing
$\lambda$
and
$\mu$
to vary with N).
The model studied in this paper is a variant of the logistic SIS epidemic model known as the logistic SIS epidemic model with self-infection (
$\varepsilon$
-SIS model), which is a continuous-time birth-and-death Markov chain
$X_N=(X_N(t))_{t\geq0}$
with state space
$\{0, 1, \ldots, N\}$
and transitions given by
\begin{align*} &x\mapsto x+1\quad\text{at rate }\lambda x(1-x/N)+\varepsilon(N-x),\\ &x\mapsto x-1\quad\text{at rate }\mu x,\end{align*}
where
$x\in\{0,1,\ldots,N\}$
and
$\lambda, \mu, \varepsilon>0$
. A literature review for this lesser-studied model is given later in the present section.
Compared with the standard SIS model, the
$\varepsilon$
-SIS model has an additional source of infection, which can be thought of as an infection from an unknown source or external disease reservoir, such as an animal carrier of the disease. Thus, any susceptible person can be infected (at rate
$\varepsilon$
) without having contact with any infected member of the population. Excluding the case of
$\varepsilon=0$
(done throughout this paper), which is the classical well-studied SIS model, the
$\varepsilon$
-SIS model admits a non-degenerate stationary distribution, and so the relevant quantity of interest is the time to stationarity, which is analogous to the extinction time in the classical SIS model. We are interested in asymptotics as the population size N tends to infinity. Assuming that the parameters of the model,
$\lambda$
,
$\mu$
, and
$\varepsilon$
, are absolute constants not depending on N, we show that the sequence of
$\varepsilon$
-SIS Markov chains
$(X_N)_{N\geq1}$
exhibits a cutoff, as per the following definition.
Definition 1.1. The sequence of Markov chains
$\{X_N(t):t \ge 0\}_{N\geq1}$
with finite state space
$E_N$
, transition function
$P_N^t(x, \,\cdot\,)$
, and stationary distribution
$\pi_N$
is said to exhibit a cutoff at time
$t_N$
with window size
$\omega_N$
if
$\omega_N=o(t_N)$
and
\begin{equation*} \lim_{s\to\infty}\liminf_{N\to\infty} \rho_N(t_N-s\omega_N)=1, \qquad \lim_{s\to\infty}\limsup_{N\to\infty} \rho_N(t_N+s\omega_N)=0,\end{equation*}
where
\begin{equation*} \rho_N(t) \,:\!=\, \max_{x\in E_N} \lVert P_N^t(x,\,\cdot\,)-\pi_N \rVert_{\text{TV}}\end{equation*}
is the worst-case total variation distance between the distribution of
$X_N(t)$
and the chain’s stationary distribution
$\pi_N$
.
Informally, cutoff means that for any starting state, the distribution of the chain goes from being about as far as possible in total variation distance from the stationary distribution to about as close as possible, over a window of time of length
$\omega_N$
centred around time
$t_N$
.
The cutoff phenomenon for Markov chains was first identified in the 1980s for random transpositions on the symmetric group by Diaconis and Shahshahani [Reference Diaconis and Shahshahani14], and the name was coined by Aldous and Diaconis [Reference Aldous and Diaconis2]. Establishing cutoff for specific models of Markov chains is to this day an active area of research and in general a difficult problem. For the model in question, we have the following main result, which gives the precise cutoff time of the chain, with an optimal window.
Theorem 1.1. The sequence of
$\varepsilon$
-SIS Markov chains
$(X_N)_{N\geq1}$
has a cutoff at
$t_N\,:\!=\,\frac{1}{2J}\log N$
with constant window size, where
$J\,:\!=\, \sqrt{(\lambda-\mu-\varepsilon)^2+4\lambda\varepsilon}$
.
Before going further, we highlight a few points about the theorem. First, Theorem 1.1 implies that for a very small
$\varepsilon$
, the cutoff time of the
$\varepsilon$
-SIS model is approximately
$\frac{1}{2(\mu-\lambda)}\log(N)$
. This is about twice as fast as the subcritical classical SIS model, which has a cutoff at
$\frac{1}{\mu-\lambda}\log(N)$
. This finding does not appear to be at all a priori obvious; we will give an intuitive explanation for it after describing the proof in more detail at the end of the introduction.
Second, general conditions guaranteeing that a sequence of birth-and-death chains will exhibit cutoff are given in [Reference Ding, Lubetzky and Peres15], where it is shown that if the sequence satisfies the so-called product condition – namely that the relaxation time
$t_{\mathrm{REL}}(N)$
, defined to be 1 over the spectral gap of the chain, is of smaller order as N goes to infinity than the mixing time
$t_{\mathrm{MIX}}(N)$
, defined to be the first time that the total variation distance to stationarity is less than
$1/4$
– then the chain exhibits cutoff with window of order at most
$\sqrt{t_{\mathrm{REL}}(N)\, t_{\mathrm{MIX}}(N)}$
. While it is likely possible in our setting to verify the product condition or related conditions (see e.g. the follow-up works [Reference Chen and Saloff-Coste11–Reference Chen and Saloff-Coste13]), we would still need to derive bounds on the mixing time, and the window size
$\sqrt{t_{\mathrm{REL}}(N)\,t_{\mathrm{MIX}}(N)}$
is at best of order
$\sqrt{\log(N)}$
, because the relaxation time is at least 1 and the mixing time is of order
$\log(N)$
. Thus our Theorem 1.1 is sharper than what would be obtained from these general results, by giving the constant for the cutoff time and showing that the window is of constant order. Ding et al. [Reference Ding, Lubetzky and Peres15] showed that the window size given in their results is unimprovable for general birth-and-death chains, so our result is also interesting as a non-trivial example where the window is smaller than predicted by the general result.
We also mention in this vein of research the work of Basu et al. [Reference Basu, Hermon and Peres8], which gives analogous conditions for cutoff of reversible Markov chains on finite trees and semi-birth-and-death chains, as well as the very recent work of Salez [Reference Salez28], which gives a ‘product-like’ condition for cutoff assuming that the Markov chain has ‘non-negative curvature’. These works also give a cutoff window of order at most
$\sqrt{t_{\mathrm{MIX}}(N)}\cdot t_{\mathrm{REL}}(N)^\alpha$
for an
$\alpha>0$
, which, as in the birth-and-death case, may not be sharp. Thus, in many applications precise information about the exact cutoff time and window size needs to be obtained by ‘bare hands’ methods.
The technique we use for proving Theorem 1.1 is adapted from [Reference Barbour, Brightwell and Luczak6], which developed a general approach to establishing the cutoff phenomenon for suitable chains by using couplings and concentration-of-measure inequalities; also see that paper for a comprehensive literature review of the cutoff phenomenon. The approach has been used in other work such as [Reference Lopes and Luczak24], in which a formula was derived for the asymptotic distribution of the extinction time for the weaker of two competing SIS epidemics (a result which, though not an example of the cutoff phenomenon, has a similar flavour), and [Reference Eskenazis and Nestoridi17], which established the cutoff phenomenon for the Bernoulli–Laplace urn model with o(N) swaps. Thus, an additional contribution of our work is to provide another example of this approach, which we hope will serve to standardise it as a tool for establishing cutoff.
A final contribution of this article is to bring the
$\varepsilon$
-SIS model to the attention of researchers in applied probability, so we next discuss the existing literature. At the end of the introduction we give an overview of the proof of Theorem 1.1 and simultaneously the organisation of the paper.
1.1. Related literature
The
$\varepsilon$
-SIS model has appeared sporadically in the applied literature. The theoretical primer (aimed at applied researchers) of Keeling and Ross [Reference Keeling and Ross21] includes the additional
$\varepsilon$
term in their definition of the (vanilla) SIS model. Stone et al. [Reference Stone, Wilkinson-Herbots and Isham29] applied the
$\varepsilon$
-SIS model to head lice epidemic data, after deriving closed-form analytic formulas for some stationary quantities, and Hill et al. [Reference Hill, Rand, Nowak and Christakis20] used it to model obesity spread. Nieddu et al. [Reference Nieddu, Forgoston and Billings27] derived analytic quantities of the model to understand the parameter space where the disease is endemic.
The most systematic study of the model appears in a series of papers by Van Mieghem, alone and with a number of co-authors [Reference Achterberg, Prasse and Van Mieghem1, Reference Van Mieghem30–Reference Van Mieghem and Wang32]. In [Reference Van Mieghem30] an exact expression is used for the mean prevalence (i.e. the expectation of
$X_N$
) in equilibrium to identify a sharp phase transition in this mean as
$\lambda/\mu$
varies, for fixed N and a fixed very small positive value of
$\varepsilon$
. A follow-up paper [Reference Van Mieghem and Wang32] studies time-dependent behaviour in this regime. We remark that known results about the supercritical classical logistic SIS model (
$\lambda/\mu > 1$
) help to explain this phase transition phenomenon. When
$\lambda/\mu > 1$
and
$\varepsilon$
is much smaller than
$1/N$
, the behaviour of the
$\varepsilon$
-SIS model is very similar to that of the usual logistic SIS model in the supercritical regime, except that after reaching state 0, the process restarts after the next self-infection, so that the mean waiting time in state 0 is
$(N\varepsilon)^{-1}$
. It is known (see e.g. [Reference Andersson and Djehiche4]) that the duration of the supercritical logistic epidemic is asymptotically exponential with a mean whose leading term is
${\mathrm{e}}^{\gamma N}$
, with
$\gamma = \log (\lambda / \mu) - 1 + \mu/\lambda$
. If
$(N\epsilon)^{-1}$
is much smaller than
${\mathrm{e}}^{\gamma N}$
, then the mean prevalence is of order N, as the
$\varepsilon$
-SIS model will be spending most of its time near the stable fixed point of the logistic equation at
$1-\mu/\lambda$
. On the other hand, if
$(N\epsilon)^{-1}$
is much larger than
${\mathrm{e}}^{\gamma N}$
, then the mean prevalence is near zero, since then most of the time the epidemic will be extinct, waiting to restart.
While the papers [Reference Van Mieghem30, Reference Van Mieghem and Wang32] assume that the population size N is fixed, the regime considered in these works is qualitatively very similar to the case where N is very large,
$\varepsilon$
is exponentially small in N, and
$\lambda$
and
$\mu$
fixed constants, and is therefore very different to the regime considered in the present paper.
1.2. Overview of the proof and the paper
In Section 2, we provide a brief discussion of the deterministic
$\varepsilon$
-SIS model, represented by the differential equation given in (2.1). The solution to this differential equation provides an approximation for the scaled process
$(X_N(t)/N)_{t\geq0}$
over an appropriate time scale, for large N.
In Section 3, we show in Lemma 3.1 that for a (deterministic) period of time that is stretched exponential in N, with high probability the scaled process
$(X_N(t)/N)$
is at most
$O(N^{-\frac{1-h}{2}})$
, for some fixed
$h\in(0,1),$
away from the solution of (2.1). In addition, we show in Lemma 3.2 that for large enough times t, the mean of
$X_N(t)/N$
is within
$O(N^{-1/2})$
of the stable fixed point
$x^{\star}$
of (2.1), given explicitly in (2.2).
In Section 4, we obtain an upper bound on the mixing time of the
$\varepsilon$
-SIS model. We show that by time
$t_N+\xi$
, where
$\xi$
is a constant that is independent of any parameters of the model and the population size N, the distribution of the chain
$X_N(t)$
is sufficiently close to its stationary distribution
$\pi_N$
. This is done by using the Markov chain coupling method, where the coupling used consists of running two copies of the chain independently over three phases. During the burn-in phase, the concentration results of Section 3 imply that by time
$\frac{1-h}{2J}\log(N)$
, both copies are within
$O(N^{\frac{1+h}{2}})$
of
$x^{\star}N$
with high probability; see Corollary 4.1. Given that this event has occurred, during the intermediate phase the copies come within
$O(\sqrt{N})$
of each other after an additional
$\frac{h}{2J}\log(N)+\xi/2$
time with high probability; see Lemma 4.4. In the final phase, given that the copies are within
$\sqrt{N}$
of each other, their distance may be compared to an unbiased random walk which hits 0 from a state of order
$\sqrt{N}$
within a constant time, given that the transition rate is of order N; see Lemma 4.5.
In Section 5, we obtain a lower bound on the mixing time. We first show an improved version of the concentration inequality given in Section 3, which holds only if the starting state of the chain
$X_N(t)$
is in a ‘good set’. We then split the proof of the lower bound into two parts. First, we combine the rapidly mixing result from the previous section and the improved concentration inequality to show that the stationary distribution
$\pi_N$
is concentrated within a ball of order
$\sqrt{N}$
around
$x^{\star}N$
. Then we use concentration around the deterministic solution to show that most of the mass of
$X_N(t_N-\xi)$
is located outside that ball, and thus by the time
$t_N-\xi$
the distribution of the chain cannot be close to stationary.
Finally, as mentioned already, for very small
$\varepsilon$
the
$\varepsilon$
-SIS model mixes twice as fast as the classical subcritical SIS model. To see why this is the case, for the
$\varepsilon$
-SIS model, the (non-normalised) process arrives within distance
$\sqrt{N}$
of the fixed point
$x^{\star}N$
, where most of the mass of the stationary distribution lies, after time of order approximately
$\frac{1}{2(\mu-\lambda)}\log(N)$
. After that, the stochastic model can be shown to do better than the deterministic one, as we can compare its behaviour to that of an unbiased random walk in continuous time taking steps at a rate of order N, since the transition rates remain of order N throughout. Such a random walk will hit 0 in constant time with high probability.
For the classical subcritical SIS model, the process also arrives within
$\sqrt{N}$
of 0 after about
$\frac{1}{2(\mu-\lambda)}\log(N)$
time. However, at that point events happen at a rate of order only
$\sqrt{N}$
and decrease as we get closer to 0, so any comparison with an unbiased random walk would be useless. Instead, we need to keep taking advantage of the negative drift right until the end, first following the differential equation closely and then approximating by a linear birth-and-death process.
2. Deterministic version of the
$\varepsilon$
--SIS model
In this section, we consider the deterministic version of the logistic SIS model with self-infection. The model represents a spreading epidemic governed by the autonomous ordinary differential equation (ODE)
\begin{equation} \frac{{\mathrm{d}} x}{{\mathrm{d}} t}=\lambda x(1-x)+\varepsilon(1-x)-\mu x, \quad t\geq0,\end{equation}
where
$\lambda, \mu, \varepsilon>0$
. The proportion of infected people at time t is modelled by x(t). When
$\varepsilon=0$
, we recover the classical deterministic logistic SIS model.
We solve the equation
$f(x)=\lambda x(1-x)+\varepsilon(1-x)-\mu x=0$
to identify the fixed points. There are two solutions to the equation, however, and since only non-negative solutions have a biological meaning, we require
$ x(t)\geq 0$
for all
$t\geq0$
in (2.1). The only fixed point that falls in this range is
\begin{equation} x^{\star}=\frac{1}{2\lambda}\left((\lambda-\mu-\varepsilon)+\sqrt{(\lambda-\mu-\varepsilon)^2+4\lambda\varepsilon}\right)\,:\!=\,\frac{\lambda-\mu-\varepsilon+J}{2\lambda},\end{equation}
where we recall from the statement of Theorem 1.1 that
$J= \sqrt{(\lambda-\mu-\varepsilon)^2+4\lambda\varepsilon}$
. Since x(t) models the proportion of infected people,
$x^{\star}=(\lambda-\mu-\varepsilon+J)/(2\lambda)\leq1$
, as one would expect. When
$\varepsilon=0$
, the solution simplifies to
$\frac{\lambda-\mu}{\lambda}$
if
$\lambda>\mu$
, whereas if
$\lambda<\mu$
the solution degenerates to zero. The other solution is
\begin{equation*} x_1^{\star}=\frac{1}{2\lambda}\left((\lambda-\mu-\varepsilon)-\sqrt{(\lambda-\mu-\varepsilon)^2+4\lambda\varepsilon}\right)\,:\!=\,\frac{\lambda-\mu-\varepsilon-J}{2\lambda},\end{equation*}
which is non-positive and degenerates to zero when
$\varepsilon=0$
, provided
$\lambda>\mu$
. The following proposition is easily verified by simple calculations and standard results, such as Theorem 2.4.2 in [Reference Boyce, DiPrima and Villagómez Velázquez9].
Proposition 2.1. The differential equation (2.1) subject to the initial condition
$x(0)=\alpha\in[0,1]$
has an explicit solution
\begin{equation} x(t)=x^{\star}+\frac{\frac{J}{\lambda}(\alpha-x^{\star})}{(\alpha-x_1^{\star}){\mathrm{e}}^{tJ}-(\alpha-x^{\star})}, \quad \text{where } J=\sqrt{(\lambda-\mu-\varepsilon)^2+4\lambda\varepsilon}.\end{equation}
It is easy to see from (2.3) that as
$t\to\infty$
, the solution monotonically approaches
$x^{\star}$
from below if
$0\leq \alpha < x^{\star}$
, whereas it monotonically approaches
$x^{\star}$
from above if
$x^{\star} < \alpha\leq 1$
. This can also be seen from the phase diagram. The graph of f(x) versus x is a downward parabola, so
${\mathrm{d}} x/{\mathrm{d}} t>0$
when
$0\leq x < x^{\star}$
and
${\mathrm{d}} x/{\mathrm{d}} t<0$
if
$x^{\star} < x\leq1$
. This implies that regardless of the starting point, any solution of (2.1) approaches
$x^{\star}$
monotonically as
$t\to\infty$
, so the fixed point
$x^{\star}$
is globally attractive over the set [0,1].
3. Concentration around the deterministic process
For the rest of this paper, we use x(t) to denote the solution to the governing equation (2.1) with initial state
$x(0)=X_N(0)/N$
. There are two main results of this section. We first show that the scaled process
$X_N(t)/N$
closely follows the solution x(t) defined in (2.3). To be precise, we prove the following result.
Lemma 3.1. There exist positive constants
$C_1$
and
$C_2$
depending only on
$\lambda$
,
$\mu$
, and
$\varepsilon$
such that for all
$h\in(0,1)$
, the following relation holds for all N large enough (depending on
$\lambda$
,
$\mu$
,
$\varepsilon$
, and h; see (3.11)):
\begin{equation} \mathbb{P}\left(\sup_{t\leq t_{\mathrm{follow}}}\left\lvert\frac{X_N(t)}{N}-x(t)\right\rvert>C_2N^{-\frac{1-h}{2}}\right)\leq 4{\mathrm{e}}^{-C_1N^h},\end{equation}
where
\begin{equation} t_{\mathrm{follow}}\equiv t_{\mathrm{follow}}(N, h)\,:\!=\,\tfrac{1}{J} \lceil {\mathrm{e}}^{C_1N^{h}}\rceil.\end{equation}
As will be seen in the proof, it is enough to consider h fixed (say equal to
$1/2$
), so the dependence of N and
$t_{\mathrm{follow}}$
on h is ultimately not important.
The other result in this section controls the mean of
$X_N(t)/N$
and is used in the proof of the lower bound on the mixing time in Section 5.
Lemma 3.2. Let
$\mathbb{E}_{x_0}$
be the expectation given the starting state
$X_N(0)=x_0$
. The following two statements hold.
-
(i) There exists a positive constant
$K_1$
, depending only on
$\lambda$
,
$\mu$
, and
$\varepsilon$
, such that for any
$c\in\mathbb{R}$
and N large enough (depending on
$\lambda$
,
$\mu$
,
$\varepsilon$
, and c),
\begin{equation*} \left\lvert \,\mathbb{E}_{x_0}\Big(X_N\big(\tfrac{1}{2J}\log(N)+c\big)\Big)-x^{\star}N \right\rvert\leq K_1 {\mathrm{e}}^{-Jc}\sqrt{N}. \end{equation*}
-
(ii) Suppose that
$x_0/N-x^{\star} > \alpha$
for some
$\alpha > 0$
. Then there exists a positive constant
$K_2$
, depending on
$\lambda$
,
$\mu$
,
$\varepsilon$
, and
$\alpha$
, such that for any
$c\in\mathbb{R}$
and N large enough (depending on
$\lambda$
,
$\mu$
,
$\varepsilon$
,
$\alpha$
, and c),
\begin{equation*} K_2 {\mathrm{e}}^{-Jc}\sqrt{N}\leq \mathbb{E}_{x_0}\Big(X_N\big(\tfrac{1}{2J}\log(N)+c\big)\Big)-x^{\star}N. \end{equation*}
3.1. Proof of Lemma 3.1
We study the centred processes
$Y_N(t)\,:\!=\,X_N(t)/N - x^{\star}$
and
$y(t)\,:\!=\,x(t)-x^{\star}$
, with
$x(0)=X_N(0)/N$
. The overall strategy of the proof is to give an integral representation of the deterministic process y(t) (Lemma 3.3), which can be compared with a similar representation of
$Y_N(t)$
but with the addition of a martingale term (Lemma 3.4). From here, the result essentially follows by controlling the martingale term (Lemma 3.6) using a simplified version of [Reference Lopes and Luczak24, Lemma 3.7] (stated here as Lemma 3.5) and then applying Grönwall’s lemma.
We first give a representation of y(t).
Lemma 3.3. In the notation just defined, we have
\begin{equation} y(t)=y(0)-\int_0^t \lambda y^2(s)+Jy(s)\,{\mathrm{d}} s \end{equation}
and
\begin{equation} y(t)={\mathrm{e}}^{-Jt}y(0)-\int_0^t \lambda {\mathrm{e}}^{-J(t-s)} y^2(s)\,{\mathrm{d}} s. \end{equation}
Proof. Using the definition of
$x^{\star}$
, the governing equation (2.1) can be rewritten as
\begin{equation*} \frac{{\mathrm{d}} x}{{\mathrm{d}} t}=-\lambda(x-x^{\star})\left(x-x^{\star}+\frac{J}{\lambda}\right), \end{equation*}
which is the same as
\begin{equation} \frac{{\mathrm{d}} y}{{\mathrm{d}} t}=-\lambda y^2-Jy. \end{equation}
From here, (3.3) follows by integration. Moreover, a simple calculation using (3.5) shows that
\begin{equation*} \frac{{\mathrm{d}}}{{\mathrm{d}} s}{\mathrm{e}}^{-J(t-s)}y(s)=-\lambda {\mathrm{e}}^{-J(t-s)} y^2(s), \end{equation*}
which is the same as (3.4) after integrating.
We compare
$Y_N(t)=X_N(t)/N-x^{\star}$
with y(t) via a representation that is similar to (3.4).
Lemma 3.4. In the notation just defined, we have
\begin{equation} Y_N(t)={\mathrm{e}}^{-Jt}Y_N(0)-\int_0^t \lambda {\mathrm{e}}^{-J(t-s)}Y^2_N(s)\,{\mathrm{d}} s+\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} M_N(s),\end{equation}
where
\begin{equation} M_N(t)\,:\!=\,Y_N(t)-Y_N(0)+\int_0^t \lambda Y^2_N(s)-JY_N(s)\,{\mathrm{d}} s\end{equation}
is a zero-mean martingale.
Proof. To show that the process
$M_N(t)$
defined in (3.7) is a martingale, note that the family of Markov chains
$(X_N(t))_{N\geq1}$
is a density-dependent family (see [Reference Kurtz22, Section 4]) with transitions of the form
\begin{align*} &x\mapsto x+1\quad \text{at rate } Nf\!\left(\frac{x}{N}, +1\right)\,:\!=\, N\cdot\left(\lambda \frac{x}{N}\left(1-\frac{x}{N}\right)+\varepsilon\left(1-\frac{x}{N}\right)\right),\\ &x\mapsto x-1\quad \text{at rate } Nf\!\left(\frac{x}{N}, -1\right)\,:\!=\,N\cdot\mu\frac{x}{N}\, , \end{align*}
and the state space
$\{0, 1,\ldots, N\}$
is compact. It is easy to check that the scaled process
$(X_N(t)/N)_{t\geq0}$
satisfies the conditions of [Reference Kurtz22, Proposition 2.1] and hence
\begin{equation*} M_N(t)\,:\!=\,\frac{X_N(t)}{N}-\frac{X_N(0)}{N}-\int_0^tF\left(\frac{X_N(s)}{N}\right)\,{\mathrm{d}} s \end{equation*}
is a zero-mean martingale, where
$F(x)=f(x, +1)-f(x, -1)$
. Then formula (3.6) holds by [Reference Barbour and Luczak7, Lemma 4.1].
Comparing expressions (3.4) and (3.6), it is clear that to be able to approximate
$Y_N(t)$
by y(t), we must control the size of
$\big\lvert\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} M_N(s)\big\rvert$
. To do this, we use the following simplified version of [Reference Lopes and Luczak24, Lemma 7] for multi-dimensional Markov jump chains.
Lemma 3.5. ([Reference Lopes and Luczak24, Lemma 7].) Let
$(X(t))_{t\geq0}$
be a pure-jump Markov chain with state space
$E\subseteq\mathbb{R}$
. For
$x,l\in\mathbb{R}$
such that
$x, x+l \in E$
, let
$q(x, x+l)$
denote the rate at which the chain jumps from x to
$x+l$
, and assume that there is a deterministic
$B>0$
such that
$q(x, x+l)=0$
for
$\lvert l \rvert >B$
. Suppose further that for each
$x\in E$
, the drift
$F(x)\,:\!=\,\sum_{l}lq(x, x+l)$
at x can be written in the form
\begin{equation*} F(x)=\widetilde{A}x+\widetilde{F}(x) \quad {for\ some\ } \widetilde{A}\leq 0.\end{equation*}
Let
$(M(t))_{t\geq0}$
be the corresponding Dynkin martingale given by
\begin{equation*} M(t)\,:\!=\,X(t)-X(0)-\int_0^t F(X(s))\,{\mathrm{d}} s,\end{equation*}
and let
$\widetilde{M}(t)=\int_0^t {\mathrm{e}}^{\widetilde{A}(t-s)}\,dM(s)$
. For
$\delta>0$
, define
$\widetilde{T}(\delta)=\inf\{t\geq0:\lvert \widetilde{M}(t)\rvert>\delta\}$
to be the infimum of the times t such that
$\widetilde{M}(t)$
exceeds
$\delta$
in absolute value. Further, given
$u\in\mathbb{R}_+$
, let
$\nu(z, u)\,:\!=\,\sum_w q(z, z+w)({\mathrm{e}}^{\widetilde{A}u}w)^2$
, and suppose that for some
$K>0$
,
$\int_0^t \nu(X(s), t-s)\,{\mathrm{d}} s\leq K$
. Then for any
$\sigma>0$
and
$0 < \omega\leq 4(\log2)^2K/B^2$
, we have
\begin{equation*} \mathbb{P}\big(\widetilde{T}({\mathrm{e}}^{-\widetilde{A}\sigma}\sqrt{\omega K})\leq \sigma \lceil {\mathrm{e}}^{\omega/8} \rceil\big)\leq 4{\mathrm{e}}^{-\omega/8}.\end{equation*}
Specialising the lemma to our setting, we obtain the following result, which controls the size of the term
$\big\lvert\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} M_N(s)\big\rvert$
.
Lemma 3.6. Fix
$h\in(0,1)$
, and set
$\omega\,:\!=\,4(\log2)^2kN^h$
,
$k\,:\!=\,(\lambda+\mu+\varepsilon)/(2J)$
, and
\begin{equation*} T_1\,:\!=\,\inf\left\{t\geq0\;:\; \left\lvert\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} M_N(s)\right\rvert>{\mathrm{e}}\sqrt{\frac{\omega k}{N}}\right\}. \end{equation*}
Then
\begin{equation*} \mathbb{P}\Big(T_1\leq \frac{1}{J}\big\lceil {\mathrm{e}}^{\omega/8}\big\rceil\Big)\leq 4{\mathrm{e}}^{-\omega/8}. \end{equation*}
Proof. We apply Lemma 3.5 to our process
$Y_N(t)$
. Clearly, the only possible jumps for
$Y_N(t)$
are
$\pm 1/N$
, so we can take
$B\,:\!=\,1/N$
. The drift
$F_X$
of
$X_N$
is given by
\begin{equation*} F_X(x)=1\cdot\lambda x\left(1-\frac{x}{N}\right)+\varepsilon(N-x)+(-1)\cdot \mu x=-\lambda N\left(\frac{x}{N}-x^{\star}\right)\left(\frac{x}{N}-x^{\star}+\frac{J}{\lambda}\right). \end{equation*}
Hence it is easily seen that the drift of
$Y_N$
is given by
$F_Y(y)=\widetilde{A}y+\widetilde{F}(y)$
, where
$\widetilde{A}=-J$
and
$\widetilde{F}(y)=-\lambda y^2$
.
Moreover, there is a uniform bound on
$\int_0^t\nu(Y_N(s), t-s)\,{\mathrm{d}} s$
, where we write
$\nu(z, u)\,:\!=\,\sum_w q(z, z+w)({\mathrm{e}}^{-Ju}w)^2$
and
$q(y, y+w)$
is the rate of the jump from y to
$y+w$
for
$y\in\{0, 1, \ldots, N\}/N$
and
$w = \pm 1/N$
:
\begin{align*} &\int_0^t\nu(Y_N(s), t-s)\,{\mathrm{d}} s\nonumber\\ &\quad=\int_0^t\left(\lambda X_N(s)\left(1-\frac{X_N(s)}{N}\right)+\varepsilon\left(N-X_N(s)\right)+\mu X_N(s)\right){\mathrm{e}}^{-2J(t-s)}N^{-2}\,{\mathrm{d}} s\nonumber\\ &\quad=\frac{1}{N}\int_0^t\left(\lambda \frac{X_N(s)}{N}\left(1-\frac{X_N(s)}{N}\right)+\varepsilon\left(1-\frac{X_N(s)}{N}\right)+\mu\frac{X_N(s)}{N}\right){\mathrm{e}}^{-2J(t-s)}\,{\mathrm{d}} s\nonumber\\ &\quad\leq \frac{1}{N}\int_0^t\left((\lambda+\mu)\frac{X_N(s)}{N}+\varepsilon\right){\mathrm{e}}^{-2J(t-s)}\,{\mathrm{d}} s\nonumber\\ &\quad\leq \frac{\lambda+\mu+\varepsilon}{N}\int_0^t{\mathrm{e}}^{-2J(t-s)}\,{\mathrm{d}} s\leq\frac{k}{N}. \end{align*}
The result then follows directly from Lemma 3.5 upon setting
$\sigma=\frac{1}{J}$
and
$K=k/N$
.
The last missing ingredient for the proof of Lemma 3.1 is a quantitative upper bound on the speed of convergence of the solution to the governing equation (2.1) with initial condition
$x(0)=X_N(0)/N$
to the fixed point
$x^{\star}$
. This will then be used to bound
$\lvert Y_N(t)-y(t) \rvert= \lvert X_N(t)-x(t) \rvert$
. The following lemma, with an elementary calculus proof, gives such a bound.
Lemma 3.7. Using the notation defined above, the following inequality holds:
\begin{equation} \lvert y(t) \rvert\leq\frac{2J}{J-(\lambda-\mu-\varepsilon)}\,\lvert y(0)\rvert \,{\mathrm{e}}^{-tJ}, \quad t\geq0.\end{equation}
Proof. Recall that
$x^{\star}=\frac{\lambda-\mu-\varepsilon+J}{2\lambda}\geq 0$
and
$x_1^{\star}=\frac{\lambda-\mu-\varepsilon-J}{2\lambda}\leq 0$
, where
$J=\sqrt{(\lambda-\mu-\varepsilon)^2+4\lambda\varepsilon}$
. We have
$-x^{\star} \leq y(0) \leq 1-x^{\star}$
. Also, from (2.3) and the fact
$J/\lambda\geq x^{\star}$
, we obtain
\begin{align*} \lvert y(t) \rvert &=\left\lvert\frac{J}{2\lambda}\frac{2 y(0)}{(x^{\star}-x_1^{\star}+y(0)){\mathrm{e}}^{tJ}-y(0)}\right\rvert =\frac{\frac{J}{\lambda}\lvert y(0) \rvert}{\left(\frac{J}{\lambda}+y(0)\right){\mathrm{e}}^{tJ}-y(0)} \\ &=\frac{\frac{J}{\lambda}\lvert y(0)\rvert}{\frac{J}{\lambda}+(1-{\mathrm{e}}^{-tJ}) y(0)}\,{\mathrm{e}}^{-tJ}.\end{align*}
It then follows by easy manipulation that
\begin{equation*} \lvert y(t) \rvert\leq \frac{\frac{J}{\lambda}\lvert y(0)\rvert }{\frac{J}{\lambda}-(1-{\mathrm{e}}^{-tJ})x^{\star}}\,{\mathrm{e}}^{-tJ} \leq\frac{\frac{J}{\lambda}\lvert y(0)\rvert }{\frac{J}{\lambda}-\frac{\lambda-\mu-\varepsilon+J}{2\lambda}}\,{\mathrm{e}}^{-tJ} =\frac{2J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0)\rvert \,{\mathrm{e}}^{-tJ}.\end{equation*}
We can now prove Lemma 3.1. As previously discussed, we use representations (3.4) and (3.6) to bound the difference between
$X_N(t)/N$
and x(t), and use Lemma 3.6 to control the martingale term in (3.6).
Proof of Lemma 3.1. Using (3.4) and (3.6), we have
\begin{align*} \widetilde{e}_N(t)&\,:\!=\,\lvert Y_N(t)-y(t)\rvert \\ &\leq\lambda\int_0^t {\mathrm{e}}^{-J(t-s)}\left\lvert Y_N(s)^2-y(s)^2\right\rvert\,{\mathrm{d}} s+\left\lvert\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} M_N(s)\right\rvert\\ &\leq\lambda\int_0^t {\mathrm{e}}^{-J(t-s)} \widetilde{e}_N(s)(\widetilde{e}_N(s)+2\lvert y(s)\rvert)\,{\mathrm{d}} s+\left\lvert\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} M_N(s)\right\rvert.\end{align*}
Using (3.8) to bound
$\lvert y(s) \rvert$
, we obtain
\begin{align} \begin{split} \widetilde{e}_N(t)\leq\frac{4\lambda J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert {\mathrm{e}}^{-Jt}\int_0^t\widetilde{e}_N(s)\,{\mathrm{d}} s & +\lambda\int_0^t {\mathrm{e}}^{-J(t-s)} \widetilde{e}_N(s)^2\,{\mathrm{d}} s\\ &+\left\lvert\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} M_N(s)\right\rvert. \end{split}\end{align}
To bound the first two terms on the right-hand side of (3.9), we define
\begin{equation*} T_2\,:\!=\,\inf\left\{t:\widetilde{e}_N(t)>3\widetilde{C}\sqrt{\frac{\omega k}{N}}\right\},\end{equation*}
where
$\widetilde{C}\,:\!=\,4{\mathrm{e}}^{\frac{4\lambda}{J-(\lambda-\mu-\varepsilon)}(x^{\star}\vee (1-x^{\star}))}$
(the exact form is not so important). Recall the definitions of
$T_1$
,
$\omega$
, and k from Lemma 3.6. We will show that on the event
$t\leq T_1 \wedge T_2$
, one has
\begin{equation} \widetilde{e}_N(t)\leq\widetilde{C}\sqrt{\frac{\omega k}{N}}.\end{equation}
For now, suppose that this is true. Define
\begin{equation*} T_3\,:\!=\,\inf\left\{t:\widetilde{e}_N(t)>2\widetilde{C}\sqrt{\frac{\omega k}{N}}\right\}.\end{equation*}
By definition,
$\mathbb{P}(T_3 \leq T_2)=1$
. Moreover, since we have assumed that (3.10) holds, we also have
$\mathbb{P}(T_3\leq T_1 \wedge T_2)=0$
, which implies that
$0=\mathbb{P}(T_3\leq T_1\wedge T_2)=\mathbb{P}(T_3\leq T_1)$
. Applying Lemma 3.6, we obtain
\begin{equation*} \mathbb{P}\Big(T_3\leq\mbox{$\frac{1}{J}$}\lceil {\mathrm{e}}^{\omega/8}\rceil\Big)\leq\mathbb{P}\Big(T_1\leq\mbox{$\frac{1}{J}$}\lceil {\mathrm{e}}^{\omega/8}\rceil\Big)\leq4{\mathrm{e}}^{-\omega/8},\end{equation*}
which completes the proof. It only remains to check (3.10). On the event
$t\leq T_1$
, it follows from (3.9) that
\begin{equation*} \widetilde{e}_N(t)\leq\frac{4\lambda J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert {\mathrm{e}}^{-Jt}\int_0^t \widetilde{e}_N(s)\,{\mathrm{d}} s+\lambda\int_0^t {\mathrm{e}}^{-J(t-s)} \widetilde{e}_N(s)^2\,{\mathrm{d}} s+{\mathrm{e}}\sqrt{\frac{\omega k}{N}}.\end{equation*}
To further bound
$\widetilde{e}_N(t)$
, a standard method is to use Grönwall’s lemma (see e.g. [Reference Ames and Pachpatte3, Theorem 1.3.1]). However, to apply the inequality we first need to control the
$\widetilde{e}_N^2$
term. On the event
$t\leq T_1 \wedge T_2$
, one has
\begin{align*} \widetilde{e}_N(t)&\leq \frac{4\lambda J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert {\mathrm{e}}^{-tJ}\int_0^t \widetilde{e}_N(s)\,{\mathrm{d}} s+9\lambda\widetilde{C}^2\frac{\omega k}{N}\int_0^t {\mathrm{e}}^{-J(t-s)}\,{\mathrm{d}} s+{\mathrm{e}}\sqrt{\frac{\omega k}{N}}\\ &\leq\frac{4\lambda J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert {\mathrm{e}}^{-tJ}\int_0^t \widetilde{e}_N(s)\,{\mathrm{d}} s+\frac{9\lambda\widetilde{C}^2}{J}\frac{\omega k}{N}+{\mathrm{e}}\sqrt{\frac{\omega k}{N}}.\end{align*}
Choose
$N>(18k\lambda\widetilde{C}^2J^{-1}\log{2} )^{\frac{2}{1-h}}$
so that
\begin{equation} \frac{9\lambda\widetilde{C}^2}{J}\frac{\omega k}{N}=\frac{18k\lambda\widetilde{C}^2\log{2} }{J}N^{-\frac{1-h}{2}}\sqrt{\frac{\omega k}{N}}<\sqrt{\frac{\omega k}{N}}\end{equation}
and hence
\begin{equation*} \widetilde{e}_N(t)\leq\frac{4\lambda J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert {\mathrm{e}}^{-Jt}\int_0^t \widetilde{e}_N(s)\,{\mathrm{d}} s+4\sqrt{\frac{\omega k}{N}}.\end{equation*}
Let
$\widehat{e}_N(t)={\mathrm{e}}^{tJ}\widetilde{e}_N(t)$
; then on the event
$t\leq T_1 \wedge T_2$
we have
\begin{equation*} \widehat{e}_N(t)\leq\frac{4\lambda J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert\int_0^t {\mathrm{e}}^{-sJ}\widehat{e}_N(s)\,{\mathrm{d}} s+4{\mathrm{e}}^{tJ}\sqrt{\frac{\omega k}{N}}\end{equation*}
for N large enough. Applying Grönwall’s lemma to
$\widehat{e}_N(t)$
, we obtain that for
$t\leq T_1 \wedge T_2$
,
\begin{align*} \widehat{e}_N(t)\leq4{\mathrm{e}}^{\frac{4\lambda J}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert\frac{1-{\mathrm{e}}^{-tJ}}{J}}\sqrt{\frac{\omega k}{N}}\,{\mathrm{e}}^{tJ}&\leq4{\mathrm{e}}^{\frac{4\lambda}{J-(\lambda-\mu-\varepsilon)}\lvert y(0) \rvert}\sqrt{\frac{\omega k}{N}}\,{\mathrm{e}}^{tJ}\end{align*}
Dividing both sides of the inequality by
${\mathrm{e}}^{tJ}$
then establishes (3.10) as
$\lvert y(0) \rvert \leq x^{\star}\vee (1-x^{\star})$
.
3.2. Proof of Lemma 3.2
To explain the proof of the other main result of this section, write
$y_0=x_0/N-x^{\star}$
, which is the corresponding starting state of the chain
$Y_N(t)$
. Recall the definition of
$M_N(t)$
in (3.7), Since
$\mathbb{E}(M_N(t))=0$
for all
$t\geq0$
, we have
\begin{align} \mathbb{E}_{x_0}(Y_N(t))&=y_0-\mathbb{E}_{x_0}\!\left(\int_0^t JY_N(s)\,{\mathrm{d}} s\right)-\mathbb{E}_{x_0}\!\left(\int_0^t \lambda Y^2_N(s)\,{\mathrm{d}} s\right)\nonumber\\ &= y_0-\int_0^t J\mathbb{E}_{x_0}\!\left(Y_N(s)\right)\,{\mathrm{d}} s-\int_0^t \lambda\mathbb{E}_{x_0}\!\left( Y^2_N(s)\right){\mathrm{d}} s, \end{align}
where we have used Fubini’s theorem in the last equality to change the order of the expectation and the integral. If we could replace
$\mathbb{E}_{x_0}( Y^2_N(s))$
by
$(\mathbb{E}_{x_0}Y_N(s))^2$
, then
$\mathbb{E}_{x_0}(Y_N(s))$
would exactly solve the integral equation (3.4), and the claim of the lemma would be trivial. Therefore we prove the result by showing that the difference between
$\mathbb{E}_{x_0}( Y^2_N(t))$
and
$(\mathbb{E}_{x_0}Y_N(t))^2$
is small for all
$t\leq t_{\mathrm{follow}}$
, and so the difference between
$\int_0^t \lambda\mathbb{E}_{x_0}( Y^2_N(s))\,{\mathrm{d}} s$
and
$\int_0^t \lambda(\mathbb{E}_{x_0}Y_N(s))^2\,{\mathrm{d}} s$
is also small for not too large t.
Proof of Lemma
3.2. Suppose that y(t) solves (3.5), and let
$A_t\,:\!=\,\{z:\lvert z-y(t)\rvert \leq C_2 N^{-\frac{1-h}{2}}\}$
for fixed
$h< 1/2$
and
$C_2$
from Lemma 3.1. Applying that lemma with this h, we conclude that
$\mathbb{P}_{x_0}(Y_N(t)\in A_t^c)$
is exponentially small in N for
$t\leq t_{\mathrm{follow}}$
. Together with the fact that
$Y_N(t)$
is bounded for all
$t\geq0$
, we obtain
\begin{equation*} \mathbb{E}_{x_0}(Y_N(t))=\mathbb{E}_{x_0}\big(Y_N(t)\unicode{x1D7D9}_{Y_N(t)\in A_t}\big)+\mathbb{E}_{x_0}\big(Y_N(t)\unicode{x1D7D9}_{Y_N(t)\in A_t^c}\big)=y(t)+O(N^{-\frac{1-h}{2}}), \end{equation*}
and using this and a similar argument implies
\begin{align} \mathrm{Var}_{x_0}\left(Y_N(t)\right)&=\mathbb{E}_{x_0}\!\left(\left(Y_N(t)-\mathbb{E}_{x_0}(Y_N(t))\right)^2\unicode{x1D7D9}_{Y_N(t)\in A_t}\right)\nonumber\\ &\quad+\mathbb{E}_{x_0}\!\left(\left(Y_N(t)-\mathbb{E}_{x_0}(Y_N(t))\right)^2\unicode{x1D7D9}_{Y_N(t)\in A_t^c}\right)=O(N^{-(1-h)}) \end{align}
for
$t\leq t_{\mathrm{follow}}$
. Rewriting (3.12) to take advantage of these bounds, we have
\begin{equation} \mathbb{E}_{x_0}(Y_N(t)) =y_0-\int_0^t J\mathbb{E}_{x_0}\!\left(Y_N(s)\right){\mathrm{d}} s -\int_0^t \lambda\left( \mathbb{E}_{x_0}Y_N(s)\right)^2 {\mathrm{d}} s-\int_0^t \mathrm{Var}_{x_0}(Y_N(s))\,{\mathrm{d}} s. \end{equation}
With this equation and the bound (3.13), we can use standard differential equation comparison theorems to bound
$\mathbb{E}_{x_0}(Y_N(t))$
. Let
$u(t)\,:\!=\,\mathbb{E}_{x_0}(Y_N(t))$
and differentiate the integral equation (3.14) to get the initial value problem
\begin{equation} \frac{{\mathrm{d}}}{{\mathrm{d}} t}u(t)= -\lambda u^2(t)-Ju(t)-\mathrm{Var}_{x_0}(Y_N(t)), \quad u(0)=y_0, \quad t\leq t_{\mathrm{follow}}. \end{equation}
It follows from (3.13) that there exists a suitable constant
$C^*>0$
such that we have the bound
$\mathrm{Var}_{x_0}(Y_N(s))\leq C^*N^{-(1-h)}$
, and so we obtain
\begin{equation*} \frac{{\mathrm{d}}}{{\mathrm{d}} t}u(t)\geq -\lambda u^2(t)-Ju(t)-C^*N^{-(1-h)}, \quad u(0)=y_0, \quad t\leq t_{\mathrm{follow}}. \end{equation*}
From standard comparison theory of differential equations (see e.g. [Reference Ames and Pachpatte3, Theorem 2.2.2]), we have
$u(t)\geq z(t)$
for all
$t\geq0$
, where z(t) is the minimal solution to the initial value problem
\begin{equation*} \frac{{\mathrm{d}}}{{\mathrm{d}} t}z(t)= -\lambda z^2(t)-Jz(t)-C^*N^{-(1-h)}, \quad z(0)=y_0, \quad t\leq t_{\mathrm{follow}}. \end{equation*}
This differential equation is of the same form as the governing equation (2.1), so it is not hard to see that for sufficiently large N such that
$J^2-4\lambda C^*N^{-(1-h)}>0$
, the solution is uniquely defined for all
$t\geq0$
and hence
\begin{equation*} u(t)\geq z(t)=c_2 + \frac{\frac{c_1}{\lambda}(y_0-c_2)}{(y_0-c_3)-(y_0-c_2)\,{\mathrm{e}}^{-c_1t}}\,{\mathrm{e}}^{-c_1t}, \end{equation*}
where
\begin{equation*} c_1\,:\!=\,\sqrt{J^2-4\lambda C^*N^{-(1-h)}}\in(0,J), \quad c_2\,:\!=\,\frac{-J+c_1}{2\lambda} < 0, \quad c_3\,:\!=\,\frac{-J-c_1}{2\lambda}<0. \end{equation*}
For any
$h < 1/2$
, we can write
$c_1=J-\delta$
,
$c_2=-\frac{\delta}{2\lambda}$
, and
$c_3=-\frac{J}{\lambda}+\frac{\delta}{2\lambda}$
, where
$\delta=$
$o(N^{-\frac{1}{2}}) > 0$
. Using this notation, the above bound then becomes
\begin{equation} u(t)\geq z(t)= -\frac{\delta}{2\lambda} + \frac{\frac{J-\delta}{\lambda}(y_0+\frac{\delta}{2\lambda})}{(y_0+\frac{J}{\lambda}-\frac{\delta}{2\lambda}){\mathrm{e}}^{-\delta t}-(y_0+\frac{\delta}{2\lambda}){\mathrm{e}}^{-Jt}}\,{\mathrm{e}}^{-Jt}. \end{equation}
Note that if
$z(0)=y_0 > -\frac{\delta}{2\lambda}$
, then as t increases, z(t) monotonically approaches
$-\frac{\delta}{2\lambda}$
from above, whereas z(t) monotonically approaches
$-\frac{\delta}{2\lambda}$
from below if
$z(0)=y_0\in(-\frac{2J-\delta}{2\lambda}, -\frac{\delta}{2\lambda})$
. (Note that
$y_0 \le -\frac{2J-\delta}{2\lambda}$
is not biologically viable.) Moreover, for any fixed t, z(t) is monotonically increasing as
$y_0$
increases, which can be verified by differentiating (3.16) with respect to
$y_0$
.
On the other hand, since
$\mathrm{Var}_{x_0}(Y_N(t)) > 0$
, it follows from (3.15) that
\begin{equation*} \frac{{\mathrm{d}}}{{\mathrm{d}} t}u(t)\leq -\lambda u^2(t)-Ju(t), \quad u(0)=y_0, \quad t\geq 0. \end{equation*}
Again, by the comparison theorem and using (3.5), we have
\begin{equation} u(t)\leq y(t)=\frac{\frac{J}{\lambda}y_0}{\big(y_0+\frac{J}{\lambda}\big)-y_0{\mathrm{e}}^{-Jt}}\,{\mathrm{e}}^{-Jt}. \end{equation}
Similar to the behaviour of z(t), if
$y(0)=y_0>0$
then y(t) monotonically approaches 0 from above, whereas if
$y(0) \in ( - \frac{J}{\lambda}, 0)$
then y(t) monotonically approaches 0 from below. (Note that
$y_0 \le -\frac{J}{\lambda}$
is not biologically viable.) Also, by differentiating (3.17) with respect to
$y_0$
, one can see that for any fixed t, y(t) is monotonically increasing as
$y_0$
increases.
For any
$c\in\mathbb{R}$
, we take
$t=\frac{1}{2J}\log(N)+c$
, which is then non-negative for N sufficiently large. If in the right-hand side of the relation (3.16) one has
$y_0=x_0/N-x^{\star}>\alpha>0$
, then, since
${\mathrm{e}}^{-\delta t} \to1$
and
${\mathrm{e}}^{-Jt} \to0$
as
$N\to\infty$
, we obtain
\begin{align*} u(t)\geq z(t) \geq \left(o(1)+\left( \frac{\alpha\frac{J}{\lambda}}{\alpha+\frac{J}{\lambda}} + o(1)\right)\right) \frac{{\mathrm{e}}^{-Jc}}{\sqrt{N}}. \end{align*}
Therefore, there exists a constant
$K_2$
depending on
$\lambda, \mu, \varepsilon$
, and
$\alpha$
such that for N large enough,
\begin{equation} u(t)\geq z(t) \geq \frac{{\mathrm{e}}^{-Jc}K_2}{\sqrt{N}}, \end{equation}
which finishes the proof of the second statement in Lemma 3.2. For the first statement, in view of (3.16) and (3.17) and the monotonicity of y(t) and z(t) with respect to the initial value
$y_0$
, one has, for any
$0 < y_0 \leq 1-x^{\star}$
,
\begin{equation} -\frac{\delta}{2\lambda} < z(t) ,\qquad 0 < y(t) \leq \bar{y}(t), \end{equation}
where
\begin{equation*} \bar{y}(t)\,:\!=\,\frac{\frac{J}{\lambda}(1-x^{\star})}{(1-x^{\star}+\frac{J}{\lambda})-(1-x^{\star}){\mathrm{e}}^{-Jt}}\,{\mathrm{e}}^{-Jt}. \end{equation*}
Similarly, for any
$-x^{\star} \leq y_0 < -\frac{\delta}{2\lambda}$
,
\begin{equation} \underline{z}(t) \leq z(t) \leq y(t) < 0, \end{equation}
where
\begin{equation*} \underline{z}(t)\,:\!=\,-\frac{\delta}{2\lambda} + \frac{\frac{J-\delta}{\lambda}(-x^{\star}+\frac{\delta}{2\lambda})}{(-x^{\star}+\frac{J}{\lambda}-\frac{\delta}{2\lambda}){\mathrm{e}}^{-\delta t}-(-x^{\star}+\frac{\delta}{2\lambda}){\mathrm{e}}^{-Jt}}\,{\mathrm{e}}^{-Jt}. \end{equation*}
Also, observe that when
$y_0\in[-\frac{\delta}{2\lambda},0]$
, we have
$z(t), y(t) \in [-\frac{\delta}{2\lambda},0]$
for all
$t\geq0$
. Since
$\lvert u(t) \rvert \leq \lvert z(t) \rvert \vee \lvert y(t) \rvert$
, it follows from (3.19), (3.20), and the previous observation that
\begin{equation*} \lvert u(t) \rvert\leq \begin{cases} -\underline{z}(t), & y_0\in [-x^{\star},-\frac{\delta}{2\lambda}),\\ \frac{\delta}{2\lambda}, & y_0\in[-\frac{\delta}{2\lambda},0],\\ \frac{\delta}{2\lambda}\vee\bar{y}(t), & y_0\in (0, 1-x^{\star}]. \end{cases} \end{equation*}
Now, fix any
$h < 1/2$
so that
$\delta=o(N^{-\frac{1}{2}})>0$
. The proof is completed by noticing that for some positive constants
$K_1^*$
and
$K_1'$
depending only on
$\lambda, \mu$
, and
$\varepsilon,$
one has
\begin{equation*} \bar{y}(t)\leq \frac{{\mathrm{e}}^{-Jc}K_1^*}{\sqrt{N}}, \qquad -\underline{z}(t)\leq \frac{{\mathrm{e}}^{-Jc}K_1'}{\sqrt{N}} \end{equation*}
for N large enough.
4. Proof of the upper bound for the mixing time
In this section, we prove the upper bound in Theorem 1.1, which in particular shows that for a population of size N, the mixing time of the Markov chain
$X_N$
is asymptotically at most
$\frac{1}{2J}\log N$
.
Recall
$\rho_N(t)=\max_{x\in\{0,1,\ldots,N\}}\lVert P^t_N(x,\cdot)-\pi_N \rVert_{\rm TV}$
and
$t_N=\frac{1}{2J}\log(N)$
from Definition 1.1 and Theorem 1.1.
Lemma 4.1. (Cutoff upper bound, rapid mixing.) For all
$\xi\geq0$
, we have
\begin{equation*} \limsup_{N\to\infty}\rho_N(t_N+\xi)\leq \psi_1(\xi),\end{equation*}
where
$\psi_1(\cdot)$
is a non-negative real-valued function depending only on
$\lambda, \mu,$
and
$\varepsilon$
and
$\psi_1(\xi)=O(1/\sqrt{\xi})$
as
$\xi\to\infty$
.
Let
$Z_N(t)$
and
$W_N(t)$
be two copies of the process
$X_N(t)$
, with initial states
$Z_N(0)\geq W_N(0)$
, moving independently until the coalescence time, which is defined as
\begin{equation*} \tau_{\text{couple}}\,:\!=\,\inf\{t\;:\; W_N(t)=Z_N(t)\}.\end{equation*}
After the coalescence time, the states in the two copies are the same and move together for ever after. Note that this defines a Markovian coupling.
By standard results (see [Reference Levin and Peres23, Corollary 5.5]), to prove Lemma 4.1, it is sufficient to show the following. Write
$\mathbb{P}_{w_0,z_0}$
for the probability measure of the chain given
$W_N(0)=w_0$
and
$Z_N(0)=z_0$
.
Lemma 4.2. For all
$w_0, z_0\in \{0,\ldots,N\}$
with
$w_0\leq z_0$
and all
$\xi\geq 0$
, we have
\begin{equation*}\limsup_{N\to\infty}\mathbb{P}_{w_0,z_0}\big(\tau_{\mathrm{couple}}>\mbox{$\frac{1}{2J}$}\log(N)+\xi\big)\leq\psi_1(\xi),\end{equation*}
where
$\psi_1(\cdot)$
is a non-negative real-valued function depending only on
$\lambda, \mu,$
and
$\varepsilon$
and
$\psi_1(\xi)=O(1/\sqrt{\xi})$
as
$\xi\to\infty$
.
Before diving into the details, we give an outline of the proof. As mentioned in the introduction, we split the analysis into the following phases.
Initial phase: We use the concentration result from Section 3 to show that with high probability, by the time
$\frac{1-h}{2J}\log(N)$
, both copies
$W_N(t)$
and
$ Z_N(t)$
will be in the interior of a good set consisting of a ball of size
$O(N^{\frac{1+h}{2}})$
around
$x^{\star}N$
. We also prove that if the copies start anywhere in the interior of the good set, then with high probability they remain in the good set for a time period that is exponential in N.
Intermediate phase: After both copies reach the interior of the good set, the independent coupling of the chains is contractive while the copies stay in the good set. As a consequence, after another
$\frac{h}{2J}\log(N)$
time (plus a constant time), the distance between the copies will drop to
$\sqrt{N}$
with high probability.
Final phase: Once the copies are within
$\sqrt{N}$
of each other and given that they are still in the good set, we show that the coalescence time of the copies is no greater than the time it takes for an unbiased random walk (with transition rate of order N so that, on average, there are N events happening in a unit time period) to hit 0, which is at most a time of constant order with high probability.
Throughout the rest of this section, we use
$\mathbb{P}_{x_0}(\cdot)$
to denote the underlying probability measure of the process
$X_N(t)$
with starting state
$X_N(0)=x_0$
.
4.1. Initial phase
We first show that with high probability uniformly over all starting states, by the time
$\frac{1-h}{2J}\log(N)$
, the process
$X_N(t)$
will be within
$O(N^{\frac{1+h}{2}})$
of the fixed point
$x^{\star}N$
. This will be done by a simple application of Lemma 3.1, on account of Proposition 2.1.
To state the result, we first need to introduce some notation, which will be used frequently in what follows. Consider intervals of the form
\begin{equation} I(r)\,:\!=\,\big[x^{\star}-r, x^{\star}+r\big], \quad r>0.\end{equation}
We denote the first time that the scaled chain leaves an interval I by
\begin{equation} \tau^{X}_{\mathrm{exit}}(I)\,:\!=\,\inf\{t\geq 0\;:\; X_N(t)/N\notin I\}.\end{equation}
To prove the upper bound for the mixing time, we fix a
$h\in(0,1)$
and consider the following set to be the good set:
\begin{equation} \widehat{S}\equiv\widehat{S}(N)\,:\!=\,I\left(\eta\right), \quad \eta\equiv\eta(N)\,:\!=\,2(C_2+C_3)N^{-\frac{1-h}{2}},\end{equation}
where
$C_2$
was defined in Lemma 3.1 and
$C_3\,:\!=\,\big(\frac{J}{\lambda} \frac{x^{\star}}{\lvert x_1^{\star}\rvert}\big) \vee (1-x^{\star})$
. We also define the interior of the good set by
$\widetilde{S}\equiv\widetilde{S}(N)\,:\!=\,I\big(\frac{\eta}{2}\big)$
. Moreover, to simplify the notation, we write
$\tau^{X}_{\mathrm{exit}}$
for
$\tau^{X}_{\mathrm{exit}}(\widehat{S})$
, i.e. the first exit time of
$\widehat{S}$
.
Recall that
$\frac{1}{J}\lceil {\mathrm{e}}^{C_1N^{h}}\rceil$
from (3.2), where
$C_1$
was defined in Lemma 3.1. We prove the following lemma, where the first part serves as the initial phase and the second part controls the exit time of the interval I(r).
Lemma 4.3.
-
(i) For any
$h\in(0,1)$
and
$x_0\in\{0,\ldots, N\}$
, for N sufficiently large such that
\begin{equation*} \mathbb{P}_{x_0}\!\left(N^{-1}X_N\left(\frac{1-h}{2J}\log(N)\right)\in\widetilde{S}\right)\geq 1-4{\mathrm{e}}^{-C_1N^h} \end{equation*}
$\frac{1-h}{2J}\log(N)\leq t_{\mathrm{follow}}$
and as per Lemma 3.1.
-
(ii) For any
$h\in(0,1)$
, suppose that
$r=r(N)$
satisfies the condition (4.4)and
\begin{equation} \frac{r}{2C_2}N^{\frac{1-h}{2}}\geq 1 \quad {as\ } N\to\infty \end{equation}
$x_0/N\in I(\frac{r}{2})$
. Then we have In particular,
\begin{equation*} \mathbb{P}_{x_0}\big(\tau^{X}_{\mathrm{exit}}(I(r))> t_{\mathrm{follow}}\big)\geq 1-4{\mathrm{e}}^{-C_1N^h}. \end{equation*}
$r=\eta(N)$
satisfies (4.4), and so
$\mathbb{P}_{x_0}(\tau^{X}_{\mathrm{exit}}> t_{\mathrm{follow}})\geq 1-4{\mathrm{e}}^{-C_1N^h}$
for all
$x_0/N\in \widetilde{S}$
.
Proof. Recall the solution to the governing equation of the deterministic
$\varepsilon$
-SIS model given in (2.3). A simple calculation using Lemma 3.7 shows that
\begin{equation} \left\lvert x\left( \mbox{$\frac{1-h}{2J}$}\log(N)\right) - x^{\star}\right\rvert \leq C_3N^{-\frac{1-h}{2}}\end{equation}
uniformly for
$x(0)\in \{0,\ldots, N\}$
. It follows from a union bound and Lemma 3.1 that for large enough N such that
$\frac{1-h}{2J}\log(N)\leq t_{\mathrm{follow}}$
,
\begin{align*} & \mathbb{P}_{x_0}\!\left(\left\lvert X_N\left(\mbox{$\frac{1-h}{2J}$}\log(N)\right)-x^{\star}N\right\rvert > (C_2+C_3)N^{\frac{1+h}{2}}\right)\\ &\qquad\leq \mathbb{P}_{x_0}\!\left(\left\lvert X_N\left(\mbox{$\frac{1-h}{2J}$}\log(N)\right)-x\left(\mbox{$\frac{1-h}{2J}$}\log(N)\right)N\right\rvert > C_2N^{\frac{1+h}{2}} \right)\\ &\qquad\leq\mathbb{P}_{x_0}\!\left(\sup_{t\leq t_{\mathrm{follow}}}\left\lvert\frac{X_N(t)}{N}-x(t)\right\rvert>C_2N^{-\frac{1-h}{2}}\right)\leq4{\mathrm{e}}^{-C_1N^h},\end{align*}
which completes the proof of the first statement. For the second statement, note that given
$x(0) \in I(\frac{r}{2})$
, by the monotonicity of x(t) in t we have
$x(t)\in I(\frac{r}{2})$
for all
$t\geq 0$
. The condition (4.4) implies that
$I(\frac{r}{2}+C_2N^{-\frac{1-h}{2}}) \subset I(r)$
for sufficiently large N. Moreover, it follows from Lemma 3.1 that the probability that
$X_N(t)/N$
is within
$C_2N^{-\frac{1-h}{2}}$
of x(t) for all
$t\leq t_{\mathrm{follow}}$
is at least
$1-4{\mathrm{e}}^{-C_1N^h}$
. Together with the previous observation, this implies that the probability that
$X_N(t)/N \in I(\frac{r}{2}+C_2N^{-\frac{1-h}{2}}) \subset I(r)$
for all
$t\leq t_{\mathrm{follow}}$
is at least
$1-4{\mathrm{e}}^{-C_1N^h}$
.
The next corollary states the result of Lemma 4.3 in terms of the two coupled copies
$W_N(t)$
and
$Z_N(t)$
; that is, by the time
$\frac{1-h}{2J}\log(N)$
, both
$W_N(t)$
and
$Z_N(t)$
have entered the interior of the good set with high probability. Moreover, once they have reached the interior, they will remain in the good set for at least
$t_{\mathrm{follow}}$
time, which is exponential in N with high probability. Let
\begin{align} \tau_{\mathrm{exit}}\,:\!=\,\inf\big\{t\geq 0\;:\; W_N(t)/N \notin \widehat{S} \text{ or } Z_N(t)/N \notin \widehat{S} \big\}\end{align}
be the first time either copy leaves the good set. The corollary follows directly from Lemma 4.3 upon applying a union bound.
Corollary 4.1. For any
$h\in(0,1)$
, the following statements hold for N sufficiently large such that
$\frac{1-h}{2J}\log(N)\leq t_{\mathrm{follow}}$
and as per Lemma 3.1.
-
(i) For any
$w_0, z_0\in\{0,\ldots, N\}$
,
\begin{equation*} \mathbb{P}_{w_0,z_0}\!\left( N^{-1}W_N\!\left(\mbox{$\frac{1-h}{2J}$}\log(N)\right)\in\widetilde{S},\: N^{-1}Z_N\!\left(\mbox{$\frac{1-h}{2J}$}\log(N)\right)\in\widetilde{S}\right)\geq 1-8{\mathrm{e}}^{-C_1N^h}. \end{equation*}
-
(ii) Suppose that
$w_0/N\in\widetilde{S}$
and
$z_0/N \in\widetilde{S}$
; then we have
$\mathbb{P}_{w_0,z_0}(\tau_{\mathrm{exit}}> t_{\mathrm{follow}})\geq 1-8{\mathrm{e}}^{-C_1N^h}$
.
4.2. Intermediate phase
For this phase, we prove that after the burn-in period in the first phase, the distance between the two copies will drop to
$\sqrt{N}$
with high probability after another
$\frac{h}{2J}\log N$
time (plus a constant time). We do this by showing that the coupling is contracting if both
$W_N(t)/N$
and
$Z_N(t)/N$
are in the good set
$\widehat{S}$
, provided that N is large enough so that
$J/2\lambda>\eta(N)$
, where
$\eta$
is as defined in (4.3). To be precise, recall from (4.6) that
$\tau_{\mathrm{exit}}$
is the first time either copy exits the good set
$\widehat{S}$
. Also, let
$D_N(t)\,:\!=\,Z_N(t)-W_N(t)$
be the difference between the two copies of the chain at time t. The next lemma states that for any
$\xi > 0$
, given that
$D_N(0)=d_0$
is of order
$N^{\frac{1+h}{2}}$
, with high probability, on the event
$\{\tau_{\mathrm{exit}}>\frac{h}{2J}\log(N)+\frac{\xi}{2}\}$
,
$D_N(t)$
drops below
$\sqrt{N}$
by the time
$\frac{h}{2J}\log(N)+\frac{\xi}{2}$
.
For use in the proof, the jump rates of the coupling
$(W_N(t), Z_N(t))$
for
$t\leq \tau_{\mathrm{couple}}$
are given by
\begin{equation} \begin{aligned} &(w,z)\mapsto (w+1,z)&&\text{ at rate } \mathcal{I}_w,\\ &(w,z)\mapsto (w,z+1)&&\text{ at rate } \mathcal{I}_z,\\ &(w,z)\mapsto (w-1,z)&&\text{ at rate } \mathcal{C}_w,\\ &(w,z)\mapsto (w,z-1)&&\text{ at rate } \mathcal{C}_z, \end{aligned}\end{equation}
where
\begin{equation*} \mathcal{I}_x\equiv \mathcal{I}(x)\,:\!=\, \lambda x\left(1-\frac{x}{N}\right)+\varepsilon (N-x) \quad \text{and} \quad \mathcal{C}_x \equiv \mathcal{C}(x)\,:\!=\, \mu x, \quad x\in\{0, \ldots, N\}.\end{equation*}
Note that before colliding the two copies almost surely do not jump simultaneously, and thus they do not cross without colliding. Since the chains move together after colliding and we assume (without loss of generality) that
$W_N(0)\leq Z_N(0)$
, the coupling is monotonic, meaning that
$W_N(t)\leq Z_N(t)$
for all
$t\geq 0$
.
Lemma 4.4. For
$h\in(0,1)$
, let
$d_0\,:\!=\,z_0-w_0$
. Suppose
$w_0/N, z_0/N\in \widehat{S}$
so that
$d_0\leq 2\eta N=4(C_2+C_3)N^{\frac{1+h}{2}}$
. There exists a positive constant
$C_4$
depending only on
$\lambda$
,
$\mu$
, and
$\varepsilon$
such that the following relation holds for N sufficiently large and any
$\xi > 0$
:
\begin{equation}\mathbb{P}_{w_0,z_0}\!\left(D_{N}\!\left(\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}\right)\geq \sqrt{N}, \: \tau_{\mathrm{exit}}>\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}\right)\leq C_4{\mathrm{e}}^{-\mbox{$\frac{J}{2}$}\xi}.\end{equation}
Proof. Recall the possible transitions for this phase defined in (4.7). Since the coupling is monotonic,
$D_N(t)$
is non-negative for all
$t\geq0$
. Also,
$\tau_{\text{couple}}=\inf\{t\geq0:D_N(t)=0\}$
. Note that the process
$D_N(t)$
is not a Markov process by itself, but
$D_N(t)$
is uniquely determined by the two-dimensional process
$(W_N(t), Z_N(t))$
, which is Markov with respect to its natural filtration.
For each N, Proposition 2.1 in [Reference Kurtz22] implies that the process
\begin{equation} (W_N(t), Z_N(t))^{\top}-(W_N(0), Z_N(0))^{\top}-\int_0^t F\!\left((W_N(s), Z_N(s))^{\top}\right){\mathrm{d}} s, \quad t\geq 0,\end{equation}
is a zero-mean martingale, where
\begin{align*} F((w, z)^{\top})& \,:\!=\, \begin{cases} (0,1)^{\top} \mathcal{I}_z+ (1,0)^{\top}\mathcal{I}_w+ (0,-1)^{\top}\mathcal{C}_z + (-1,0)^{\top}\mathcal{C}_w, & w\not=z, \\ (1,1)^{\top} \mathcal{I}_w +(-1,-1)^{\top}\mathcal{C}_w, & w = z. \end{cases}\end{align*}
Taking expectations in (4.9) and subtracting the coordinates, we obtain
\begin{align*} \mathbb{E}_{w_0, z_0}D_N(t)=(z_0-w_0) &+ \mathbb{E}_{w_0, z_0} \int_0^t \big(\mathcal{I}(Z_N(s))-\mathcal{I}(W_N(s))\big) \,{\mathrm{d}} s\\ &- \mathbb{E}_{w_0, z_0} \int_0^t \big(\mathcal{C}(Z_N(s))-\mathcal{C}(W_N(s))\big) \,{\mathrm{d}} s.\end{align*}
Note that for all
$t\leq \tau_{\mathrm{exit}}$
, one has
$(x^{\star}-\eta)N\leq W_N(t)\leq Z_N(t)$
. Moreover, for any states
$w,z \in\widehat{S}$
we have
\begin{align*} \mathcal{I}_z-\mathcal{I}_w &=(\lambda-\varepsilon)(z-w)-\frac{\lambda}{N}(z-w)(z+w)\nonumber\\ &\leq (\lambda-\varepsilon)(z-w)-\frac{2\lambda}{N}(z-w)\left(x^{\star}-\eta\right)N\nonumber\\ &=\left(\mu-J+2\lambda\eta\right)(z-w).\end{align*}
Choose N large enough so that
$J/(2\lambda)\geq \eta(N)$
. Applying the optional stopping theorem to the Dynkin martingale for
$D_N(t)$
(which is a function of the two-dimensional Markov chain
$(W_N(t),Z_N(t))$
) and the bounded stopping time
$t \wedge \tau_{\mathrm{exit}}$
, as well as using Fubini’s theorem and the fact that
$D_N(t)$
is non-negative, we obtain
\begin{align*} \mathbb{E}_{w_0, z_0}\!\left(D_N(t)\unicode{x1D7D9}_{t< \tau_{\mathrm{exit}}}\right) &\leq \mathbb{E}_{w_0, z_0}D_N(t\wedge \tau_{\mathrm{exit}})\\ &\leq(z_0-w_0) - (J-2\lambda\eta) \mathbb{E}_{w_0, z_0} \!\left(\int_0^{t \wedge \tau_{\mathrm{exit}}} D_N(s) \,{\mathrm{d}} s\right)\\ &=(z_0-w_0) - (J-2\lambda\eta) \mathbb{E}_{w_0, z_0} \!\left(\int_0^{t} D_N(s)\unicode{x1D7D9}_{s<\tau_{\mathrm{exit}}} \,{\mathrm{d}} s\right)\\ &=(z_0-w_0) - (J-2\lambda\eta)\int_0^{t} \mathbb{E}_{w_0, z_0}\!\left(D_N(s)\unicode{x1D7D9}_{s<\tau_{\mathrm{exit}}} \right)\,{\mathrm{d}} s.\end{align*}
Letting
$d(t)\,:\!=\,\mathbb{E}_{w_0, z_0}(D_N(t)\unicode{x1D7D9}_{t< \tau_{\mathrm{exit}}})$
, we see that d(t) satisfies the integral inequality
\begin{equation*} d(t)\leq d_0 - (J-2\lambda\eta) \int_0^t d(s) \,{\mathrm{d}} s.\end{equation*}
Then, for all N large enough so that
$J/(2\lambda) \geq \eta(N)$
, by adapting Bellman’s proof of Grönwall’s inequality (see [Reference Ames and Pachpatte3, Theorem 1.2.2]) to this setting, we obtain that for all
$t\geq0$
,
\begin{equation*} d(t)\leq d_0{\mathrm{e}}^{-(J-2\lambda\eta)t}.\end{equation*}
Since we have assumed that
$d_0\leq 4(C_2+C_3)N^{\frac{1+h}{2}}$
, we have
\begin{align*} \mathbb{E}_{w_0, z_0}\!\left(D_N\!\left(\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}\right) \unicode{x1D7D9}_{\tau_{\mathrm{exit}}>\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}}\right)&\leq d_0{\mathrm{e}}^{-(J-2\lambda\eta) \big(\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}\big)}\\ &\leq 4(C_2+C_3)N^{\frac{1}{2}}N^{\frac{\lambda h \eta}{J}}{\mathrm{e}}^{-\mbox{$\frac{J-2\lambda\eta}{2}$}\xi}.\end{align*}
Now, using the fact that
$\unicode{x1D7D9}_{D_{N}\left(t\right)\geq \sqrt{N}}\leq D_{N}(t)/\sqrt{N}$
and the above inequality, we have
\begin{align*} &\mathbb{P}_{w_0,z_0}\!\left(D_{N}\left(\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}\right)\geq \sqrt{N}, \: \tau_{\mathrm{exit}}>\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}\right) \\ &\quad\leq N^{-1/2} \mathbb{E}_{w_0, z_0}\!\left(D_N\left(\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}\right) \unicode{x1D7D9}_{\tau_{\mathrm{exit}}>\mbox{$\frac{h}{2J}$}\log(N)+\mbox{$\frac{\xi}{2}$}}\right)\\ &\quad\leq 4(C_2+C_3)N^{\frac{\lambda h \eta}{J}}{\mathrm{e}}^{-\mbox{$\frac{J-2\lambda\eta}{2}$}\xi}.\end{align*}
The proof is complete after noting that
$\lim_{N\to\infty} N^{\frac{\lambda h}{J}\eta}=1$
, using that
$\eta(N)=O(N^{-\frac{1-h}{2}})$
.
4.3. Final phase
We now show that once the two copies are within distance
$\sqrt{N}$
of each other, the additional time to coalescence is at most
$\xi/2>0$
(which is an absolute constant), with high probability, on the event that the copies stay in the good set
$\widehat{S}$
for a time that is at least
$\xi/2$
.
Lemma 4.5. Let
$\tau_0\,:\!=\,\inf\{t\geq0\;:\; D_N(t)=0\}$
. Suppose that
$w_0/N, z_0/N\in\widehat{S}$
and
$d_0=z_0-w_0 \le\sqrt{N}$
. Then for all N sufficiently large such that
$J/(2\lambda) \ge \eta(N)$
, the following relation holds for all
$\xi>0$
:
\begin{equation*} \mathbb{P}_{w_0, z_0}\big(\tau_0 > \mbox{$\frac{\xi}{2}$},\tau_{\mathrm{exit}}>\mbox{$\frac{\xi}{2}$}\big)\leq\frac{4}{\sqrt{\mu\wedge\varepsilon}}\,\xi^{-\frac{1}{2}}.\end{equation*}
To prove this lemma, we require Proposition 4.1 of [Reference Barbour, Brightwell and Luczak6] (stated below as Proposition 4.1), which is a continuous-time analogue of Proposition 17.19 in [Reference Levin and Peres23] and controls the tails of certain hitting times. With the right setup, the proof of Lemma 4.5 is a straightforward application of the lemma.
Proposition 4.1. ([Reference Barbour, Brightwell and Luczak6, Proposition 4.1].) Let X(t) be a continuous-time Markov jump chain with state space S and rate matrix Q that is stable, conservative, and non-explosive. Let B and
$\sigma^2$
be positive, and let
$f\;:\; S \to \mathbb{R}_+$
be a function. Set
$S_0 \,:\!=\, \{x\in S \;:\; f (x) = 0\}$
, and assume the following conditions:
-
(i) the drift
$\sum_y Q(x, y)(f(y)-f(x))$
of f is non-positive for all
$x \in S \backslash S_0$
; -
(ii) f(X) makes jumps of magnitude at most B;
-
(iii)
$\sum_y Q(x, y)(f(y)-f(x))^2\geq \sigma^2$
for all
$x \in S \backslash S_0$
.
Define
$T_{*}\,:\!=\,\inf\{t:f(X(t))=0\}$
, the hitting time of
$S_0$
. Then for any
$t_0\geq 2B^2/\sigma^2$
,
\begin{equation*} \mathbb{P}(T_{*}\geq t_0)\leq \frac{2\sqrt{2}f(X_0)}{\sigma\sqrt{t_0}}.\end{equation*}
The drift condition of the proposition does not hold globally for
$X_N$
, but it does hold in the good set
$\widehat{S}$
. Since we are only interested in the behaviour of the chain before it leaves the good set, conceptually the lemma still applies. To apply it directly, we introduce a modified version of the chain that reflects at the ‘boundary’ of the good set. Let
$\ell\,:\!=\,\{\lceil (x^{\star}-\eta)N \rceil-1\}$
and
$u\,:\!=\,\{\lfloor (x^{\star}+\eta)N \rfloor+1\}$
be the states corresponding to leaving the good set
$\widehat S$
. Define a state space
$S\,:\!=\,N\widehat{S}\cup u \cup\ell$
. Let
$\overline{X}_N(t)$
be a Markov chain on S, which evolves as follows. If
$\overline{X}_N(t)/N\in\widehat{S}$
, then it makes jumps according to the transition rates of the original process
$X_N(t)$
; otherwise,
\begin{align} & u \to u-1 \quad\text{ at rate } \mathcal{C}_{u}, \qquad \ell \to \ell-1 \quad \text{ at rate } 0,\\ & u \to u+1 \quad \text{ at rate } 0,\qquad \ \ \ell \to \ell+1 \quad\text{ at rate } \mathcal{I}_{\ell}.\nonumber\end{align}
The processes
$X_N(t)$
and
$\overline{X}_N(t)$
admit a natural coupling, under which the two processes start from the same initial state
$x_0/N\in\widehat{S}$
and evolve together until time
$\tau^{X}_{\mathrm{exit}}=\inf\{t\geq 0\;:\; X_N(t)/N\notin\widehat{S}\}$
defined in (4.2). This leads to the following immediate observation: for any event A in the stopped sigma-algebra of
$\tau_{\mathrm{exit}}^X$
, one has
$\mathbb{P}(A)=\overline{\mathbb{P}}(A)$
, where we use
$\mathbb{P}$
to denote the underlying probability measure of
$X_N(t)$
and
$\overline{\mathbb{P}}$
the underlying probability measure of
$\overline{X}_N(t)$
. That is, the two processes
$X_N(t)$
and
$\overline{X}_N(t)$
are pathwise indistinguishable in probability up to time
$\tau^{X}_{\mathrm{exit}}$
.
As before, let
$(W_N(t), Z_N(t))$
be two independent copies of
$X_N(t)$
with transitions specified by (4.7) before coalescence and moving together after coalescence. Also, let
$(\overline{W}_N(t), \overline{Z}_N(t))$
evolve as two independent copies of
$\overline{X}_N(t)$
with
$\overline{W}_N(0)\leq\overline{Z}_N(0)$
until coalescence and moving together after coalescence. Analogously to the relationship between
$X_N(t)$
and
$\overline{X}_N(t)$
, the two-dimensional processes
$(W_N(t), Z_N(t))$
and
$(\overline{W}_N(t), \overline{Z}_N(t))$
are pathwise indistinguishable in probability up to the first time that
$(W_N(t), Z_N(t))$
exits
$N\widehat{S}\times N\widehat{S}$
, that is, until the time
$\tau_{\mathrm{exit}}$
defined in (4.6).
Proof of Lemma 4.5. Set
\begin{align*} \tau^{\overline{W}, \overline{Z}}_{0}&\,:\!=\,\inf\{t\geq 0\;:\; \overline{Z}_N(t)-\overline{W}_N(t)=0\}, \\ \tau^{\overline{W}, \overline{Z}}_{\mathrm{exit}}&\,:\!=\,\inf\{t\geq 0\;:\; \overline{W}_N(t)=\ell \text{ or } \overline{Z}_N(t)=u\},\end{align*}
and write
$\mathbb{P}$
for the underlying probability measure of
$(W_N(t), Z_N(t))$
and
$\overline{\mathbb{P}}$
for the underlying probability measure of
$(\overline{W}_N(t), \overline{Z}_N(t))$
. Since
$\overline{W}_N(t)\leq \overline{Z}_N(t)$
for all
$t\geq0$
, the process
$(\overline{W}_N(t), \overline{Z}_N(t))$
leaves
$N\widehat{S}\times N\widehat{S}$
either by having the lower one jump down or by having the upper one jump up. Then, as in the previous discussion of the relationship between
$X_N(t)$
and
$\overline{X}_N(t)$
, we have the following two immediate observations:
\begin{align} \mathbb{P}_{w_0, z_0}\big(\tau_{\mathrm{exit}}\leq \mbox{$\frac{\xi}{2}$}\big) &=\overline{\mathbb{P}}_{w_0, z_0}\big(\tau^{\overline{W}, \overline{Z}}_{\mathrm{exit}}\leq \mbox{$\frac{\xi}{2}$}\big);. \end{align}
\begin{align} \mathbb{P}_{w_0, z_0}\big(\tau_0\leq\mbox{$\frac{\xi}{2}$},\,\tau_{\mathrm{exit}}> \mbox{$\frac{\xi}{2}$}\big) &=\overline{\mathbb{P}}_{w_0, z_0}\big(\tau^{\overline{W}, \overline{Z}}_{0}\leq\mbox{$\frac{\xi}{2}$},\, \tau^{\overline{W}, \overline{Z}}_{\mathrm{exit}}> \mbox{$\frac{\xi}{2}$}\big). \end{align}
Therefore, it suffices to prove the result for the process
$(\overline{W}_N(t), \overline{Z}_N(t))$
. To apply Proposition 4.1 of [Reference Barbour, Brightwell and Luczak6] (i.e. Proposition 4.1) to
$(\overline{W}_N(t), \overline{Z}_N(t))$
, first set
\begin{equation*} f((w,z))=(z-w)\unicode{x1D7D9}_{w\leq z}.\end{equation*}
Clearly, f is non-negative and integer-valued, so
$f(\textbf{x})\geq 1$
for all
$\textbf{x}=(w,z)$
such that
$f(\textbf{x})\neq 0$
. Also, condition (ii) of Proposition 4.1 is satisfied by taking
$B=1$
.
We now verify condition (i) of Proposition 4.1, i.e. that the drift,
$\sum_{\textbf{y}} Q(\textbf{x}, \textbf{y})(f(\textbf{y})-f(\textbf{x}))$
, is non-positive for all
$\textbf{x}$
such that
$f(\textbf{x})\neq 0$
. First note that, in our case, there are four terms in the sum, since before coalescence the coupled process
$(\overline{W}_N(t), \overline{Z}_N(t))$
has four possible ways of jumping. The movements
\begin{align*} &\textbf{x}=(\bar{w},\bar{z})\mapsto \textbf{y}=(\bar{w}+1,\bar{z})\quad\text{ with } Q(\textbf{x}, \textbf{y})=\mathcal{I}_{\bar{w}},\\ &\textbf{x}=(\bar{w},\bar{z})\mapsto \textbf{y}=(\bar{w},\bar{z}-1)\quad\text{ with } Q(\textbf{x}, \textbf{y})=\mathcal{C}_{\bar{z}}\end{align*}
are always allowed and lead to
$f(\textbf{y}) - f(\textbf{x}) = -1$
. The other two possible jumps,
\begin{align*} &\textbf{x}=(\bar{w},\bar{z})\mapsto \textbf{y}=(\bar{w},\bar{z}+1)\quad\text{ with } Q(\textbf{x}, \textbf{y})=\mathcal{I}_{\bar{z}}\cdot\unicode{x1D7D9}\{\bar{z}\neq u\},\\ &\textbf{x}=(\bar{w},\bar{z})\mapsto \textbf{y}=(\bar{w}-1,\bar{z})\quad\text{ with } Q(\textbf{x}, \textbf{y})=\mathcal{C}_{\bar{w}}\cdot\unicode{x1D7D9}\{\bar{w}\neq \ell\},\end{align*}
always lead to
$f(\textbf{y}) - f(\textbf{x}) = 1$
, and the boundary conditions are reflected by the indicators in the transition rates. Also, note that for all
$x\in S$
,
\begin{equation*} \lvert x/N-x^{\star} \rvert \leq \eta+N^{-1}=O(N^{-\frac{1-h}{2}}). \end{equation*}
with
$\eta\equiv\eta(N)$
defined in (4.3). It then follows that
\begin{align} \smash{\sum_{\textbf{y}}} Q(\textbf{x}, \textbf{y})(f(\textbf{y})-f(\textbf{x})) &= (\mathcal{I}_{\bar{z}}\cdot\unicode{x1D7D9}\{\bar{z}\neq u\}+\mathcal{C}_{\bar{w}}\cdot\unicode{x1D7D9}\{\bar{w}\neq \ell\})-(\mathcal{I}_{\bar{w}}+\mathcal{C}_{\bar{z}})\nonumber\\ &\leq(\mathcal{I}_{\bar{z}}-\mathcal{I}_{\bar{w}})-(\mathcal{C}_{\bar{z}}-\mathcal{C}_{\bar{w}})\nonumber\\ & =(\lambda-\mu-\varepsilon) (\bar z-\bar w) - \mbox{$\frac{\lambda}{N}$}(\bar z-\bar w)(\bar z+\bar w)\nonumber\\ &\leq \left((\lambda-\mu-\varepsilon) - 2\lambda\left(x^{\star}-\eta-N^{-1}\right)\right)(\bar z-\bar w) \nonumber\\ & = -(J-2\lambda\eta-2\lambda N^{-1})\lvert \bar z- \bar w\rvert,\end{align}
which is clearly negative when N is sufficiently large, for
$\bar z\not= \bar w$
. To obtain the
$\sigma^2$
satisfying condition (iii), note that
\begin{align*} \sum_{\textbf{y}} Q(\textbf{x}, \textbf{y})(f(\textbf{y})-f(\textbf{x}))^2 &= \mathcal{I}_{\bar{w}} + \mathcal{I}_{\bar{z}}\cdot\unicode{x1D7D9}\{\bar{z}\neq u\} + \mathcal{C}_{\bar{z}} + \mathcal{C}_{\bar{w}}\cdot\unicode{x1D7D9}\{\bar{w}\neq \ell\}\\ &\geq \mathcal{I}_{\bar{w}} + \mathcal{C}_{\bar{z}} \geq \mathcal{I}_{\bar{w}} + \mathcal{C}_{\bar{w}} \geq(\mu \wedge \varepsilon)N \,:\!=\, \sigma^2,\end{align*}
since the minimum of
\begin{equation*} g(x)\,:\!=\,\mathcal{I}_{x}+\mathcal{C}_{x}=-\frac{\lambda}{N} x^2+(\lambda+\mu-\varepsilon)x+\varepsilon N\end{equation*}
is achieved at either
$g(0)=\varepsilon N$
or
$g(N)=\mu N$
. An application of Proposition 4.1 gives
\begin{equation} \overline{\mathbb{P}}_{w_0,z_0}\big(\tau^{\overline{W}, \overline{Z}}_{0}\wedge \tau^{\overline{W}, \overline{Z}}_{\mathrm{exit}}>\mbox{$\frac{\xi}{2}$}\big)\leq \overline{\mathbb{P}}_{w_0,z_0}\big(\tau^{\overline{W}, \overline{Z}}_{0}>\mbox{$\frac{\xi}{2}$}\big)\leq \frac{2\sqrt{2}d_0}{\sqrt{(\mu \wedge \varepsilon)N}\sqrt{\xi/2}}\leq \frac{4}{\sqrt{\mu \wedge \varepsilon}}\,\xi^{-\frac{1}{2}}.\end{equation}
Then, in view of observations (4.11) and (4.12), we conclude that
\begin{align*} \mathbb{P}_{w_0, z_0}\big(\tau_0\leq\xi/2,\tau_{\mathrm{exit}}>\xi/2\big)&=\overline{\mathbb{P}}_{w_0, z_0}\big(\tau^{\overline{W}, \overline{Z}}_{0}\leq\xi/2,\, \tau^{\overline{W}, \overline{Z}}_{\mathrm{exit}}>\xi/2\big)\\ &= \overline{\mathbb{P}}_{w_0,z_0}\big(\tau^{\overline{W}, \overline{Z}}_{\mathrm{exit}}>\xi/2\big)-\overline{\mathbb{P}}_{w_0,z_0}\big(\tau^{\overline{W}, \overline{Z}}_{0}\wedge \tau^{\overline{W}, \overline{Z}}_{\mathrm{exit}}>\xi/2\big)\\ &\geq\mathbb{P}_{w_0,z_0}\big(\tau_{\mathrm{exit}}>\xi/2\big)-\frac{4}{\sqrt{\mu \wedge \varepsilon}}\xi^{-\frac{1}{2}},\end{align*}
and hence
\begin{align*} \mathbb{P}_{w_0, z_0}\big(\tau_0>\xi/2,\tau_{\mathrm{exit}}>\xi/2\big)&=\mathbb{P}_{w_0,z_0}\big(\tau_{\mathrm{exit}}>\xi/2\big)-\mathbb{P}_{w_0, z_0}\big(\tau_0\leq\xi/2,\tau_{\mathrm{exit}}>\xi/2\big)\\ &\leq\frac{4}{\sqrt{\mu \wedge \varepsilon}}\,\xi^{-\frac{1}{2}},\end{align*}
as desired.
4.4. Bounding the time to coalescence
We combine the previous results from this section for a proof of Lemma 4.2.
Proof of Lemma
4.2. Fix
$\xi>0$
. Let the good event that the coupled processes
$W_N(t)$
and
$Z_N(t)$
are in the interior good set
$\widetilde S$
by time
$\frac{1-h}{2J}\log(N)$
be denoted by
\[B_N\,:\!=\,\left\{N^{-1} W_N\!\left(\mbox{$\frac{1-h}{2J}$}\log(N)\right)\in\widetilde{S}, \: N^{-1}Z_N\!\left(\mbox{$\frac{1-h}{2J}$}\log(N)\right)\in\widetilde{S}\right\}. \]
Then the first part of Corollary 4.1 implies
\begin{equation}\begin{split}&\mathbb{P}_{w_0,z_0}\!\left(\tau_{\mathrm{couple}}>\mbox{$\frac{1-h}{2J}$}\log(N)+\mbox{$\frac{h}{2J}$}\log(N)+\xi\right) \\ &\quad\leq \mathbb{P}_{w_0,z_0}\!\left(\tau_{\mathrm{couple}}>\mbox{$\frac{1-h}{2J}$}\log(N)+\mbox{$\frac{h}{2J}$}\log(N)+\xi, B_N \right) + 8{\mathrm{e}}^{-C_1N^h}. \end{split}\end{equation}
By the Markov property, to bound the first term on the right-hand side of (4.15), it is enough to bound, uniformly in
$w_0/N, z_0/N\in\widetilde{S}\subset\widehat{S}$
,
\begin{align*}&\mathbb{P}_{w_0,z_0}\!\left(\tau_{\mathrm{couple}}>\mbox{$\frac{h}{2J}$}\log(N)+\xi\right) \\ &\quad\leq \mathbb{P}_{w_0,z_0}\!\left(\tau_{\mathrm{couple}}>\mbox{$\frac{h}{2J}$}\log(N)+\xi, \tau_{\mathrm{exit}}>t_{\mathrm{follow}} \right)+ 8{\mathrm{e}}^{-C_1N^h} \\ &\quad\leq \mathbb{P}_{w_0,z_0}\!\left(\tau_{\mathrm{couple}}>\mbox{$\frac{h}{2J}$}\log(N)+\xi, \tau_{\mathrm{exit}}>\mbox{$\frac{h}{2J}$}\log(N)+\xi \right)+ 8{\mathrm{e}}^{-C_1N^h}\end{align*}
where the first inequality follows from the second part of Corollary 4.1, and for the second inequality we assume N to be sufficiently large so that h2J
$\log(N)+\xi\leq t_{\mathrm{follow}}$
.
Lemmas 4.4 and 4.5, combined with a straightforward application of the Markov property, imply that for all N large enough,
\begin{equation*}\mathbb{P}_{w_0,z_0}\!\left(\tau_{\mathrm{couple}}>\mbox{$\frac{h}{2J}$}\log(N)+\xi,\: \tau_{\mathrm{exit}}>\mbox{$\frac{h}{2J}$}\log(N)+\xi\right)\leq \frac{4}{\sqrt{\mu \wedge \varepsilon}}\,\xi^{-\frac{1}{2}}+C_4{\mathrm{e}}^{-\mbox{$\frac{J}{2}$}\xi}.\end{equation*}
Combining the inequalities above gives
\begin{equation*}\mathbb{P}_{w_0,z_0}\!\left(\tau_{\mathrm{couple}}>\mbox{$\frac{1-h}{2J}$}\log(N)+\mbox{$\frac{h}{2J}$}\log(N)+\xi\right)\leq \frac{4}{\sqrt{\mu \wedge \varepsilon}}\,\xi^{-\frac{1}{2}}+C_4{\mathrm{e}}^{-\mbox{$\frac{J}{2}$}\xi}+16{\mathrm{e}}^{-C_1N^{h}},\end{equation*}
and taking the limit superior as
$N \to \infty$
on both sides finishes the proof.
5. Proof of the lower bound for the mixing time
In this section, we prove the following lower bound on the mixing time, which together with Lemma 4.1 proves Theorem 1.1. Recall
$\rho_N(t)=\max_{x\in\{0,1,\ldots,N\}}\lVert P^t_N(x,\cdot)-\pi_N \rVert_{\rm TV}$
and
$t_N=\frac{1}{2J}\log(N)$
from Definition 1.1 and Theorem 1.1.
Lemma 5.1. For sufficiently large
$\xi\geq0$
,
\begin{equation*} \liminf_{N\to\infty}\rho_N(t_N-\xi)\geq 1-\psi_2(\xi),\end{equation*}
where
$\psi_2(\cdot)$
is a non-negative real-valued function depending only on
$\lambda$
,
$\mu$
, and
$\varepsilon$
with
$\psi_2(\xi)=O(1/\sqrt{\xi})$
as
$\xi\to\infty$
.
Before outlining the strategy of the proof, we first state an improved version of the concentration-of-measure inequality from Lemma 3.1 for the scaled process
$X_N(t)/N$
, which holds only if the starting state of the chain
$X_N(t)$
is close enough to
$x^{\star}N$
. Recall the interval of the form
$I(r)=[x^{\star}-r, x^{\star}+r]$
defined in (4.1). In the previous section, we took
$r=\eta(N)$
in defining our good set
$\widehat{S}$
, so that the size of the good set shrinks as N gets large. To prove the lower bound, we consider
$r < J/(6\lambda)$
as a positive constant, i.e. independent of N.
Lemma 5.2. Fix
$h\in(0,1)$
,
$r < J/(6\lambda)$
, and
$\xi>0$
. Let
$x_0/N\in I(\frac{r}{2})$
and let
$t\leq t_{\mathrm{follow}}=$
1J
$\lceil {\mathrm{e}}^{C_1N^{h}}\rceil$
. Then the following holds for all N large enough (depending on h,
$\xi$
,
$\lambda$
,
$\mu$
, and
$\varepsilon$
):
\begin{equation*} \mathbb{P}_{x_0}\!\left(\left\lvert X_N(t)-\mathbb{E}_{x_0}(X_N(t))\right\rvert \geq 2\xi\sqrt{N}\right)\leq 3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}}.\end{equation*}
The lemma essentially follows from an application of Theorem 3.3 from [Reference Barbour, Brightwell and Luczak6], but the details are technical, so we postpone the proof until the end of this section. Assuming that Lemma 5.2 holds, the proof of Lemma 5.1 is then broken down into two steps.
The first step is taken in Lemma 5.3, where we show that the stationary distribution
$\pi_N$
is with high probability concentrated in a ball of order
$\sqrt{N}$
around the fixed point
$x^{\star} N$
. The explicit expression for the stationary distribution can be obtained by solving the detailed balance equation (see e.g. (A1) and (A2) in [Reference Van Mieghem30]), but it is not easy to observe the concentration from this expression. The outline of our strategy is to first fix
$\xi>0$
and choose N large enough such that
$t_N+\xi < t_{\mathrm{follow}}$
. We use the improved concentration inequality of Lemma 5.2 to show that the distribution of
$X_N(t_N+\xi)$
is concentrated in a
$2\xi\sqrt{N}$
-ball around
$\mathbb{E}_{x_0}(X_N(t_N+\xi))$
given
$x_0/N\in I(\frac{r}{2})$
. Next, the first part of Lemma 3.2 implies that
$\mathbb{E}_{x_0}(X_N(t_N+\xi))$
is within
${\mathrm{e}}^{-J\xi}K_1\sqrt{N}$
of
$x^{\star}N$
. Together these imply that
$X_N(t_N+\xi)$
is in a
$({\mathrm{e}}^{-J\xi}K_1+2\xi)\sqrt{N}$
-ball around
$x^{\star}N$
with high probability. Finally, since the distribution of
$X_N$
is close to stationary by the time
$t_N+\xi$
, as stated in Lemma 4.1, this implies that
$\pi_N$
also assigns most of the mass to a
$({\mathrm{e}}^{-J\xi}K_1+2\xi)\sqrt{N}$
-ball around
$x^{\star}N$
.
To prove the lower bound, it is sufficient to consider only one specific initial state. For convenience, we take the initial state to be
$\bar{x}\,:\!=\,\lfloor (x^{\star}+\frac{r}{2})N \rfloor$
. The second step of the proof of Lemma 5.1 is then to show that the distribution of
$X_N(t_N-\xi)$
given
$X_N(0)=\bar{x}$
is concentrated in a region that is sufficiently apart from
$x^{\star}N$
; combined with the concentration of
$\pi_N$
around
$x^{\star}N$
, this gives a lower bound on the mixing time. The outline of the proof of this result is as follows. First fix a
$\xi$
large enough such that
${\mathrm{e}}^{J\xi}K_2-2\xi>{\mathrm{e}}^{-J\xi}K_1+2\xi$
, where
$K_1$
and
$K_2$
are as in Lemma 3.2. By the improved concentration inequality, the distribution of
$X_{N}(t_N-\xi)$
is concentrated in a
$2\xi\sqrt{N}$
-ball around
$\mathbb{E}_{\bar{x}}(X_{N}(t_N-\xi))$
. The second part of Lemma 3.2 then implies that
$\mathbb{E}_{\bar{x}}(X_{N}(t_N-\xi))$
is at least
${\mathrm{e}}^{J\xi}K_2\sqrt{N}$
above the fixed point
$x^{\star}N$
. Together, these two results indicate that with high probability,
\[ X_{\bar{x}}(t_N-\xi)- x^{\star}N \geq ({\mathrm{e}}^{J\xi}K_2-2\xi)\sqrt{N}>({\mathrm{e}}^{-J\xi}K_1+2\xi)\sqrt{N},\]
but by Lemma 5.3 we know that
$\pi_N$
assigns most of its mass within
$({\mathrm{e}}^{-J\xi}K_1+2\xi)\sqrt{N}$
of
$x^{\star}N$
.
Now, with the outline in mind, we state and prove concentration for the stationary distribution
$\pi_N$
.
Lemma 5.3. For any
$\xi>0$
, define the set
\begin{equation*} \mathcal{S}_N\,:\!=\,\left\{x\in\{0,1,\ldots,N\}\;:\;\left\lvert x-x^{\star}N\right\rvert \leq ({\mathrm{e}}^{-J\xi}K_1+2\xi)\sqrt{N}\right\},\end{equation*}
where
$K_1$
is the constant defined in Lemma 3.2. Then one has
\begin{equation*} \limsup_{N\to\infty}\pi_N(\mathcal{S}_N^c)\leq \psi_1(\xi)+3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}},\end{equation*}
where
$\psi_1(\xi)=O(1/\sqrt{\xi})$
is as defined in Lemma 4.1.
Proof. Let
$x_0/N\in I(\frac{r}{2})$
,
$h\in(0,1)$
, and
$\xi>0$
. Lemma 5.2 implies that as long as N is sufficiently large,
\begin{align*} \mathbb{P}_{x_0}\!\left(\left\lvert X_N\left(t_N+\xi \right)-\mathbb{E}_{x_0}\left(X_N(t_N+\xi)\right)\right\rvert\leq 2\xi\sqrt{N}\right)\geq1-3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}}.\end{align*}
Moreover, applying the first part of Lemma 3.2 with
$c=\xi$
gives
\begin{equation*} \big\lvert \mathbb{E}_{x_0}(X_N(t_N+\xi))-x^{\star}N \big\rvert \leq {\mathrm{e}}^{-J\xi}K_1\sqrt{N}\end{equation*}
for N large enough. It then follows that for N large enough,
\begin{align*} &\mathbb{P}_{x_0}\!\left(\left\lvert X_N(t_N+\xi)-x^{\star}N\right\rvert \leq (2\xi+{\mathrm{e}}^{-J\xi}K_1)\sqrt{N}\right) \\ &\quad\geq \mathbb{P}\!\left(\left\lvert X_N(t_N+\xi)-\mathbb{E}_{x_0}\left(X_N(t_N+\xi)\right)\, N\right\rvert \leq 2\xi\sqrt{N}\right)\\ &\quad\geq 1-3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}}.\end{align*}
Thus, for any
$\xi>0$
and N large enough, the inequality implies that
\begin{align*} \pi_N(\mathcal{S}_N^c)& \leq P_N^{t_N+\xi}(x_0,\,\mathcal{S}_N^c)+\rho_N(t_N+\xi) \\ &\leq 3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}} + \rho_N(t_N+\xi),\end{align*}
where
$P_N^{t}(x_0,\,\cdot\,)$
is the law of
$X_N(t)$
given the initial state
$x_0$
. The result now follows by taking the limsup and applying Lemma 4.1.
We can now prove our lower bound on the mixing time.
Proof of Lemma
5.1. Fix a large enough
$\xi>0$
such that
${\mathrm{e}}^{J\xi}K_2-2\xi>{\mathrm{e}}^{-J\xi}K_1+2\xi$
and let
$\bar{x}=\lfloor (x^{\star}+\frac{r}{2})N \rfloor$
. It follows from the second part of Lemma 3.2 by taking
$c=-\xi$
that
\begin{equation*} \mathbb{E}_{\bar{x}}\big(X_N(t_N-\xi)\big)-x^{\star}N \geq {\mathrm{e}}^{J\xi}K_2\sqrt{N}\end{equation*}
for all N large enough. Moreover, note that
$\bar{x}/N\in I(\frac{r}{2})$
, and so for any N such that
$t_N-\xi\leq t_{\mathrm{follow}}$
, Lemma 5.2 implies that
\begin{align*} \mathbb{P}_{\bar{x}}\!\left(\left\lvert X_N(t_N-\xi)- \mathbb{E}_{\bar{x}}\left(X_N(t_N-\xi)\right)\right\rvert \leq 2\xi\sqrt{N}\right)\geq1-3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}}\end{align*}
for all N large enough. Combining the previous two relations gives
\begin{equation} P_N^{t_N-\xi}(\bar{x}, \mathcal{S}_N)\leq3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}},\end{equation}
where
$\mathcal{S}_N$
is the set defined in Lemma 5.3. Now,
\begin{align*} \rho_N(t_N-\xi) &\geq \lVert P_N^{t_N-\xi}(\bar{x}, \cdot)-\pi_N \rVert_{\rm TV} \geq \big\lvert \pi_N(\mathcal{S}_N)-P_N^{t_n-\xi}(\bar{x}, \mathcal{S}_N)\big\rvert\,,\end{align*}
so (5.1) and Lemma 5.3 imply that for all sufficiently large
$\xi$
,
\begin{equation*} \liminf_{N\to\infty} \rho_N(t_N-\xi)\geq 1-\psi_1(\xi)-6{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}}.\end{equation*}
At this point it only remains to prove Lemma 5.2. To do this, we make use of Theorem 3.3 of [Reference Barbour, Brightwell and Luczak6], which provides a concentration inequality for contracting Markov chains.
Theorem 5.1. ([Reference Barbour, Brightwell and Luczak6, Theorem 3.3].) Let X(t) be a stable, conservative, and non-explosive continuous-time Markov chain on a discrete state space E, with generator matrix
$Q\,:\!=\,(Q(x,y)\;:\; x,y\in E)$
. Suppose that
$d(\cdot\,,\cdot)$
is a metric on E, and let
$f \;:\; E \to \mathbb{R}$
be a function such that for some constant L,
$\lvert f(x)-f(y)\rvert \leq Ld(x, y)$
for all
$x, y \in E$
. Let
$\widehat{E}$
be a subset of E, and let q and D be constants such that
$-Q(x, x) \leq q$
for all
$x \in \widehat{E}$
and
$d(x,y) \leq D$
whenever
$x \in \widehat{E}$
and y is such that
$Q(x, y) > 0$
. For
$t > 0$
, let
$A_t = \{X(s) \in \widehat{E} \text{ for } 0 \leq s < t\}$
. Suppose that there is a Markovian coupling of two copies of X(t), with generator
$\mathcal{A}$
and constant
$\ell>0$
, such that for all
$x, y\in E$
,
\begin{equation} \mathcal{A}d(x,y)\leq -\ell d(x,y). \end{equation}
Then for all
$x \in \widehat{E}$
,
$t > 0$
, and
$\xi\geq0$
,
\begin{equation*} \mathbb{P}_x\Big(\big\{\big\lvert f(X(t))-\mathbb{E}_x(f(X(t)))\big\rvert \geq \xi \big\}\cap A_t\Big)\leq 2\exp\!\left(-\frac{\xi^2}{qL^2D^2/\ell+2LD\xi/3}\right). \end{equation*}
We are not able to apply this theorem directly to our chain
$X_N(t)$
, since it is not contracting on the entire state space. One could modify the theorem to get a version that requires the contraction property to hold only on a ‘good’ subset of the state space, as is the case for
$X_N(t)$
near
$x^{\star}N$
. (Indeed, Theorem 2.3 of [Reference Barbour, Brightwell and Luczak6] is stated in such a form, but for discrete time.) Instead, we avoid this issue by making use of the reflected chain
$\overline{X}_N(t)$
defined for the final phase immediately after Proposition 4.1, which behaves as
$X_N(t)$
in a good set and reflects at the boundary. Here, with a slight abuse of notation, we define
$\overline{X}_N(t)$
to be the reflected chain on the state space
$E\,:\!=\,NI(r)\cup \{\lfloor (x^{\star}+r)N \rfloor + 1\} \cup \{\lceil (x^{\star}-r)N \rceil - 1\}$
, where
$\{\lfloor (x^{\star}+r)N \rfloor + 1\}$
and
$\{\lceil (x^{\star}-r)N \rceil - 1\}$
are considered to be the upper and lower boundaries, respectively, and
$r < J/(6\lambda)$
is a fixed positive constant.
Proof of Lemma
5.2. Recall the definition of
$\tau^{X}_{\mathrm{exit}}(I(r))$
from (4.2). Just as we argued in the passage following (4.10), it is sufficient to prove the concentration for
$\overline{X}_N(t)$
on
$A_t=\{\tau^{\overline{X}}_{\mathrm{exit}}(I(r))\geq t\}$
, where
$\tau^{\overline{X}}_{\mathrm{exit}}(I(r))\,:\!=\,\inf\{t\geq0\;:\; \overline{X}_N(t)\in \{\lfloor (x^{\star}+r)N \rfloor + 1\}\cup \{\lceil (x^{\star}-r)N \rceil - 1\}\}$
. To apply Theorem 5.1, we take f to be the identity function and the metric to be
$d(x,\,y)=\lvert x-y \rvert$
so that
$L=1$
. The jump size of
$\overline{X}_N(t)$
is clearly bounded by
$D=1$
, and for all
$x\in \{0,\ldots,N\}$
we have
\begin{equation*} -Q(x,x) \le \lambda x(1-x/N)+\varepsilon(N-x)+\mu x\leq(\lambda+\mu+\varepsilon)N\,:\!=\,q. \end{equation*}
Finally, we show that there is a coupling
$(\overline{W}_N(t), \overline{Z}_N(t))$
of two copies of
$\overline X_N(t)$
which satisfies (5.2) for all
$(\overline{W}_N(0), \overline{Z}_N(0))=(w,z)\in E\times E$
, and hence
$\overline{X}_N(t)$
is contracting in Wasserstein distance. The coupling is that used earlier in Subsection 4.3, where the copies move independently until they collide, and then they move in unison. Verifying (5.2) for this coupling proceeds very similarly to verifying condition (i) in Proposition 4.1.
To compute the left-hand side of (5.2), first note that if the two copies have already collided with each other, then the left-hand side is 0. Otherwise, the left-hand side is the same as in (4.13) with
$\eta$
replaced by r. Since we have chosen r to be less than
$J/(6\lambda)$
, for sufficiently large N we must have
$J-2\lambda r-2\lambda N^{-1}\geq J/2$
. Therefore (5.2) is satisfied with
$\ell=J/2$
. Then, Theorem 5.1 implies that for all
$x_0\in \widehat{E}\,:\!=\,NI(r)$
,
$t\geq0$
, and
$\xi>0$
,
\begin{align*} \overline{\mathbb{P}}_{x_0}\!\left(\left\{\left\lvert \overline{X}_N(t)-\overline{\mathbb{E}}_{x_0}(\overline{X}_N(t))\right\rvert \geq \xi\sqrt{N}\right\}\cap \{\tau^{\overline{X}}_{\mathrm{exit}}(I(r))\geq t\}\right)\leq 2{\mathrm{e}}^{-\frac{\xi^2}{2(\lambda+\mu+\varepsilon)/J+2\xi/(3\sqrt{N})}}. \end{align*}
Moreover, since
$X_N(t)$
and
$\overline{X}_N(t)$
are pathwise indistinguishable in probability before leaving NI(r), we have
\begin{align*} \big\lvert \mathbb{E}_{x_0}(X_N(t))-\overline{\mathbb{E}}_{x_0}(\overline{X}_N(t))\big\rvert &= \left \lvert \mathbb{E}_{x_0}\big(X_N(t)\unicode{x1D7D9}_{\tau^{X}_{\mathrm{exit}}(I(r))< t} \big)-\overline{\mathbb{E}}_{x_0}\big(\overline{X}_N(t)\unicode{x1D7D9}_{\tau^{\overline X}_{\mathrm{exit}}(I(r))< t}\big) \right\rvert\\ &\leq N \mathbb{P}_{x_0}\big(\tau^{X}_{\mathrm{exit}}(I(r))< t\big). \end{align*}
The second part of Lemma 4.3 implies that for all
$t\leq t_{\mathrm{follow}}$
,
$x_0/N\in I(\frac{r}{2})\subset I(r)$
, and sufficiently large N, we have
\begin{equation} \mathbb{P}_{x_0}\big(\tau^{X}_{\mathrm{exit}}(I(r))< t\big)\leq \mathbb{P}_{x_0}\big(\tau^{X}_{\mathrm{exit}}(I(r))\leq t_{\mathrm{follow}}\big)\leq 4{\mathrm{e}}^{-C_1N^h},\end{equation}
and hence
\begin{equation*} \left\lvert \mathbb{E}_{x_0}(X_N(t))-\overline{\mathbb{E}}_{x_0}(\overline{X}_N(t)) \right\rvert=o(1). \end{equation*}
Now, for any fixed
$\xi>0$
, choose N large enough so that
$\lvert \mathbb{E}_{x_0}(X_N(t))-\overline{\mathbb{E}}_{x_0}(\overline{X}_N(t)) \rvert<\xi\sqrt{N}$
. It follows that
\begin{align*} &\mathbb{P}_{x_0}\!\left(\left\{\left\lvert X_N(t)-\mathbb{E}_{x_0}(X_N(t))\right\rvert \geq 2\xi\sqrt{N}\right\}\cap \{\tau^{X}_{\mathrm{exit}}(I(r))\geq t\}\right)\\ &\quad\leq \overline{\mathbb{P}}_{x_0}\!\left(\left\{\left\lvert \overline{X}_N(t)-\overline{\mathbb{E}}_{x_0}(\overline{X}_N(t))\right\rvert \geq \xi\sqrt{N}\right\}\cap \{\tau^{\overline{X}}_{\mathrm{exit}}(I(r))\geq t\}\right) \\ &\quad\leq 2{\mathrm{e}}^{-\frac{\xi^2}{2(\lambda+\mu+\varepsilon)/J+2\xi/(3\sqrt{N})}}. \end{align*}
Together with (5.3), we obtain
\begin{align*} \mathbb{P}_{x_0}\!\left(\left\lvert X_N(t)-\mathbb{E}_{x_0}(X_N(t))\right\rvert \geq 2\xi\sqrt{N}\right) &\leq 2{\mathrm{e}}^{-\frac{\xi^2}{2(\lambda+\mu+\varepsilon)/J+2\xi/(3\sqrt{N})}}+4{\mathrm{e}}^{-C_1N^h}\\ & \leq 3{\mathrm{e}}^{-\frac{J\xi^2}{3(\lambda+\mu+\varepsilon)}} \end{align*}
for N large enough, as required.
Acknowledgements
We thank the editors for their thoughtful handling of the paper, and two anonymous referees for their comments, which, in particular, led to an improved discussion of related literature.
Funding information
The research of Malwina Luczak is currently supported by the Leverhulme Trust, grant reference LIP-2022-005, and was previously supported by an Australian Research Council Future Fellowship (FT170104009).
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
