text:
# Discrete small world networks

## 1 Introduction

There are many variants of the mathematical model introduced by Watts and Strogatz  to describe the “small–world” networks popular in the social sciences; one of them, the great circle model of Ball et. al. , actually precedes . See  for a recent overview, as well as the books  and . A typical description is as follows. Starting from a ring lattice with $`L`$ vertices, each vertex is connected to all of its neighbours within distance $`k`$ by an undirected edge. Then a number of shortcuts are added between randomly chosen pairs of sites. Interest centres on the statistics of the shortest distance between two (randomly chosen) vertices, when shortcuts are taken to have length zero.

Newman, Moore and Watts ,  proposed an idealized version, in which the lattice is replaced by a circle and distance along the circle is the usual arc length, shortcuts now being added between random pairs of uniformly distributed points. Within their \[NMW\] model, they made a heuristic computation of the mean distance between a randomly chosen pair of points. Then Barbour and Reinert  proved an asymptotic approximation for the distribution of this distance as the mean number $`L\rho `$ of shortcuts tends to infinity; the parameter $`\rho `$ describes the average intensity of end points of shortcuts around the circle. In this paper, we move from the continuous model back to a genuinely discrete model, in which the ring lattice consists of exactly $`L`$ vertices, each with connections to the $`k`$ nearest neighbours on either side, but in which the random shortcuts, being edges of the graph, are taken to have length $`1`$; thus distance becomes the usual graph distance between vertices. However, this model is rather complicated to analyze, so we first present a simpler version, in which time runs in discrete steps, but the process still lives on the continuous circle, and which serves to illustrate the main qualitative differences between discrete and continuous models. This intermediate model would be reasonable for describing the spread of a simple epidemic, when the incubation time of the disease is a fixed value, and the infectious period is very short in comparison. In each of these more complicated models, we also show that the approximation derived for the \[NMW\] model gives a reasonable approximation to the distribution of inter-point distances, provided that $`\rho `$ (or its equivalent) is small; here, the error in Kolmogorov distance is of order $`O(\rho ^{\frac{1}{3}}\mathrm{log}(\frac{1}{\rho }))`$, although the distribution functions are only $`O(\rho )`$ apart in the bulk of the distribution.

## 2 The continuous circle model for discrete time

In this section, we consider the continuous model of , which consists of a circle $`C`$ of circumference $`L`$, to which are added a Poisson $`\mathrm{Po}(L\rho /2)`$ number of uniform and independent random chords, but now with a new measure of distance between points $`P`$ and $`Q`$. This distance is the minimum of $`d(\gamma )`$ over paths $`\gamma `$ along the graph between $`P`$ and $`Q`$, where, if $`\gamma `$ consists of $`s`$ arcs of lengths $`l_1,\mathrm{},l_s`$ connected by shortcuts, then $`d(\gamma ):=_{r=1}^sl_r`$, where, as usual, $`l`$ denotes the smallest integer $`ml`$; shortcuts make no contribution to the distance. We are interested in asymptotics as $`L\rho \mathrm{}`$, and so assume throughout that $`L\rho >1`$.

We begin with a dynamic realization of the network, which describes, for each $`n0`$, the set of points $`R(n)C`$ that can be reached from a given point $`P`$ within time $`n`$, where time corresponds to the $`d()`$ distance along paths. Pick Poisson $`\mathrm{Po}(L\rho )`$ uniformly and independently distributed ‘potential’ chords of the circle $`C`$; such a chord is an unordered pair of independent and uniformly distributed random points of $`C`$. Label one point of each pair with $`1`$ and the other with $`2`$, making the choices equiprobably, independently of everything else. We call the set of label 1 points $`Q`$, and, for each $`qQ`$, we let $`q^{}=q^{}(q)`$ denote the label 2 end point. Our construction realizes a random subset of these potential chords as shortcuts. We start by taking $`R(0)=\{P\}`$ and $`B(0)=1`$, and let time increase in integer steps. $`R(n)`$ then consists of a union of $`B(n)`$ intervals of $`C`$, each of which is increased by unit length at each end point at time $`n+1`$, but with the rule that overlapping intervals are merged into a single interval; this defines a new union of $`B^{}(n+1)`$ intervals $`R^{}(n+1)`$; note that $`B^{}(n+1)`$ may be less than $`B(n)`$.

Now define $`R(n+1):=R^{}(n+1)R(n)`$. Whenever $`R(n+1)Q`$ is not empty — that is, whenever $`R(n+1)`$ includes label 1 points — then, for each $`qR(n+1)Q`$, we accept the chord $`\{q,q^{}\}`$ if $`q^{}=q^{}(q)R^{}(n+1)`$ (that is, if the chord would reach beyond the cluster $`R^{}(n+1)`$), we reject it if $`q^{}R(n)`$, and we accept the chord $`\{q,q^{}\}`$ with probability $`1/2`$ if $`q^{}R(n+1)`$, independently of all else. Letting $`Q(n+1):=\{q^{}:\{q,q^{}\}\text{ newly accepted}\}`$, take $`R(n+1)=R^{}(n+1)Q(n+1)`$ and set $`B(n+1)=B^{}(n+1)+|Q(n+1)|`$. Note that $`B(n+1)`$ may be either larger or smaller than $`B(n)`$, and that $`B_{L/2}=1`$ a.s.

After at most $`L/2`$ time steps, each of the potential chords has been either accepted or rejected independently with probability $`1/2`$, because of auxiliary randomization for those chords such that $`\{q,q^{}\}R(n)`$ for some $`n`$, and because of the random labelling of the end points of the chords for the remainder. Hence this construction does indeed lead to $`\mathrm{Po}(L\rho /2)`$ independent uniform chords of $`C`$.

For our analysis, as in , we define a second process $`S(n)`$, starting from the same $`P`$ and the same set of potential chords, and with the same unit growth per time step. The differences are that every potential chord is included, so that no thinning takes place, and, additionally, whenever two intervals intersect, they continue to grow, overlapping one another, and each continues to generate further chords according to a Poisson process of rate $`\rho `$. This pure growth process $`S(n)`$ agrees with the original construction during the initial development with high probability, until $`S`$ has grown enough that overlap becomes likely; its advantage is that it has a branching structure, and is thus much more easily analysed. We denote its length at time $`n`$ by $`s(n)r(n)`$, overlaps now being counted according to multiplicity, and the number of intervals by $`M(n)B(n)`$. Then $`M(n)`$ is just a pure birth chain with offspring distribution $`1+\mathrm{Po}(2\rho )`$, so that $`𝐄M(n)=(1+2\rho )^n`$, and the total length of the $`M(n)`$ intervals is given by

$$s(n)=2\underset{k=0}{\overset{n1}{}}M(k),$$

so that

$$𝐄s(n)=\rho ^1((1+2\rho )^n1).$$

Furthermore,

$$W(n):=(1+2\rho )^nM(n)$$

forms a square integrable martingale, so that $`(1+2\rho )^nM(n)W_\rho `$ a.s. for some $`W_\rho `$ such that $`W_\rho >0`$ a.s. and $`𝐄W_\rho =1`$. Hence also $`(1+2\rho )^ns(n)\rho ^1W_\rho `$ a.s. and $`\frac{s(n)}{M(n)}\rho ^1`$ a.s.. Note also that $`\mathrm{Var}W(n)1.`$

Our strategy is to pick a starting point $`P`$, and run both constructions up to an integer time $`\tau _r`$, chosen in such a way that $`R(n)`$ and $`S(n)`$ are (almost) the same for $`n\tau _r`$. Pick

$$n_0=\frac{\mathrm{log}\left(L\rho \right)}{2\mathrm{log}(1+2\rho )},$$

where $`x`$ denotes the largest integer no greater than $`x`$, and let

$$\varphi _0:=\varphi _0(L,\rho )=(L\rho )^{1/2}(1+2\rho )^{n_0},$$

so that $`(1+2\rho )^{n_0}=\varphi _0\sqrt{L\rho }`$ and $`(1+2\rho )^1\varphi _01`$; note that $`\varphi _01`$ if $`\rho `$ is small. Now let $`\tau _r=n_0+r`$, and assume that

$$|r|\frac{1}{6\mathrm{log}(1+2\rho )}\mathrm{log}\left(L\rho \right),$$
(2.1)
implying in particular that $`\tau _r\frac{2\mathrm{log}(L\rho )}{3\mathrm{log}(1+2\rho )}`$. Then, writing $`R_r=R(\tau _r),S_r=S(\tau _r),M_r=M(\tau _r)`$, and $`s_r=s(\tau _r)`$, we have

$$𝐄M_r=\varphi _0\sqrt{L\rho }(1+2\rho )^r$$

and

$$𝐄s_r=\rho ^1(\varphi _0\sqrt{L\rho }(1+2\rho )^r1).$$

Next, independently and uniformly, we pick a second point $`P^{}C`$, and a second set of potential chords, $`Q^{}`$, and run both constructions for time $`\tau _r^{}`$, where $`r^{}`$ also satisfies (2.1), yielding $`R_r^{}^{},S_r^{}^{},M_r^{}^{}=:N_r^{}`$ and $`s_r^{}^{}=:u_r^{}`$. Then, at least for small $`\rho `$, there are about $`\varphi _0^2L\rho (1+2\rho )^{r+r^{}}`$ pairs of intervals, with one in $`S_r`$ and the other in $`S_r^{}^{}`$, and each is of typical length $`\rho ^1`$, so that the expected number of intersecting pairs of intervals is about

$$\frac{2}{L\rho }\varphi _0^2L\rho (1+2\rho )^{r+r^{}}=2\varphi _0^2(1+2\rho )^{r+r^{}},$$

which, in the chosen range of $`r,r^{}`$, grows from almost nothing to the typically large value $`2\varphi _0^2(L\rho )^{1/3}`$. For later use, label the intervals in $`S_r`$ as $`I_1,\mathrm{},I_{M_r}`$, and the intervals in $`S_r^{}^{}`$ as $`J_1,\mathrm{},J_{N_r^{}}`$; then we can write the number $`\widehat{V}_{r,r^{}}`$ of intersecting pairs of intervals as

$`\widehat{V}_{r,r^{}}={\displaystyle \underset{i=1}{\overset{M_r}{}}}{\displaystyle \underset{j=1}{\overset{N_r^{}}{}}}X_{ij},`$ (2.2)
where

$`X_{ij}=\mathrm{𝟏}\{I_iJ_j\mathrm{}\}.`$ (2.3)
Now the probability that $`\widehat{V}_{r,r^{}}=0`$ is the same as when the construction for $`S^{}`$ uses the original set $`Q`$ of potential chords, because of the independence of Poisson processes on disjoint subsets; the event $`\widehat{V}_{r,r^{}}=0`$ indicates that the two processes have no intersecting pairs of intervals when stopped at the times $`\tau _r`$, $`\tau _r^{}`$, and thus use disjoint sets of chords. Furthermore, we can show that the event $`\widehat{V}_{r,r^{}}=0`$ is with high probability the same as the event $`V_{r,r^{}}=0`$, where $`V_{r,r^{}}`$ is the number of intersections of $`R(r)`$ and $`R^{}(r^{})`$. Finally, if $`R(r)`$ and $`R^{}(r^{})`$ have no intersections, then the “small worlds” distance between $`P`$ and $`P^{}`$ is more than

$$\tau _r+\tau _r^{}=2n_0+r+r^{}.$$

Hence we have solved the problem if we can find a good approximation to the probability that $`\widehat{V}_{r,r^{}}=0`$; this we do by showing that $`\widehat{V}_{r,r^{}}`$ approximately has a mixed Poisson distribution, and by identifying the mixture distribution. We usually take $`r=r^{}`$ or $`r=r^{}+1`$, the latter to allow for the possibility of the number of steps in the shortest path being odd.

After this preparation, we are in a position to summarize our main results. These are treated in more detail in the next section, in Theorem 3.9, Corollary 3.10 and Theorem 3.15. We let $`D`$ denote the small worlds distance between a randomly chosen pair of points $`P`$ and $`Q`$ on $`C`$, so that, as above,

$$𝐏[D>2n_0+r+r^{}]=𝐏[V_{r,r^{}}=0].$$

The following theorem approximates the distribution of $`D`$ by that of another random variable $`D^{}`$, whose distribution is more accessible; in this theorem, $`\rho `$ and the derived quantities $`\varphi _0,n_0,N_0`$ and $`x_0`$ all implicitly depend on $`L`$, as does the distribution of $`D^{}`$.

###### Theorem 2.1

Let $`\mathrm{\Delta }`$ denote a random variable on the integers with distribution given by

$`𝐏\left[\mathrm{\Delta }>x\right]=𝐄\{e^{2\varphi _0^2(1+2\rho )^xW_\rho W_\rho ^{}}\},x𝐙,`$
and set $`D^{}=\mathrm{\Delta }+2n_0`$. If $`L\rho \mathrm{}`$ and $`\rho =\rho (L)=O(L^\beta )`$, with $`\beta <4/31`$, then

$`d_{TV}((D),(D^{}))0\text{as}L\mathrm{}.`$
1. If $`\rho `$ is large, let $`N_0`$ be such that $`(1+2\rho )^{N_0}L\rho <(1+2\rho )^{N_0+1}`$, and define $`\alpha [0,1)`$ to be such that $`L\rho =(1+2\rho )^{N_0+\alpha }`$; then, with $`x_0=N_02n_0+1`$,

$`𝐏\left[\mathrm{\Delta }x_0\right]`$ $``$ $`12(1+2\rho )^\alpha ;`$
$`𝐏\left[\mathrm{\Delta }x_0+1\right]`$ $`=`$ $`O\left((1+2\rho )^{1+\alpha }\mathrm{log}(1+\rho )\right),`$
so that $`\mathrm{\Delta }`$ concentrates almost all its mass on $`x_0`$, unless $`\alpha `$ is very close to $`1`$.
2. If $`\rho 0`$, the distribution of $`\rho \mathrm{\Delta }`$ approaches that of the random variable $`T`$ defined in , Corollary 3.10:

$`𝐏[\rho \mathrm{\Delta }>x]𝐏\left[T>x\right]={\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{e^y}{1+2e^{2x}y}}𝑑y.`$

The errors in these distributional approximations are also quantified, for given choices of $`L`$ and $`\rho (L)`$.

This result shows that, for $`\rho `$ small and $`x=l\rho `$ with $`l𝐙`$,

$`𝐏[\rho \mathrm{\Delta }>x]`$ $`=`$ $`𝐄\{e^{2\varphi _0^2(1+2\rho )^{x/\rho }W_\rho W_\rho ^{}}\}`$ (2.4)
$``$ $`𝐄\{e^{2e^{2x}WW^{}}\}=𝐏[T>x],`$
where $`W`$ and $`W^{}`$ are independent NE$`(1)`$ random variables. Indeed, it follows from Lemma 3.13 below that $`W_\rho _𝒟W`$ as $`\rho 0`$. One way of realizing a random variable $`T`$ with the above distribution is to realize $`W`$ and $`W^{}`$, and then to sample $`T`$ from the conditional distribution

$`𝐏[T>x|W,W^{}]`$ $`=`$ $`e^{2e^{2x}WW^{}}`$ (2.5)
$`=`$ $`e^{\mathrm{exp}\{2x+\mathrm{log}2+\mathrm{log}W+\mathrm{log}W^{}\}}`$
$`=`$ $`e^{\mathrm{exp}\{2x+\mathrm{log}2G_1G_2\}},`$
where $`G_1:=\mathrm{log}W`$ and $`G_2:=\mathrm{log}W^{}`$ both have the Gumbel distribution. With this construction,

$`𝐏[2T\{G_1+G_2\mathrm{log}2\}>x|W,W^{}]=e^{e^x},`$
whatever the values of $`W`$ and $`W^{}`$, and hence of $`G_1`$ and $`G_2`$, implying that

$$2T=_𝒟G_1+G_2G_3\mathrm{log}2,$$

where $`G_1,G_2`$ and $`G_3`$ are independent random variables with the Gumbel distribution. The cumulants of $`T`$ can thus immediately be deduced from those of the Gumbel distribution, given in Gumbel :

$`𝐄T`$ $`=`$ $`{\displaystyle \frac{1}{2}}(\gamma \mathrm{log}2)0.058;`$
$`\mathrm{Var}T`$ $`=`$ $`{\displaystyle \frac{\pi ^2}{8}}.`$
Note that, in view of Corollary 3.2 below, the conditional construction (2.5) can be interpreted in terms of the processes $`S`$ and $`S^{}`$, since $`W_\rho `$ and $`W_\rho ^{}`$ are essentially determined by the early stages of the respective pure birth processes, and the extra randomness, conditional on the values of $`W_\rho `$ and $`W_\rho ^{}`$, comes from the random arrangement of the intervals on the circle $`C`$.

In the NMW heuristic, the random variable $`T_{NMW}`$ is logistic, having distribution function $`e^{2x}(1+e^{2x})^1`$; note that this is just the distribution of $`\frac{1}{2}(G_1G_3)`$. Hence the heuristic effectively neglects some of the initial branching variation.

## 3 The continuous circle model: proofs

The first step in the argument outlined above is to establish a Poisson approximation theorem for the number of pairs of overlapping intervals, one in $`S_r`$ and the other in $`S_r^{}^{}`$. The following result has been shown in .

###### Proposition 3.1

Let $`M`$ intervals $`I_1,\mathrm{},I_M`$ with lengths $`t_1,\mathrm{},t_M`$ and $`N`$ intervals $`J_1,\mathrm{},J_N`$ with lengths $`u_1,\mathrm{},u_N`$ be positioned uniformly and independently on $`C`$. Set $`V:=_{i=1}^M_{j=1}^NX_{ij}`$, where $`X_{ij}:=I[I_iJ_j\mathrm{}]`$. Then

$$d_{TV}((V),\mathrm{Po}(\lambda _{(M,N,t,u)}))4(M+N)v_{tu}/L,$$

where $`\lambda _{(M,N,t,u)}:=L^1(Nt+Mu)`$, $`t:=_{i=1}^Mt_i`$, $`u:=_{j=1}^Nu_j`$ and $`v_{tu}:=\mathrm{max}\{\mathrm{max}_it_i,\mathrm{max}_ju_j\}`$.

The proposition translates immediately into a useful statement about $`\widehat{V}_{r,r^{}}`$, when $`P^{}`$ is chosen uniformly at random, independently of all else.

###### Corollary 3.2

For the processes $`S`$ and $`S^{}`$ of the previous section, we have

$`|𝐏[\widehat{V}_{r,r^{}}=0|M_r=M,N_r^{}=N,s_r=t,u_r^{}=u]\mathrm{exp}\{L^1(Nt+Mu)\}|`$
$`8L^1(M\tau _r+N\tau _r^{}).`$
Remark. If $`P^{}`$ is not chosen at random, but is a fixed point of $`C`$, the result of Corollary 3.2 remains essentially unchanged, provided that $`P`$ and $`P^{}`$ are more than an arc distance of $`\tau _r+\tau _r^{}`$ apart. The only difference is that then $`X_{11}=0`$ a.s., and that $`Nt+Mu`$ is replaced by $`Nt+Mu2\tau _r2\tau _r^{}`$. If $`P`$ and $`P^{}`$ are less than $`\tau _r+\tau _r^{}`$ apart, then $`𝐏[\widehat{V}_{r,r^{}}=0]=0`$.

The next step is to show that $`𝐏[\widehat{V}_{r,r^{}}=0]`$ is close to $`𝐏[V_{r,r^{}}=0]`$. We do this by directly comparing the random variables $`\widehat{V}_{r,r^{}}`$ and $`V_{r,r^{}}`$ in the joint construction. As for Corollary 3.5 in , the following assertion can easily be shown to hold.

###### Proposition 3.3

With notation as above, we have

$$𝐏[\widehat{V}_{r,r^{}}V_{r,r^{}}]32\tau _r\tau _r^{}L^2𝐄\{\frac{1}{2}M_rN_r^{}(M_r+N_r^{}2)\}.$$

To apply Corollary 3.2 and Proposition 3.3, it remains to establish more detailed information about the distributions of $`M_r`$ and $`s_r`$. In particular, we need to bound the first and second moments of $`M_r`$, and to approximate the quantity $`𝐄(\mathrm{exp}\{L^1(N_r^{}s_r+M_ru_r^{})\})`$. We begin with the following lemma.

###### Lemma 3.4

The random variable $`M(n)`$ has as probability generating function

$`G_{M(n)}(s):=𝐄s^{M(n)}=f^{(n)}(s),f(s)=se^{2\rho (s1)},`$
where $`f^{(n)}`$ denotes the $`n`$th iteration of $`f`$. In particular, we have

$`𝐄M_r`$ $`=`$ $`\varphi _0\sqrt{L\rho }(1+2\rho )^r`$
$`{\displaystyle \frac{1}{2}}𝐄M_r(M_r1)`$ $`=`$ $`(\rho +1)\varphi _0\sqrt{L\rho }(1+2\rho )^{r1}\left\{\varphi _0\sqrt{L\rho }(1+2\rho )^r1\right\}`$
$``$ $`\varphi _0^2L\rho (1+2\rho )^{2r}.`$
Proof: Since $`M(n)`$ is a branching process with $`1+\mathrm{Po}(2\rho )`$ offspring distribution, the probability generating function is immediate, as are the moment calculations

$`𝐄M(n)`$ $`=`$ $`(1+2\rho )^n;`$
$`𝐄M(n)(M(n)1)`$ $`=`$ $`2(\rho +1)(1+2\rho )^{n1}\left\{(1+2\rho )^n1\right\}.`$
The moments of $`M_r`$ follow from the definition of $`\tau _r`$. $`[]`$

These estimates can be directly applied in Corollary 3.2 and Proposition 3.3. Define

$`\eta _1(r,r^{})`$ $`:=`$ $`64\{\rho (n_0+(rr^{}))\}^2\varphi _0^3(1+2\rho )^{r+r^{}+(rr^{})}`$ (3.1)
$`\eta _2(r,r^{})`$ $`:=`$ $`16\{\rho (n_0+(rr^{}))\}\varphi _0(1+2\rho )^{(rr^{})}.`$ (3.2)
###### Corollary 3.5

We have

$$𝐏[\widehat{V}_{r,r^{}}V_{r,r^{}}]\eta _1(r,r^{})(L\rho )^{1/2}$$

and

$$|𝐏[V_{r,r^{}}=0]𝐄\mathrm{exp}\{L^1(N_r^{}s_r+M_ru_r^{})\}|\{\eta _1(r,r^{})+\eta _2(r,r^{})\}(L\rho )^{1/2}.$$

Consideration of the quantity $`𝐄(\mathrm{exp}\{L^1(N_r^{}s_r+M_ru_r^{})\})`$ now gives the immediate asymptotics of

$$𝐏[V_{r,r^{}}=0]=𝐏[D>2n_0+r+r^{}],$$

where $`D`$ denotes the “small world” distance between $`P`$ and $`P^{}`$.

###### Corollary 3.6

If $`\rho =\rho (L)`$ is bounded above and $`L\rho \mathrm{}`$, then as $`L\mathrm{}`$,

$`|𝐏[D>2n_0+r+r^{}]𝐄\mathrm{exp}\{2\varphi _0^2(1+2\rho )^{r+r^{}}W_\rho W_\rho ^{}\}|0`$
uniformly in $`|r|,|r|^{}\frac{1}{6\mathrm{log}(1+2\rho )}\mathrm{log}\left(L\rho \right)`$, where $`W_\rho `$ and $`W_\rho ^{}`$ are independent copies of the limiting random variable associated with the pure birth chain $`M`$.

Proof: The conditions ensure that $`\tau _r`$ and $`\tau _r^{}`$ both tend to infinity as $`L\mathrm{}`$, at least as fast at $`c\mathrm{log}(L\rho )`$, for some $`c>0`$. Then, since $`W(n)=(1+2\rho )^nM(n)W_\rho `$ a.s. and $`s(n)/M(n)\rho ^1`$ a.s., and since $`(1+2\rho )^{\tau _r+\tau _r^{}}=\varphi _0^2(1+2\rho )^{r+r^{}}L\rho `$, it is clear that

$`\mathrm{exp}\{L^1(N_r^{}s_r+M_ru_r^{})\}`$ $``$ $`\mathrm{exp}\{2(L\rho )^1M_rN_r^{}\}`$
$`=`$ $`\mathrm{exp}\left\{2(L\rho )^1(1+2\rho )^{\tau _r+\tau _r^{}}W(\tau _r)W^{}(\tau _r^{})\right\}`$
$``$ $`\mathrm{exp}\{2\varphi _0^2(1+2\rho )^{r+r^{}}W_\rho W_\rho ^{}\},`$
uniformly for $`r`$, $`r^{}`$ in the given ranges. $`[]`$

Hence $`𝐏[D>2n_0+r+r^{}]`$ can be approximated in terms of the distribution of the limiting random variable $`W_\rho `$ associated with the pure birth chain $`M`$. However, in contrast to the model with time running continuously, this distribution is not always $`\mathrm{NE}(1)`$, but genuinely depends on $`\rho `$. Its properties are not so easy to derive, though moments can be calculated, and, in particular,

$$𝐄W_\rho =1;\mathrm{Var}W_\rho =1/(1+2\rho );$$
(3.3)
it is also shown in Lemma 3.13 that $`(W_\rho )`$ is close to $`\mathrm{NE}(1)`$ for $`\rho `$ small. We also need the following lemma, which is useful in bounding the behaviour of the upper tail of $`(D)`$.

###### Lemma 3.7

For all $`\theta ,\rho >0`$,

$$𝐄(e^{\theta W_\rho W_\rho ^{}})\theta ^1\mathrm{log}(1+\theta ).$$

Proof: The offspring generating function of the birth process $`M`$ satisfies

$$f(s)=se^{2\rho (s1)}s\{1+2\rho (1s)\}^1=:f_1(s)$$

for all $`0s1`$. Hence, with $`m=1+2\rho `$,

$$𝐄(e^{\psi W_\rho })=\underset{n\mathrm{}}{lim}f^{(n)}(e^{\psi m^n})\underset{n\mathrm{}}{lim}f_1^{(n)}(e^{\psi m^n})=(1+\psi )^1.$$
(3.4)
The last equality follows from (8.11), p.17 in , noting that the right-hand side is the Laplace transform of the NE(1) - distribution. Furthermore, we have

$$(1+\theta w)^1=\theta ^1_0^{\mathrm{}}e^{tw}e^{t/\theta }𝑑t,$$

and so, applying (3.4) twice, and because the function $`(1+t)^1`$ is decreasing in $`t0`$, we obtain

$`𝐄\left(e^{\theta W_\rho W_\rho ^{}}\right)`$ $``$ $`𝐄\{(1+\theta W_\rho )^1\}`$
$`=`$ $`\theta ^1{\displaystyle _0^{\mathrm{}}}𝐄e^{tW_\rho }e^{t/\theta }𝑑t`$
$``$ $`\theta ^1{\displaystyle _0^{\mathrm{}}}(1+t)^1e^{t/\theta }𝑑t`$
$``$ $`\theta ^1{\displaystyle _0^\theta }(1+t)^1𝑑t=\theta ^1\mathrm{log}(1+\theta ),`$
as required. $`[]`$

The simple asymptotics of Corollary 3.6 can be sharpened. At first sight surprisingly, it turns out that it is not necessary for the times $`\tau _r`$ and $`\tau _r^{}`$ to tend to infinity, since, for values of $`\rho `$ so large that $`n_0`$ is bounded, the quantities $`W(n)`$ are (almost) constant for all $`n`$. Write

$`(1+2\rho )^ns(n)`$ $`=`$ $`2{\displaystyle \underset{j=0}{\overset{n1}{}}}W(j)(1+2\rho )^{(nj)}`$ (3.5)
$`=`$ $`{\displaystyle \frac{1}{\rho }}W(n)+{\displaystyle \frac{1+\rho }{\rho }}U(n),`$
where

$`{\displaystyle \frac{1+\rho }{\rho }}U(n)`$ $`=`$ $`2{\displaystyle \underset{j=0}{\overset{n1}{}}}(W(j)W(n))(1+2\rho )^{(nj)}W(n)\rho ^1(1+2\rho )^n.`$
Computation gives $`𝐄U(n)=(1+\rho )^1(1+2\rho )^n`$, and

$$𝐄\{(W(n)W(j))(W(n)W(\mathrm{}))\}=\frac{1}{(1+2\rho )^{j+1}}\left(1\frac{1}{(1+2\rho )^{nj}}\right)$$

if $`j\mathrm{}`$, so that

$`\mathrm{Var}\{U(n)\}`$ $``$ $`2{\displaystyle \frac{2(1+2\rho )^n+2(1+2\rho )^{2n}}{(1+\rho )^2}}`$ (3.6)
$``$ $`8{\displaystyle \frac{(1+2\rho )^n}{(1+\rho )^2}},`$
and thus

$$(1+\rho )^2𝐄\{U(n)^2\}9(1+2\rho )^n.$$
(3.7)
Then we have

$`L^1(N_r^{}s_r+M_ru_r^{})`$
$`=`$ $`\varphi _0^2(1+2\rho )^{r+r^{}}\{W(\tau _r)(W^{}(\tau _r^{})+(1+\rho )U_r^{}^{})+W^{}(\tau _r^{})(W(\tau _r)+(1+\rho )U_r)\},`$
where $`W(\tau _r):=W(\tau _r)`$ and $`U_r:=U(\tau _r)`$, so that, by Taylor’s expansion, and because $`𝐄W(n)=1`$ for all $`n`$,

$`\left|𝐄\mathrm{exp}\{L^1(N_r^{}s_r+M_ru_r^{})\}𝐄\mathrm{exp}\{2\varphi _0^2(1+2\rho )^{r+r^{}}W(\tau _r)W^{}(\tau _r^{})\}\right|`$
$`\varphi _0^2(1+2\rho )^{r+r^{}}(1+\rho )\{𝐄|U_r|+𝐄|U_r^{}^{}|\}`$ (3.8)
and

$`\left|𝐄\mathrm{exp}\{2\varphi _0^2(1+2\rho )^{r+r^{}}W(\tau _r)W^{}(\tau _r^{})\}𝐄\mathrm{exp}\{2\varphi _0^2(1+2\rho )^{r+r^{}}W_\rho W_\rho ^{}\}\right|`$
$`2\varphi _0^2(1+2\rho )^{r+r^{}}\{𝐄|W_\rho W(\tau _r)|+𝐄|W_\rho ^{}W^{}(\tau _r^{})|\}.`$ (3.9)
Using these results, we obtain the following theorem.

###### Theorem 3.8

If $`P^{}`$ is randomly chosen on $`C`$, then

$`\left|𝐏[D>2n_0+r+r^{}]𝐄\{e^{2\varphi _0^2(1+2\rho )^{r+r^{}}W_\rho W_\rho ^{}}\}\right|`$
$`\{\eta _1(r,r^{})+\eta _2(r,r^{})\}(L\rho )^{1/2}+\eta _3(r,r^{})(L\rho )^{1/4},`$
where $`\eta _1,\eta _2`$ are given in (3.1) and (3.2),

$$\eta _3(r,r^{}):=10\varphi _0^{3/2}(1+2\rho )^{r+r^{}\frac{1}{2}(rr^{})}$$

and where, as before, $`D`$ denotes the shortest distance between $`P`$ and $`P^{}`$ on the shortcut graph.

Proof: Since $`\{V_{r,r^{}}=0\}=\left\{D>2n_0+r+r^{}\right\}`$, we use Corollary 3.5 and (3.8) and (3.9) to give

$`\left|𝐏[D>2n_0+r+r^{}]𝐄\{e^{2\varphi _0^2(1+2\rho )^{r+r^{}}W_\rho W_{\rho }^{}{}_{}{}^{}}\}\right|`$ (3.10)
$``$ $`\{\eta _1(r,r^{})+\eta _2(r,r^{})\}(L\rho )^{1/2}+\varphi _0^2(1+2\rho )^{r+r^{}}(1+\rho )\{𝐄|U_r|+𝐄|U_r^{}^{}|\}`$
$`+2\varphi _0^2(1+2\rho )^{r+r^{}}\{𝐄|W_\rho W(\tau _r)|+𝐄|W_\rho ^{}W^{}(\tau _r^{})|\}.`$
Now, from (3.7) and the Cauchy-Schwarz inequality,

$$(1+\rho )𝐄|U_r|3(L\rho )^{1/4}\varphi _0^{1/2}(1+2\rho )^{r/2}.$$
(3.11)
Then, since $`W(n)`$ is a martingale, and

$`W_\rho W(n)`$ $`=`$ $`{\displaystyle \underset{\mathrm{}=n}{\overset{\mathrm{}}{}}}(W(\mathrm{}+1)W(\mathrm{}))`$
$`=`$ $`{\displaystyle \underset{\mathrm{}=n}{\overset{\mathrm{}}{}}}(1+2\rho )^\mathrm{}1(M(\mathrm{}+1)(1+2\rho )M(\mathrm{})),`$
we have

$`𝐄(W_\rho W(n))^2`$ $`=`$ $`{\displaystyle \underset{\mathrm{}=n}{\overset{\mathrm{}}{}}}(1+2\rho )^{2(\mathrm{}+1)}𝐄(M(\mathrm{}+1)(1+2\rho )M(\mathrm{}))^2.`$
Now

$`M(\mathrm{}+1)`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{M(\mathrm{})}{}}}(Z_{\mathrm{}+1}(i)+1),`$
where $`(Z_{\mathrm{}}(i))_{\mathrm{},i}`$ are i.i.d. $`\mathrm{Po}(2\rho )`$-variates, and so

$`𝐄(M(\mathrm{}+1)(1+2\rho )M(\mathrm{}))^2`$ $`=`$ $`𝐄\mathrm{Var}(M(\mathrm{}+1)|M(\mathrm{}))`$
$`=`$ $`2\rho 𝐄M(\mathrm{})=2\rho (1+2\rho )^{\mathrm{}},`$
implying that

$`𝐄(W_\rho W(\tau _r))^2`$ $``$ $`2\rho (1+2\rho )^2{\displaystyle \underset{\mathrm{}=\tau _r}{\overset{\mathrm{}}{}}}(1+2\rho )^{\mathrm{}}`$
$`=`$ $`(1+2\rho )^2(1+2\rho )^{\tau _r}.`$
Hence

$`𝐄|W_\rho W(\tau _r)|`$ $``$ $`(1+2\rho )^{1\frac{1}{2}(n_0+r)}`$
$``$ $`(L\rho )^{1/4}\varphi _0^{1/2}(1+2\rho )^{\frac{r}{2}},`$
and the theorem follows. $`[]`$

Theorem 3.8 can be translated into a uniform distributional approximation, as follows.

###### Theorem 3.9

If $`\mathrm{\Delta }`$ denotes a random variable on the integers with distribution given by

$$𝐏\left[\mathrm{\Delta }>x\right]=𝐄\{e^{2\varphi _0^2(1+2\rho )^xW_\rho W_{\rho }^{}{}_{}{}^{}}\},x𝐙,$$
(3.12)
and $`D^{}=\mathrm{\Delta }+2n_0`$, then

$`d_{TV}((D),(D^{}))`$
$`=`$ $`O\left(\mathrm{log}(L\rho )(1+2\rho )^{1/4}(L\rho )^{\frac{1}{7}}+\left({\displaystyle \frac{\rho \mathrm{log}(L\rho )}{\mathrm{log}(1+2\rho )}}\right)^2(1+2\rho )^{1/2}(L\rho )^{\frac{2}{7}}\right).`$
In particular, for $`\rho =\rho (L)=O(L^\beta )`$ with $`\beta <4/31`$,

$`d_{TV}((D),(D^{}))0\text{as}L\mathrm{}.`$
Proof: It is easy to see that $`\mathrm{\Delta }`$, defined as above, is indeed a random variable. Its upper tail is bounded by Lemma 3.7, which implies that

$$𝐏[\mathrm{\Delta }>x]\frac{1}{2\varphi _0^2}(1+2\rho )^x(2+x\mathrm{log}(1+2\rho ))$$
(3.13)
for any $`x>0`$, since $`\varphi _01`$ and $`\mathrm{log}(1+2y)2+\mathrm{log}y`$ in $`y1`$. Then, for any $`x𝐙`$, writing $`r(x)=x/2`$ and $`r^{}(x)=xr(x)(x+1)/2`$, it follows from Theorem 3.8 that

$`|𝐏[D>2n_0+x]𝐏[D^{}>2n_0+x]|`$
$`\{\eta _1(r(x),r^{}(x))+\eta _2(r(x),r^{}(x))\}(L\rho )^{1/2}+\eta _3(r(x),r^{}(x))(L\rho )^{1/4}`$
$`=O(\left({\displaystyle \frac{\rho \mathrm{log}(L\rho )}{\mathrm{log}(1+2\rho )}}\right)^2(1+2\rho )^{\frac{1}{2}}(L\rho )^{\frac{2}{7}}`$
$`+\left({\displaystyle \frac{\rho \mathrm{log}(L\rho )}{\mathrm{log}(1+2\rho )}}\right)(1+2\rho )^{\frac{1}{2}}(L\rho )^{\frac{3}{7}}+(1+2\rho )^{\frac{1}{4}}(L\rho )^{\frac{1}{7}}),`$
so long as $`x\frac{\frac{1}{7}\mathrm{log}(L\rho )2\mathrm{log}\varphi _0}{\mathrm{log}(1+2\rho )}`$. This is combined with (3.13) evaluated at $`x=\frac{\frac{1}{7}\mathrm{log}(L\rho )2\mathrm{log}\varphi _0}{\mathrm{log}(1+2\rho )}`$, which gives rise to a term of order $`O\left((L\rho )^{\frac{1}{7}}\mathrm{log}(L\rho )\right)`$, and the main estimate follows.

The above bound tends to zero as $`L\mathrm{}`$ as long as $`\rho =\rho (L)=O(L^\beta )`$ for $`\beta <4/31`$. Thus the theorem is proved. $`[]`$

For larger $`\rho `$ and for $`L`$ large, it is easy to check that $`n_0`$ can be no larger than $`4`$, so that interpoint distances are extremely short, few steps in each branching process are needed, and the closeness of $`(D)`$ and $`(D^{})`$ could be justified by direct arguments. Even in the range covered by Theorem 3.9, it is clear that $`(D)`$ becomes concentrated on very few values, once $`\rho `$ is large, since the factor $`2\varphi _0^2(1+2\rho )^x`$ in the exponent in (3.12) is multiplied by the large factor $`(1+2\rho )`$ if $`x`$ is increased by $`1`$. The following corollary makes this more precise.

###### Corollary 3.10

If $`N_0`$ is such that

$$(1+2\rho )^{N_0}L\rho <(1+2\rho )^{N_0+1},$$

and if $`L\rho =(1+2\rho )^{N_0+\alpha }`$, for some $`\alpha [0,1)`$, then, taking $`x_0=N_02n_0+1`$, we have

$$𝐏[\mathrm{\Delta }x_0]12(1+2\rho )^\alpha ,$$

and

$$𝐏[\mathrm{\Delta }x_0+1]=𝐄\mathrm{exp}\{2(1+2\rho )^{1\alpha }W_\rho W_\rho ^{}\}\frac{1}{2}(1+2\rho )^{1+\alpha }\mathrm{log}(3+4\rho ).$$

Proof: The result follows immediately from Jensen’s inequality;

$`𝐄\mathrm{exp}\{2(1+2\rho )^\alpha W_\rho W_\rho ^{}\}`$ $``$ $`\mathrm{exp}\left\{2(1+2\rho )^\alpha 𝐄W_\rho 𝐄W_\rho ^{}\right\}`$
$``$ $`12(1+2\rho )^\alpha `$
as $`𝐄W_\rho =1`$, and from Lemma 3.7 with $`\theta =2(1+2\rho )^{1\alpha }`$. $`[]`$

Thus the distribution is essentially concentrated on the single value $`x_0`$ if $`\rho `$ is large and $`\alpha `$ is bounded away from $`0`$ and $`1`$. If, for instance, $`\alpha `$ is close to $`1`$, then both $`x_0`$ and $`x_0+1`$ may carry appreciable probability.

If $`\rho \rho _0`$ as $`L\mathrm{}`$, then the distribution of $`\mathrm{\Delta }`$ becomes spread out over $`𝐙`$, converging to a non–trivial limit as $`L\mathrm{}`$ along any subsequence such that $`\varphi _0(L,\rho )`$ converges. Both this behaviour and that for larger $`\rho `$ are quite different from the behaviour found in the continuous model of . However, if $`\rho `$ becomes smaller, the differences become less; we now show that, as $`\rho 0`$, the distribution of $`\rho \mathrm{\Delta }`$ approaches the limiting distribution of $`T`$ obtained in .

The argument is based on showing that the distribution of $`W_\rho `$ is close to $`\mathrm{NE}(1)`$. To do so, we employ the characterizing Poincaré equation for Galton–Watson branching processes (see Harris , Theorem 8.2, p.15); if

$$\varphi _\rho (\theta )=𝐄e^{\theta W_\rho }$$

is the Laplace transform of $`(W_\rho )`$, then

$`\varphi _\rho ((1+2\rho )\theta )=f(\varphi _\rho (\theta )).`$ (3.14)
We show that when $`\rho 0`$ then $`\varphi _\rho (\theta )`$ is close to $`\varphi _e(\theta )=(1+\theta )^1`$, the Laplace transform of the $`\mathrm{NE}(1)`$ distribution.

Let

$$𝒢=\{g:[0,\mathrm{})𝐑:g_𝒢:=\underset{\theta >0}{sup}\theta ^2|g(\theta )|<\mathrm{}\},$$

and let

$$=\{\chi :[0,\mathrm{})𝐑:\chi (\theta )=1\theta +g(\theta )\text{ for some }g𝒢\}.$$

Then $``$ contains all Laplace transforms of probability distributions with mean $`1`$ and finite variance. On $``$, define the operator $`\mathrm{\Psi }`$ by

$$(\mathrm{\Psi }\chi )(\theta )=f\left(\chi \left(\frac{\theta }{m}\right)\right),$$

where

$$f(s)=se^{2\rho (s1)}$$

is the probability generating function of $`1+\mathrm{Po}(2\rho )`$, and $`m=1+2\rho >1`$. Thus the Laplace transform $`\varphi _\rho `$ of interest to us is a fixed point of $`\mathrm{\Psi }`$.

###### Lemma 3.11

The operator $`\mathrm{\Psi }`$ is a contraction, and, for all $`\chi ,\psi `$,

$`\mathrm{\Psi }\chi \mathrm{\Psi }\psi _𝒢`$ $``$ $`{\displaystyle \frac{1}{m}}\chi \psi _𝒢.`$
Proof: For all $`\chi ,\psi `$ and $`\theta >0`$, we have

$`\theta ^2|\mathrm{\Psi }\chi (\theta )\mathrm{\Psi }\psi (\theta )|`$ $`=`$ $`\theta ^2\left|f\left(\chi \left({\displaystyle \frac{\theta }{m}}\right)\right)f\left(\psi \left({\displaystyle \frac{\theta }{m}}\right)\right)\right|`$
$``$ $`f_{\mathrm{}}\theta ^2\left|\chi \left({\displaystyle \frac{\theta }{m}}\right)\psi \left({\displaystyle \frac{\theta }{m}}\right)\right|`$
$`=`$ $`\theta ^2m\left|\chi \left({\displaystyle \frac{\theta }{m}}\right)\psi \left({\displaystyle \frac{\theta }{m}}\right)\right|`$
$`=`$ $`m^1(\theta /m)^2\left|\chi \left({\displaystyle \frac{\theta }{m}}\right)\psi \left({\displaystyle \frac{\theta }{m}}\right)\right|`$
$``$ $`m^1\chi \psi _𝒢,`$
as required. $`[]`$

###### Lemma 3.12

For the Laplace transform $`\varphi _e`$, we have

$`\mathrm{\Psi }\varphi _e\varphi _e_𝒢{\displaystyle \frac{2\rho ^2}{(1+2\rho )^2}}.`$
Proof: For all $`\theta >0`$, we have

$`\left|{\displaystyle \frac{|\mathrm{\Psi }\varphi _e(\theta )\varphi _e(\theta )}{\theta ^2}}\right|`$ $`=`$ $`{\displaystyle \frac{1}{1+\theta }}{\displaystyle \frac{1}{\theta ^2}}\left|\left(1+{\displaystyle \frac{2\rho \theta }{m+\theta }}\right)e^{2\frac{\rho \theta }{m+\theta }}1\right|`$
$``$ $`{\displaystyle \frac{1}{2(1+\theta )\theta ^2}}\left({\displaystyle \frac{2\rho \theta }{m+\theta }}\right)^2,`$
using the inequality $`|(1+x)e^x1|\frac{x^2}{2}`$ for $`x>0`$. The lemma now follows because $`m+\theta >m=1+2\rho `$ and $`1+\theta >1`$. $`[]`$

Lemmas 3.11 and 3.12 together yield the following result.

###### Lemma 3.13

For any $`\rho >0`$,

$`\varphi _\rho \varphi _e_𝒢`$ $``$ $`{\displaystyle \frac{\rho }{1+2\rho }}.`$
Proof: With Lemmas 3.11 and 3.12, it follows that

$`\varphi _\rho \varphi _e_𝒢`$ $`=`$ $`\mathrm{\Psi }\varphi _\rho \varphi _e_𝒢`$
$``$ $`\mathrm{\Psi }\varphi _\rho \mathrm{\Psi }\varphi _e_𝒢+\mathrm{\Psi }\varphi _e\varphi _e_𝒢`$
$``$ $`{\displaystyle \frac{1}{m}}\varphi _\rho \varphi _e_𝒢+{\displaystyle \frac{2\rho ^2}{(1+2\rho )^2}}.`$
Note that indeed $`\varphi _\rho \varphi _e𝒢`$. Thus, since $`m>1`$, it follows that

$`\varphi _\rho \varphi _e_𝒢`$ $``$ $`{\displaystyle \frac{m}{m1}}{\displaystyle \frac{2\rho ^2}{(1+2\rho )^2}}={\displaystyle \frac{\rho }{1+2\rho }},`$
as required. $`[]`$

As an immediate consequence, $`(W_\rho )\mathrm{NE}(1)`$ as $`\rho 0`$. Theorem 3.14 reformulates this convergence as a pointwise comparison theorem directly relevant to the distribution functions of $`\mathrm{\Delta }`$ and $`T`$.

###### Theorem 3.14

Let $`W,W^{}`$ be independent $`\mathrm{NE}(1)`$ random variables. Then, for all $`\theta >0`$, we have

$`\left|𝐄e^{\theta W_\rho W_{\rho }^{}{}_{}{}^{}}𝐄e^{\theta WW^{}}\right|`$ $``$ $`{\displaystyle \frac{4\rho }{1+\rho }}\theta ^2.`$
Proof: We have

$`𝐄e^{\theta W_\rho W_{\rho }^{}{}_{}{}^{}}𝐄e^{\theta WW^{}}`$
$`=`$ $`𝐄\{𝐄(e^{\theta W_\rho W_\rho ^{}}|W_\rho ^{})\}𝐄\{𝐄(e^{\theta WW^{}}|W^{})\}`$
$`=`$ $`𝐄\varphi _\rho (\theta W_\rho ^{})𝐄\varphi _e(\theta W)`$
$`=`$ $`𝐄\mathrm{\Psi }\varphi _\rho (\theta W_\rho ^{})𝐄\mathrm{\Psi }\varphi _e(\theta W_\rho ^{})+𝐄\mathrm{\Psi }\varphi _e(\theta W_\rho ^{})𝐄\varphi _e(\theta W_\rho ^{})`$
$`+𝐄\varphi _e(\theta W_\rho ^{})𝐄\varphi _e(\theta W).`$
Since

$`𝐄\varphi _e(\theta W_\rho ^{})`$ $`=`$ $`𝐄e^{\theta WW_\rho ^{}}=𝐄\varphi _\rho (\theta W),`$
we obtain from the triangle inequality, (3.3) and Lemmas 3.11, 3.12 and 3.13 that

$`\left|𝐄e^{\theta W_\rho W_\rho ^{}}𝐄e^{\theta WW^{}}\right|`$ $``$ $`{\displaystyle \frac{1}{m}}\varphi _\rho \varphi _e_𝒢\theta ^2𝐄(W_\rho ^2)+{\displaystyle \frac{2\rho ^2}{(1+2\rho )^2}}\theta ^2𝐄(W_\rho ^2)`$
$`+\varphi _\rho \varphi _e_𝒢\theta ^2𝐄(W_\rho ^2)`$
$``$ $`{\displaystyle \frac{2\theta ^2(1+\rho )}{1+2\rho }}\left\{\left({\displaystyle \frac{1}{1+2\rho }}+1\right){\displaystyle \frac{\rho }{1+2\rho }}+{\displaystyle \frac{2\rho ^2}{(1+2\rho )^2}}\right\}`$
$``$ $`{\displaystyle \frac{4\rho }{1+2\rho }}\theta ^2,`$
as required. $`[]`$

Noting that

$$𝐄e^{\theta WW^{}}=_0^{\mathrm{}}\frac{e^y}{1+\theta y}𝑑y,$$

we obtain the following theorem.

###### Theorem 3.15

As in Theorem 3.9, let $`\mathrm{\Delta }`$ be a random variable on $`𝐙`$ with distribution given by

$$𝐏\left[\mathrm{\Delta }>x\right]=𝐄\{e^{2\varphi _0^2(1+2\rho )^xW_\rho W_{\rho }^{}{}_{}{}^{}}\}.$$

Let $`T`$ denote a random variable on $`𝐑`$ with distribution given by

$`𝐏\left[T>z\right]={\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{e^y}{1+2ye^{2z}}}𝑑y.`$
Then

$$\underset{z𝐑}{sup}|𝐏[\rho \mathrm{\Delta }>z]𝐏[T>z]|=O\left(\rho ^{1/3}(1+\mathrm{log}(1/\rho ))\right).$$

Proof: We use an argument similar to that used for Theorem 3.9. For $`a`$ large, we can use the bound

$$_0^{\mathrm{}}\frac{e^ydy}{1+ay}_0^1\frac{dy}{1+ay}=a^1\mathrm{log}(1+a),$$
(3.15)
from which, for $`z>0`$ and with $`c(\rho )`$ defined by

$$1c(\rho ):=(2\rho )^1\mathrm{log}(1+2\rho )1\rho ,$$

we have

$`𝐏[T>zc(\rho )]`$ $``$ $`e^{2zc(\rho )}(1+zc(\rho ))(1+zc(\rho ))e^{2z(1\rho )}.`$ (3.16)
Similarly, from Lemma 3.7, we have

$`𝐏[\rho \mathrm{\Delta }>z]`$ $``$ $`(1+2\rho )^{(z/\rho )+2}(1+zc(\rho ))(1+2\rho )^2(1+zc(\rho ))e^{2z(1\rho )}.`$
Complementing these upper tail bounds, from Theorem 3.14 and for $`z\rho 𝐙`$, we have

$$\left|𝐏[\rho \mathrm{\Delta }>z]_0^{\mathrm{}}\frac{e^y}{1+2y\varphi _0^2(1+2\rho )^{z/\rho }}𝑑y\right|\frac{16\rho }{1+2\rho }(1+2\rho )^{2z/\rho }\frac{16\rho }{1+2\rho }e^{4z}.$$
(3.17)
Using the facts that $`(1+2\rho )^{z/\rho }=e^{2zc(\rho )}`$ and that $`(1+2\rho )^1\varphi _01`$, and because, for $`a,b>0`$,

$$\left|_0^{\mathrm{}}\frac{e^y}{1+ay}𝑑y_0^{\mathrm{}}\frac{e^y}{1+by}𝑑y\right|\frac{|ba|}{\mathrm{max}\{1,a,b\}},$$
(3.18)
it also follows that

$`\left|{\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{e^y}{1+2y\varphi _0^2(1+2\rho )^{z/\rho }}}𝑑y𝐏[T_0>zc(\rho )]\right|`$
$`2|\varphi _0^21|(1+2\rho )^{z/\rho }{\displaystyle \frac{8\rho }{1+2\rho }}e^{2z};`$ (3.19)
and then, from (3.18) and (3.15), we have

$$|𝐏[T>zc(\rho )]𝐏[T>z]|\mathrm{min}\{4z(1c(\rho )),(2+z)e^z\}=O(\rho \mathrm{log}(1/\rho )).$$
(3.20)
Combining the bounds (3.17), (3) and (3.20) for $`e^{2z}\rho ^{1/3}`$ gives a supremum of order $`\rho ^{1/3}`$ for $`|𝐏[\rho \mathrm{\Delta }>z]𝐏[T>z]|`$; note that $`z`$ may actually be allowed to take any real value in this range, since $`T`$ has bounded density. For any larger values of $`z`$, the upper tail bounds give a maximum discrepancy of order $`O\{\rho ^{1/3}(1+\mathrm{log}(1/\rho ))\}`$, as required. Note that, in the main part of the distribution, for $`z`$ of order $`1`$, the discrepancy is actually of order $`\rho `$. $`[]`$

Numerically, instead of calculating the limiting distribution of $`W_\rho `$, we would use the approximation

$`\left|𝐄\left\{e^{L^1(N_r^{}s_r+M_ru_r^{})}\right\}𝐄\left\{e^{2\varphi _0^2(1+2\rho )^{r+r^{}}W(\tau _r)W^{}(\tau _r^{})}\right\}\right|`$
$`6\varphi _0^{3/2}(1+\rho )(1+2\rho )^{r+r^{}\frac{1}{2}(rr^{})}(L\rho )^{1/4},`$
from (3.8) and (3.11), where the distributions of $`W(\tau _r)`$ and $`W^{}(\tau _r^{})`$ can be calculated iteratively, using the generating function from Lemma 3.4. As $`D`$ is centred around $`2n_0=2\frac{N}{2}`$, and as $`r`$ is of order at most $`\frac{\mathrm{log}(L\rho )}{\mathrm{log}(1+2\rho )}`$, only order $`\frac{\mathrm{log}(L\rho )}{\mathrm{log}(1+2\rho )}`$ iterations would be needed.

## 4 The discrete circle model: description

Now suppose, as in the discrete circle model of Newman et al. , that the circle $`C`$ becomes a ring lattice with $`\mathrm{\Lambda }=Lk`$ vertices, where each vertex is connected to all its neighbours within distance $`k`$ by an undirected edge. In the notation of , a number of shortcuts are added between randomly chosen pairs of sites, with probability $`\varphi `$ per connection in the lattice, of which there are $`\mathrm{\Lambda }k`$; thus, on average, there are $`\mathrm{\Lambda }k\varphi `$ shortcuts in the graph. In contrast to the previous setting, it is natural in the discrete model to use graph distance, which implies that all edges, including shortcuts, have length 1. This turns out to make a significant difference to the results when shortcuts are very plentiful.

For ease of comparison with the previous model, which collapsed the $`k`$-neighbourhoods, we adopt a different notation. The model can be formulated as the union of a Bernoulli random graph $`G_{\mathrm{\Lambda },\frac{\sigma }{\mathrm{\Lambda }}}`$ and the underlying ring lattice on $`\mathrm{\Lambda }`$ vertices. Here we write $`\sigma =\frac{\rho }{k}`$, so that the expected number of edges in $`G_{\mathrm{\Lambda },\frac{\sigma }{\mathrm{\Lambda }}}`$ is close to the value $`L\rho /2`$ in the previous model; comparing the expected number of shortcuts with that given in , we also have

$$\mathrm{\Lambda }k\varphi =\frac{1}{2}\mathrm{\Lambda }(\mathrm{\Lambda }2k1)\frac{\sigma }{\mathrm{\Lambda }}=\frac{\rho }{2k}(\mathrm{\Lambda }2k1)\frac{1}{2}L\rho ,$$

relating our parameter $`\sigma `$ to those of . In particular, we have

$`\sigma ={\displaystyle \frac{2\mathrm{\Lambda }k\varphi }{\mathrm{\Lambda }2k1}}2k\varphi .`$ (4.1)
The model can also be realized by a dynamic construction. Choosing a point $`P_0\{1,\mathrm{},\mathrm{\Lambda }\}`$ at random, set $`R(0)=\{P_0\}`$. Then, at the first step (distance 1), the ‘island’ consisting of $`P_0`$ is increased by $`k`$ points at each end, and, in addition, $`M_1^{(1)}\mathrm{Bi}(\mathrm{\Lambda }2k1,\frac{\sigma }{\mathrm{\Lambda }})`$ shortcuts connect to centres of new islands. At each subsequent step, starting from the set $`R(n)`$ of vertices within distance $`n`$ of $`P_0`$, each island is increased by the addition of $`k`$ points at either end, but with overlapping islands merged, to form a set $`R^{}(n+1)`$; this is then increased to $`R(n+1)`$ by choosing a Bernoulli–$`\frac{\sigma }{\mathrm{\Lambda }}`$ thinning of the edges joining $`R(n)R(n1)`$ to $`CR^{}(n+1)`$ as shortcuts.

The branching analogue of this process, which agrees with the current process until its first self–overlap occurs, has individuals, here representing the islands, of two types: newly formed type 1 islands, consisting of just one vertex, and existing type 2 islands. A type 1 island at time $`n`$ becomes a type 2 island at time $`n+1`$, and, in addition, has a $`\mathrm{Bi}(\mathrm{\Lambda },\frac{\sigma }{\mathrm{\Lambda }})`$–distributed number of type 1 islands as ‘offspring’. A type 2 island at time $`n`$ stays a type 2 island at time $`n+1`$, and has a $`\mathrm{Bi}(2k\mathrm{\Lambda },\frac{\sigma }{\mathrm{\Lambda }})`$–distributed number of type 1 islands as offspring. Each new island starts at an independent and randomly chosen point of the circle, and at each subsequent step acquires $`k`$ more vertices at either end. Writing

$$\widehat{M}(n):=(\widehat{M}^{(1)}(n),\widehat{M}^{(2)}(n))^T,n0,$$

for the numbers of islands of the two types at time $`n`$, where the superscript $`T`$ denotes the transpose, their development over time is given by the branching recursion

$`\widehat{M}^{(1)}(n)`$ $``$ $`\mathrm{Bi}((\widehat{M}^{(1)}(n1)+2k\widehat{M}^{(2)}(n1))\mathrm{\Lambda },{\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}),`$
$`\widehat{M}^{(2)}(n)`$ $`=`$ $`\widehat{M}^{(1)}(n1)+\widehat{M}^{(2)}(n1):`$
$`\widehat{M}^{(1)}(0)`$ $`=`$ $`1,\widehat{M}^{(2)}(0)=0.`$ (4.2)
The total number of intervals at time $`n`$ is denoted by

$`\widehat{M}^+(n)=\widehat{M}^{(1)}(n)+\widehat{M}^{(2)}(n),`$ (4.3)
and the total number of vertices in these intervals by

$`\widehat{s}(n)=\widehat{M}^+(n)+2k{\displaystyle \underset{j=0}{\overset{n1}{}}}\widehat{M}^+(j)\widehat{M}^+(n).`$ (4.4)
As before, we use the branching process as the basic tool in our argument. It is now a two type Galton–Watson process with mean matrix

$`A=\left(\begin{array}{cc}\sigma & 2k\sigma \\ 1& 1\end{array}\right).`$
The characteristic equation

$`(t1)(t\sigma )=2k\sigma `$ (4.6)
of $`A`$ yields the eigenvalues

$`\lambda =\lambda _1`$ $`=`$ $`\frac{1}{2}\{\sigma +1+\sqrt{(\sigma +1)^2+4\sigma (2k1)}\}>\sigma +1;`$
$`\lambda <\lambda _2`$ $`=`$ $`\frac{1}{2}\{\sigma +1\sqrt{(\sigma +1)^2+4\sigma (2k1)}\}<0:`$
also, from (4.6),

$`\lambda +\lambda _2=\sigma +1\text{and}\lambda \lambda _2=\sigma (2k1).`$ (4.7)
From the equation $`fA=\lambda f`$, we find that the left eigenvectors $`f^{(i)}`$, $`i=1,2`$, satisfy

$`f_2^{(i)}=(\lambda _i\sigma )f_1^{(i)}.`$ (4.8)
We standardize the positive left eigenvector $`f^{(1)}`$ of $`A`$, associated with the eigenvalue $`\lambda `$, so that

$`f_1^{(1)}`$ $`=`$ $`(\lambda \sigma )^{\frac{1}{2}},f_2^{(1)}=(\lambda \sigma )^{\frac{1}{2}};`$ (4.9)
for $`f^{(2)}`$, we choose

$`f_1^{(2)}=(\sigma \lambda _2)^{\frac{1}{2}},f_2^{(2)}=(\sigma \lambda _2)^{\frac{1}{2}}.`$
Then, for $`i=1,2`$, we have

$`𝐄((f^{(i)})^T\widehat{M}_{n+1}|(n))`$ $`=`$ $`(f^{(i)})^TA\widehat{M}(n)=\lambda _i(f^{(i)})^T\widehat{M}(n),`$
where $`(n)`$ denotes the $`\sigma `$-algebra $`\sigma (\widehat{M}(0),\mathrm{},\widehat{M}(n))`$. Thus, from (4.8),

$`W^{(i)}(n)`$ $`:=`$ $`\lambda _i^n(f^{(i)})^T\widehat{M}(n)`$
$`=`$ $`\lambda _i^nf_1^{(i)}(\widehat{M}_n^{(1)}+(\lambda _i\sigma )\widehat{M}_n^{(2)})`$
is a (non-zero mean) martingale, for $`i=1,2`$; we let

$`W_{k,\sigma }:=\underset{n\mathrm{}}{lim}W^{(1)}(n)\text{ a.s.}=\underset{n\mathrm{}}{lim}\lambda _1^n(f^{(1)})^T\widehat{M}(n)\text{ a.s.}`$ (4.11)
be the almost sure limit of the martingale $`W^{(1)}(n)`$.

Our main conclusions can be summarized as follows: the detailed results and their proofs are given in Theorems 5.6 and 5.9. Let $`\mathrm{\Delta }_d`$ denote a random variable on the integers with distribution given by

$`𝐏\left[\mathrm{\Delta }_d>x\right]=𝐄\mathrm{exp}\left\{\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\varphi _d^2\lambda ^xW_{k,\sigma }W_{k,\sigma }^{}\right\},`$ (4.12)
for any $`x𝐙`$, and set $`D^{}=\mathrm{\Delta }_d+2n_d`$. Here, $`n_d`$ and $`\varphi _d`$ are such that $`\lambda ^{n_d}=\varphi _d(\mathrm{\Lambda }\sigma )^{1/2}`$ and $`\lambda ^1<\varphi _d1`$. Let $`D`$ denote the graph distance between a randomly chosen pair of vertices on the ring lattice $`C`$.

###### Theorem 4.1

If $`\mathrm{\Lambda }\sigma \mathrm{}`$ and $`\rho =k\sigma `$ remains bounded, then it follows that $`d_{TV}((D),(D^{}))0`$. If $`\rho 0`$, then $`\rho \mathrm{\Delta }_d_𝒟T`$, where $`T`$ is as in Theorem 2.1.

Note that the expectation in (4.12) is taken under the initial condition (4.2); we shall later need also to consider the distribution of $`W_{k,\sigma }`$ under other initial conditions.

## 5 The discrete circle model: proofs

We begin the detailed discussion with some moment formulae.

###### Lemma 5.1

For the means,

$`𝐄\widehat{M}^{(1)}(n)`$ $`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}(\lambda ^n(\sigma \lambda _2)+\lambda _2^n(\lambda \sigma ));`$
$`𝐄\widehat{M}^{(2)}(n)`$ $`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}(\lambda ^n\lambda _2^n);`$
$`𝐄\widehat{M}^+(n)`$ $`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}(\lambda ^{n+1}\lambda _2^{n+1})2\lambda ^n,`$ (5.1)
and

$`𝐄(\widehat{M}_n^{(1)}+2k\widehat{M}_n^{(2)})`$ $`=`$ $`{\displaystyle \frac{1}{(\lambda \lambda _2)}}\{(1\lambda _2/\sigma )\lambda ^{n+1}+(\lambda _2/\sigma )(\lambda \sigma )\lambda _2^n\}`$ (5.2)
$``$ $`c\lambda ^n,\text{ for }c=4k1.`$
For the variances, for $`jn`$,

$`\mathrm{Var}(W^{(1)}(j)W^{(1)}(n))\kappa ^2(f_1^{(1)})^2\lambda ^j,\kappa ^2:={\displaystyle \frac{c\sigma }{\lambda (\lambda 1)}};`$ (5.3)
$`\mathrm{Var}(W^{(2)}(j)W^{(2)}(n))`$ (5.4)
$`c\sigma \left({\displaystyle \frac{f_1^{(2)}}{\lambda _2}}\right)^2\mathrm{min}\{{\displaystyle \frac{\lambda _2^2}{|\lambda \lambda _2^2|}},(nj)\}\left({\displaystyle \frac{\lambda }{\lambda _2^2}}\right)^j\mathrm{max}\{1,{\displaystyle \frac{\lambda }{\lambda _2^2}}\}^{nj}`$
and, for $`\widehat{M}^+(n)`$,

$`\mathrm{Var}\widehat{M}^+(n)`$ $``$ $`4\kappa ^2\lambda ^{2n};`$ (5.5)
$`𝐄\widehat{M}^+(n)(\widehat{M}^+(n)1)`$ $``$ $`4(1+\kappa ^2)\lambda ^{2n}.`$ (5.6)
Note that, from (4.6), we have

$`0\kappa ^2={\displaystyle \frac{c}{2k+\lambda 1}}{\displaystyle \frac{4k1}{2k}}2.`$ (5.7)
Proof: First, observe that

$$𝐄W^{(i)}(n)=W_0^{(i)}=(f^{(i)})^T\widehat{M}_0^+=(f^{(i)})^T(1,0)^T=f_1^{(i)}$$
(5.8)
for all $`n`$, by the martingale property. From (4) and (4.8), we have

$`(f_1^{(1)})^1\lambda ^nW^{(1)}(n)`$ $`=`$ $`\widehat{M}^{(1)}(n)+(\lambda \sigma )\widehat{M}^{(2)}(n);`$
$`(f_1^{(2)})^1\lambda _2^nW^{(2)}(n)`$ $`=`$ $`\widehat{M}^{(1)}(n)+(\lambda _2\sigma )\widehat{M}^{(2)}(n),`$
and thus

$`\widehat{M}^{(1)}(n)`$ $`=`$ $`\lambda ^nW^{(1)}(n){\displaystyle \frac{\sigma \lambda _2}{(\lambda \lambda _2)f_1^{(1)}}}+\lambda _2^nW^{(2)}(n){\displaystyle \frac{\lambda \sigma }{(\lambda \lambda _2)f_1^{(2)}}};`$ (5.9)
$`\widehat{M}^{(2)}(n)`$ $`=`$ $`\lambda ^nW^{(1)}(n){\displaystyle \frac{1}{(\lambda \lambda _2)f_1^{(1)}}}\lambda _2^nW^{(2)}(n){\displaystyle \frac{1}{(\lambda \lambda _2)f_1^{(2)}}}.`$
From (5.9) and (5.8) we obtain

$`𝐄\widehat{M}^{(1)}(n)`$ $`=`$ $`\lambda ^n{\displaystyle \frac{\sigma \lambda _2}{(\lambda \lambda _2)}}+\lambda _2^n{\displaystyle \frac{\lambda \sigma }{(\lambda \lambda _2)}};`$
$`𝐄\widehat{M}^{(2)}(n)`$ $`=`$ $`\lambda ^n{\displaystyle \frac{1}{(\lambda \lambda _2)}}\lambda _2^n{\displaystyle \frac{1}{(\lambda \lambda _2)}},`$
giving (5.1); for the last part use $`\sigma +1\lambda =\lambda _2`$ and $`\sigma +1\lambda _2=\lambda `$, from (4.7). Then (5.2) follows immediately, using (4.6) and (4.7).

Now define

$`X(n):=\widehat{M}^{(1)}(n)\sigma (\widehat{M}^{(1)}(n1)+2k\widehat{M}^{(2)}(n1)),n1,`$ (5.10)
noting that it has a centred binomial distribution conditional on $`(n1)`$; representing quantities in terms of these martingale differences greatly simplifies the subsequent calculations. For instance,

$`W^{(i)}(n+1)W^{(i)}(n)`$
$`=\lambda _i^{n1}f_1^{(i)}\{\widehat{M}^{(1)}(n+1)+(\lambda _i\sigma )\widehat{M}^{(2)}(n+1)`$
$`\lambda _i\widehat{M}^{(1)}(n)\lambda _i(\lambda _i\sigma )\widehat{M}^{(2)}(n)\}`$
$`=\lambda _i^{n1}f_1^{(i)}\{\widehat{M}^{(1)}(n+1)\sigma \widehat{M}^{(1)}(n)2k\sigma \widehat{M}^{(2)}(n)\}`$
$`=\lambda _i^{n1}f_1^{(i)}X(n+1),`$ (5.11)
where we have used $`(\lambda _i1)(\lambda _i\sigma )=2k\sigma `$, from (4.6), and the branching recursion.

Since

$$𝐄\{X^2(n+1)|(n)\}=\frac{\sigma }{\mathrm{\Lambda }}\left(1\frac{\sigma }{\mathrm{\Lambda }}\right)(\widehat{M}^{(1)}(n)+2k\widehat{M}^{(2)}(n))\mathrm{\Lambda },$$

we have

$$𝐄X^2(n+1)c\sigma \lambda ^n,$$

from (5.2). Thus, immediately,

$$𝐄\{(W^{(i)}(n+1)W^{(i)}(n))^2\}c\sigma (f_1^{(i)})^2\lambda _i^{2n2}\lambda ^n.$$
(5.12)
Hence, for $`i=1,2`$ and for any $`0j<n`$,

$`\mathrm{Var}(W^{(i)}(j)W^{(i)}(n))`$
$`={\displaystyle \underset{k=j}{\overset{n1}{}}}𝐄(W^{(i)}(k)W^{(i)}(k+1))^2`$
$`c\sigma (f_1^{(i)})^2{\displaystyle \underset{k=j}{\overset{n1}{}}}\lambda ^k\lambda _i^{2(k+1)}`$
$`c\sigma (f_1^{(i)})^2\lambda _i^2\left({\displaystyle \frac{\lambda }{\lambda _i^2}}\right)^j\mathrm{min}\{{\displaystyle \frac{\lambda _i^2}{|\lambda \lambda _i^2|}},(nj)\}\mathrm{max}(1,\left({\displaystyle \frac{\lambda }{\lambda _i^2}}\right)^{nj}),`$
and the formulae (5.3) and (5.4) follow.

Moreover, from (5.9),

$`\widehat{M}^+(n)={\displaystyle \frac{1}{\lambda \lambda _2}}\left({\displaystyle \frac{\lambda ^{n+1}}{f_1^{(1)}}}W^{(1)}(n){\displaystyle \frac{\lambda _2^{n+1}}{f_1^{(2)}}}W^{(2)}(n)\right),`$ (5.13)
and hence

$`(\lambda \lambda _2)^2\mathrm{Var}\widehat{M}^+(n)`$ $`=`$ $`{\displaystyle \underset{j=1}{\overset{n}{}}}(\lambda ^{n+1j}\lambda _2^{n+1j})^2\mathrm{Var}X(j)`$
$``$ $`4c\sigma {\displaystyle \underset{j=1}{\overset{n}{}}}\lambda ^{2n(j1)}4c\sigma \lambda ^{2n+1}/(\lambda 1).`$
From this, using the inequality

$`𝐄\widehat{M}^+(n)(\widehat{M}^+(n)1)`$ $``$ $`\mathrm{Var}(\widehat{M}^+(n))+(𝐄\widehat{M}^+(n))^2,`$
(5.6) is easily obtained. $`[]`$

As in the previous section, we run two branching processes $`\widehat{M}`$ and $`\widehat{M}^{}=:\widehat{N}`$ independently, and investigate the time at which the first intersection occurs, irrespective of the types of the intervals. We write $`\widehat{s}^{}(n)=:\widehat{u}(n)`$, and use notation of the form $`\widehat{M}_r`$ to denote $`\widehat{M}(n_d+r)`$, for an appropriate $`n_d`$ which we shall define later; we also use $`\tau _r:=\{2k(n_d+r)+1\}`$ to denote the length of the longest interval in the branching process at time $`n_d+r`$. Then, with $`\widehat{V}_{r,r^{}}`$ defined as before to be the number of pairs of intervals of $`\widehat{M}`$ and $`\widehat{N}`$ intersecting, when $`\widehat{M}`$ has been run for time $`n_d+r`$ and $`\widehat{N}`$ for time $`n_d+r^{}`$, the analogue of Proposition 3.3 shows that

$`|𝐏[\widehat{V}_{r,r^{}}=0]𝐏[D>2n_d+r+r^{}]|`$
$`32\mathrm{\Lambda }^2\tau _{(rr^{})}^2𝐄\{\frac{1}{2}\widehat{M}_r^+\widehat{N}_r^{}^+(\widehat{M}_r^++\widehat{N}_r^{}^+2)\},`$ (5.14)
and that of Corollary 3.2 gives

$`|𝐏[\widehat{V}_{r,r^{}}=0|\widehat{M}_r^+=M,\widehat{N}_r^{}^+=N,\widehat{s}_r=t,\widehat{u}_r^{}=u]`$
$`\mathrm{exp}\{\mathrm{\Lambda }^1(Nt+MuMN)\}|`$
$`8\mathrm{\Lambda }^1(M+N)\tau _{(rr^{})}.`$ (5.15)
The estimates (5.14) and (5.15) can be made more explicit with the help of the bounds

$$𝐄\widehat{M}_r^+2\lambda ^{n_d+r};𝐄\widehat{M}_r^+(\widehat{M}_r^+1)4(1+\kappa ^2)\lambda ^{2(n_d+r)},$$
(5.16)
which follow from from Lemma 5.1; together, they give the following result, in which $`D`$ denotes the shortest distance between $`P_0`$ and a randomly chosen vertex $`P^{}`$ of $`C`$.

###### Lemma 5.2

With the above notation and definitions, we have

$`|𝐏[D>2n_d+r+r^{}]𝐏[\widehat{V}_{r,r^{}}=0]|`$
$`256\mathrm{\Lambda }^2\tau _{(rr^{})}^2(1+\kappa ^2)\lambda ^{3n_d+r+r^{}+(rr^{})},`$
and

$`|𝐏[\widehat{V}_{r,r^{}}=0|\widehat{M}_r^+=M,\widehat{N}_r^{}^+=N,\widehat{s}_r=t,\widehat{u}_r^{}=u]`$
$`\mathrm{exp}\{\mathrm{\Lambda }^1(Nt+MuMN)\}|`$
$`32\mathrm{\Lambda }^1\tau _{(rr^{})}\lambda ^{n_d+(rr^{})}.`$
We now need to examine $`𝐄\mathrm{exp}\{\mathrm{\Lambda }^1(\widehat{N}_r^{}^+\widehat{s}_r+\widehat{M}_r^+\widehat{u}_r^{}\widehat{M}_r^+\widehat{N}_r^{}^+)\}`$ more closely.

To start with, from (5.1) in Lemma 5.1, we have

$`𝐄\widehat{s}(n)`$ $`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}\left\{(\lambda ^{n+1}\lambda _2^{n+1})+2k{\displaystyle \underset{j=0}{\overset{n1}{}}}(\lambda ^{j+1}\lambda _2^{j+1})\right\}`$ (5.17)
$`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}\{\lambda ^{n+1}(1+{\displaystyle \frac{2k}{\lambda 1}})\lambda _2^{n+1}(1+{\displaystyle \frac{2k}{\lambda _21}})`$
$`2k({\displaystyle \frac{\lambda }{\lambda 1}}{\displaystyle \frac{\lambda _2}{\lambda _21}})\}`$
$`=`$ $`{\displaystyle \frac{1}{\sigma (\lambda \lambda _2)}}\left\{\lambda ^{n+2}\lambda _2^{n+2}(\lambda \lambda _2)\right\},`$
where we have used (4.6) and (4.7) to simplify, and this expression is rather close to $`(\lambda /\sigma )𝐄\widehat{M}^+(n)`$ as given in (5.1). This reflects the fact that both $`\widehat{s}(n)`$ and $`(\lambda /\sigma )\widehat{M}^+(n)`$ are rather close to

$$\frac{\lambda ^{n+2}}{\sigma (\lambda \lambda _2)}\frac{W^{(1)}(n1)}{f_1^{(1)}}.$$

###### Lemma 5.3

We have the following approximations:

$`\widehat{s}(n)`$ $`=`$ $`{\displaystyle \frac{\lambda ^{2+n}}{\sigma (\lambda \lambda _2)}}\left({\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}+\stackrel{~}{U}_1(n)\right);`$
$`{\displaystyle \frac{\lambda }{\sigma }}\widehat{M}^+(n)`$ $`=`$ $`{\displaystyle \frac{\lambda ^{2+n}}{\sigma (\lambda \lambda _2)}}\left({\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}+\stackrel{~}{U}_2(n)\right),`$
where

$`𝐄|\stackrel{~}{U}_1(n)|`$ $``$ $`\{3+2\kappa \sqrt{n+\sigma ^2}\}\mathrm{max}\{\lambda ^{1/2},{\displaystyle \frac{|\lambda _2|}{\lambda }}\}^n;`$ (5.18)
$`𝐄|\stackrel{~}{U}_2(n)|`$ $``$ $`\{1+2\kappa \sqrt{n+\lambda 1}\}\mathrm{max}\{\lambda ^{1/2},{\displaystyle \frac{|\lambda _2|}{\lambda }}\}^n.`$ (5.19)
Proof: We first express $`\widehat{s}(n)`$ and $`(\lambda /\sigma )\widehat{M}^+(n)`$ in terms of the martingale differences $`\{X(l),l1\}`$. From (5.13) and (5), we have

$`\widehat{M}^+(n)`$ $`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}\left\{{\displaystyle \frac{\lambda ^{n+1}}{f_1^{(1)}}}W^{(1)}(n){\displaystyle \frac{\lambda _2^{n+1}}{f_1^{(2)}}}W^{(2)}(n)\right\}`$
$`=`$ $`{\displaystyle \frac{\lambda ^{n+1}}{(\lambda \lambda _2)f_1^{(1)}}}W^{(1)}(n1)+X(n){\displaystyle \frac{\lambda _2^{n+1}}{\lambda \lambda _2}}\left(1+{\displaystyle \underset{l=1}{\overset{n1}{}}}\lambda _2^lX(l)\right).`$
Similarly, from (5.13) and (5),

$`{\displaystyle \underset{j=0}{\overset{n1}{}}}\widehat{M}^+(j)`$
$`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}{\displaystyle \underset{j=0}{\overset{n1}{}}}\left\{{\displaystyle \frac{\lambda ^{j+1}}{f_1^{(1)}}}W^{(1)}(j){\displaystyle \frac{\lambda _2^{j+1}}{f_1^{(2)}}}W^{(2)}(j)\right\}`$
$`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}{\displaystyle \underset{j=0}{\overset{n1}{}}}\{{\displaystyle \frac{\lambda ^{j+1}}{f_1^{(1)}}}W^{(1)}(n1)\lambda ^{j+1}{\displaystyle \underset{l=j+1}{\overset{n1}{}}}\lambda ^lX(l)`$
$`\lambda _2^{j+1}(1+{\displaystyle \underset{l=1}{\overset{j}{}}}\lambda _2^lX(l))\}`$
$`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}\{{\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}{\displaystyle \frac{\lambda ^{n+1}}{\lambda 1}}{\displaystyle \frac{\lambda }{\lambda 1}}(1+{\displaystyle \underset{j=1}{\overset{n1}{}}}\lambda ^jX(j))`$
$`{\displaystyle \underset{l=1}{\overset{n1}{}}}\lambda ^lX(l){\displaystyle \underset{j=0}{\overset{l1}{}}}\lambda ^{j+1}{\displaystyle \frac{\lambda _2^{n+1}\lambda _2}{\lambda _21}}{\displaystyle \underset{l=1}{\overset{n1}{}}}\lambda _2^lX(l){\displaystyle \underset{j=l+1}{\overset{n}{}}}\lambda _2^j\}`$
$`=`$ $`{\displaystyle \frac{1}{\lambda \lambda _2}}\{{\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}{\displaystyle \frac{\lambda ^{n+1}}{\lambda 1}}({\displaystyle \frac{\lambda }{\lambda 1}}{\displaystyle \frac{\lambda _2}{\lambda _21}})(1+{\displaystyle \underset{l=1}{\overset{n1}{}}}X(l))`$
$`{\displaystyle \frac{\lambda _2^{n+1}}{\lambda _21}}(1+{\displaystyle \underset{l=1}{\overset{n1}{}}}\lambda _2^lX(l))\}.`$
Substituting these into (4.4), and because $`1+2k/(\lambda _i1)=\lambda _i/\sigma `$, $`i=1,2`$, from (4.6) and (4.7), we obtain

$`\widehat{s}(n)`$ $`=`$ $`{\displaystyle \frac{\lambda ^{2+n}}{\sigma (\lambda \lambda _2)}}{\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}+X(n)`$
$`{\displaystyle \frac{1}{\sigma }}\left\{{\displaystyle \underset{l=1}{\overset{n1}{}}}X(l)\left(1+{\displaystyle \frac{\lambda _2^{n+2l}}{\lambda \lambda _2}}\right)+1+{\displaystyle \frac{\lambda _2^{n+2}}{\lambda \lambda _2}}\right\}`$
$`=`$ $`{\displaystyle \frac{\lambda ^{2+n}}{\sigma (\lambda \lambda _2)}}\left({\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}+\stackrel{~}{U}_1(n)\right),`$
where

$$|𝐄\stackrel{~}{U}_1(n)|=\lambda ^{n2}|\lambda \lambda _2+\lambda _2^{n+2}|3\mathrm{max}\{\lambda ^1,\frac{|\lambda _2|}{\lambda }\}^{n+1}$$

and

$`\mathrm{Var}\stackrel{~}{U}_1(n)`$ $``$ $`\lambda ^{2n4}c\sigma (\lambda \lambda _2)^2\left\{\sigma ^2\lambda ^{n1}+{\displaystyle \underset{l=1}{\overset{n1}{}}}\lambda ^{l1}\left(1+{\displaystyle \frac{\lambda _2^{n+2l}}{\lambda \lambda _2}}\right)^2\right\}`$
$``$ $`4\kappa ^2(\sigma ^2+n)\mathrm{max}\{\lambda ^1,{\displaystyle \frac{\lambda _2^2}{\lambda ^2}}\}^{n+1},`$
giving the first approximation. By similar arguments, for $`(\lambda /\sigma )\widehat{M}^+(n)`$ we obtain

$`{\displaystyle \frac{\lambda }{\sigma }}\widehat{M}^+(n)`$ $`=`$ $`{\displaystyle \frac{\lambda ^{2+n}}{\sigma (\lambda \lambda _2)}}{\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}`$
$`+{\displaystyle \frac{\lambda }{\sigma }}\left\{X(n){\displaystyle \frac{1}{\lambda \lambda _2}}{\displaystyle \underset{l=1}{\overset{n1}{}}}X(l)\lambda _2^{n+1l}{\displaystyle \frac{\lambda _2^{n+1}}{\lambda \lambda _2}}\right\}`$
$`=`$ $`{\displaystyle \frac{\lambda ^{2+n}}{\sigma (\lambda \lambda _2)}}\left({\displaystyle \frac{W^{(1)}(n1)}{f_1^{(1)}}}+\stackrel{~}{U}_2(n)\right),`$
where

$$|𝐄\stackrel{~}{U}_2(n)|=(|\lambda _2|/\lambda )^{n+1}$$

and

$`\mathrm{Var}\stackrel{~}{U}_2(n)`$ $``$ $`\lambda ^{2n2}c\sigma (\lambda \lambda _2)^2\left\{\lambda ^{n1}+{\displaystyle \underset{l=1}{\overset{n1}{}}}{\displaystyle \frac{\lambda ^{l1}\lambda _2^{2(n+1l)}}{(\lambda \lambda _2)^2}}\right\}`$
$``$ $`4\kappa ^2(\lambda 1+n)\mathrm{max}\{\lambda ^1,{\displaystyle \frac{\lambda _2^2}{\lambda ^2}}\}^n,`$
giving the second approximation. $`[]`$

We now use these approximations as in the previous section, starting by observing that

$`\epsilon (n,n^{}):=|𝐄\mathrm{exp}\{\mathrm{\Lambda }^1(\widehat{N}^+(n^{})\widehat{s}(n)+\widehat{M}^+(n)\widehat{u}(n^{})\widehat{M}^+(n)\widehat{N}^+(n^{}))\}`$
$`𝐄\mathrm{exp}\{\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\left({\displaystyle \frac{\lambda ^{n+n^{}}}{\mathrm{\Lambda }\sigma }}\right)W^{(1)}(n1)W^{}{}_{}{}^{(1)}(n^{}1)\}|`$
$``$ $`{\displaystyle \frac{\lambda ^3}{\sigma (\lambda \lambda _2)^2}}{\displaystyle \frac{\lambda ^{n+n^{}}}{\mathrm{\Lambda }}}\{𝐄|\stackrel{~}{U}_1^{}(n^{})|𝐄\{\lambda ^n\widehat{M}^+(n)\}+𝐄|\stackrel{~}{U}_2(n)|`$
$`+𝐄|\stackrel{~}{U}_1(n)|𝐄\{\lambda ^n^{}\widehat{N}^+(n^{})\}+𝐄|\stackrel{~}{U}_2^{}(n^{})|\}`$
$`+\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2{\displaystyle \frac{\lambda ^{n+n^{}}}{\mathrm{\Lambda }}}\left\{𝐄|\stackrel{~}{U}_2(n)|𝐄\{\lambda ^n^{}\widehat{N}^+(n^{})\}+𝐄|\stackrel{~}{U}_2^{}(n^{})|\right\},`$
since $`𝐄W^{(1)}(m)=f_1^{(1)}=(\lambda \sigma )^{1/2}`$ for all $`m`$. Since also, from (5.1), $`\lambda ^m𝐄\widehat{M}^+(m)2`$, it follows from Lemma 5.3 and because $`\lambda 1+\sigma >1`$ that

$`\epsilon (n,n^{})`$ $``$ $`\{17+18\kappa \sqrt{(nn^{})+(\sigma ^2(\lambda 1))}\}{\displaystyle \frac{\lambda ^3}{(\lambda \lambda _2)^2}}{\displaystyle \frac{\lambda ^{n+n^{}}}{\mathrm{\Lambda }\sigma }}`$ (5.20)
$`\times \mathrm{max}\{\lambda ^{1/2},{\displaystyle \frac{|\lambda _2|}{\lambda }}\}^{(nn^{})}.`$
Then similarly, since $`(W^{(1)}(j)W_{k,\sigma })/f_1^{(1)}`$ has mean zero and, letting $`n\mathrm{}`$ in (5.3), variance at most $`\kappa ^2\lambda ^j`$, it follows that

$`|𝐄\mathrm{exp}\{\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\left({\displaystyle \frac{\lambda ^{n+n^{}}}{\mathrm{\Lambda }\sigma }}\right)W^{(1)}(n1)W^{}{}_{}{}^{(1)}(n^{}1)\}`$ (5.21)
$`𝐄\mathrm{exp}\{\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\left({\displaystyle \frac{\lambda ^{n+n^{}}}{\mathrm{\Lambda }\sigma }}\right)W_{k,\sigma }W_{k,\sigma }^{}\}|`$
$``$ $`2\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\left({\displaystyle \frac{\lambda ^{n+n^{}}}{\mathrm{\Lambda }\sigma }}\right)\kappa \lambda ^{\{(nn^{})1\}/2}.`$
So choose $`n_d`$ so that $`\lambda ^{n_d}=\varphi _d(\mathrm{\Lambda }\sigma )^{1/2}`$ with $`\lambda ^1<\varphi _d1`$, and let $`n=n_d+r`$, $`n^{}=n_d+r^{}`$; then define the quantities

$`\eta _1^{}(r,r^{})`$ $`:=`$ $`256\varphi _d^3\{\sigma (2k(n_d+(rr^{}))+1)\}^2(1+\kappa ^2)\lambda ^{r+r^{}+(rr^{})};`$
$`\eta _2^{}(r,r^{})`$ $`:=`$ $`32\varphi _d\{\sigma (2k(n_d+(rr^{}))+1)\}\lambda ^{(rr^{})};`$
$`\eta _3^{}(r,r^{})`$ $`:=`$ $`4\varphi _d^{3/2}\lambda ^{1/2}(\lambda \sigma )^2\kappa \lambda ^{r+r^{}(rr^{})/2},`$
and

$$\eta _4^{}(r,r^{}):=18\varphi _d^{2\gamma }\lambda ^{1\gamma }\{1+\kappa (n_d+(rr^{})+(\sigma ^2(\lambda 1)))^{1/2}\}\lambda ^{r+r^{}\gamma (rr^{})},$$

where

$`\gamma `$ $`:=`$ $`\gamma (k,\sigma ):=\mathrm{min}\{\frac{1}{2},(\mathrm{log}(\lambda /|\lambda _2|)/\mathrm{log}\lambda \}.`$ (5.22)
Note that, for fixed $`k\sigma =\rho `$, simple differentiation shows that $`\lambda _1`$ is an increasing function of $`\sigma `$ and $`|\lambda _2|`$ a decreasing function, so that $`\lambda _1(\sigma )\lambda _1(0)`$, $`|\lambda _2(\sigma )||\lambda _2(0)|`$, and hence

$$\frac{\mathrm{log}(\lambda /|\lambda _2|)}{\mathrm{log}\lambda }=1\frac{\mathrm{log}|\lambda _2|}{\mathrm{log}\lambda }1\frac{\mathrm{log}(\sqrt{1+8\rho }1)}{\mathrm{log}(\sqrt{1+8\rho }+1)}\frac{1}{2}$$

in $`\rho 1`$. Thus, for $`\rho 1`$, we have $`\gamma =\frac{1}{2}`$.

Then, from Lemma 5.2 and (5.20) and (5.21), we have the following analogue of Theorem 3.8.

###### Theorem 5.4

With the above assumptions and definitions, for $`x𝐙`$ and $`r=r(x)=x/2`$, $`r^{}=r^{}(x)=xr(x)(x+1)/2`$, we have

$`\left|𝐏[D>2n_d+x]𝐄\mathrm{exp}\left\{\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\varphi _d^2\lambda ^xW_{k,\sigma }W_{k,\sigma }^{}\right\}\right|`$
$`(\eta _1^{}(r,r^{})+\eta _2^{}(r,r^{}))(\mathrm{\Lambda }\sigma )^{1/2}+\eta _3^{}(r,r^{})(\mathrm{\Lambda }\sigma )^{1/4}+\eta _4^{}(r,r^{})(\mathrm{\Lambda }\sigma )^{\gamma /2}.`$
In particular, if $`\rho 1`$,

$`\left|𝐏[D>2n_d+x]𝐄\mathrm{exp}\left\{\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\varphi _d^2\lambda ^xW_{k,\sigma }W_{k,\sigma }^{}\right\}\right|`$
$`(\eta _1^{}(r,r^{})+\eta _2^{}(r,r^{}))(\mathrm{\Lambda }\sigma )^{1/2}+(\eta _3^{}(r,r^{})+\eta _4^{}(r,r^{}))(\mathrm{\Lambda }\sigma )^{1/4}.`$
Note that the expectation in Theorem 5.4 is taken conditional on the initial condition $`\widehat{M}_0=𝐞^{(1)}`$.

The theorem can be translated into a uniform bound, similar to that of Theorem 3.9. To do so, we need to be able to control $`𝐄\{e^{\psi W_{k,\sigma }W_{k,\sigma }^{}}\}`$ for large $`\psi `$. The following analogue of Lemma 3.7 makes this possible. To state it, we first need some notation.

For $`W_{k,\sigma }`$ as in (4.11), let $`\varphi _{k,\sigma }:=(\varphi _1,\varphi _2)`$ denote the Laplace transforms

$`\varphi _1(\theta )`$ $`=`$ $`𝐄\{e^{\theta (f_1^{(1)})^1W_{k,\sigma }}|\widehat{M}_0=𝐞^{(1)}\};`$ (5.23)
$`\varphi _2(\theta )`$ $`=`$ $`𝐄\{e^{\theta (f_1^{(1)})^1W_{k,\sigma }}|\widehat{M}_0=𝐞^{(2)}\}`$
of $`((f_1^{(1)})^1W_{k,\sigma })`$, where $`𝐞^{(i)}`$ is the $`i`$’th unit vector. Although we now need to distinguish other initial conditions for the branching process, unconditional expectations will always in what follows presuppose the initial condition $`\widehat{M}_0=𝐞^{(1)}`$, as before. Then, as in Harris , p.45, $`\varphi _{k,\sigma }`$ satisfies the Poincaré equation

$`\varphi _i(\lambda \theta )`$ $`=`$ $`g^i(\varphi _1(\theta ),\varphi _2(\theta ))\text{in}\mathrm{}\theta 0;i=1,2,`$ (5.24)
where $`g^i`$ is the generating function of $`\widehat{M}_1`$ if $`\widehat{M}_0=𝐞^{(i)}`$:

$`g^i(s_1,s_2)={\displaystyle \underset{r_1,r_2=0}{\overset{\mathrm{}}{}}}p^i(r_1,r_2)s_1^{r_1}s_2^{r_2},`$
where $`p^i(r_1,r_2)`$ is the probability that an individual of type $`i`$ has $`r_1`$ children of type 1 and $`r_2`$ children of type 2. Here, from the binomial structure,

$`g^1(s_1,s_2)`$ $`=`$ $`s_2\left({\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}s_1+1{\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}\right)^\mathrm{\Lambda }`$
and

$`g^2(s_1,s_2)`$ $`=`$ $`s_2\left({\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}s_1+1{\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}\right)^{2k\mathrm{\Lambda }}.`$
The Laplace transforms $`\varphi _{k,\sigma }`$ can be bounded as follows.

###### Lemma 5.5

For $`\theta ,\sigma >0`$, we have

$`\varphi _{k,\sigma ;1}(\theta )=:\varphi _1(\theta )`$ $``$ $`{\displaystyle \frac{1}{1+\theta }};`$
$`\varphi _{k,\sigma ;2}(\theta )=:\varphi _2(\theta )`$ $``$ $`{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}},`$
and hence

$`𝐄\left\{e^{\theta \left(f_1^{(1)}\right)^2W_{k,\sigma }W_{k,\sigma }^{}}\right|\widehat{M}(0)=\widehat{M}^{}(0)=𝐞^{(1)}\}`$ $``$ $`\theta ^1\mathrm{log}\left(1+\theta \right).`$
Proof: We proceed by induction. Put

$`\varphi _{i,n}(\theta )`$ $`=`$ $`𝐄\left(e^{\theta (f_1^{(1)})^1W^{(1)}(n)}|\widehat{M}(0)=𝐞^{(i)}\right),i=1,2.`$
Then

$`\varphi _{1,0}(\theta )`$ $`=`$ $`e^\theta {\displaystyle \frac{1}{1+\theta }};`$
$`\varphi _{2,0}(\theta )`$ $`=`$ $`e^{\theta (\lambda \sigma )}{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}}.`$
Assume that

$`\varphi _{1,n}(\theta )`$ $``$ $`{\displaystyle \frac{1}{1+\theta }};`$
$`\varphi _{2,n}(\theta )`$ $``$ $`{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}}.`$
By the Poincaré recursion,

$`\varphi _{i,n+1}(\theta )`$ $`=`$ $`g^i(\varphi _{1,n}\left({\displaystyle \frac{\theta }{\lambda }}\right),\varphi _{2,n}\left({\displaystyle \frac{\theta }{\lambda }}\right))`$
for $`i=1,2`$. Hence, using the induction assumption,

$`\varphi _{1,n+1}(\theta )`$ $``$ $`{\displaystyle \frac{\lambda }{\lambda +\theta (\lambda \sigma )}}\mathrm{exp}\left\{\sigma \left({\displaystyle \frac{\lambda }{\lambda +\theta }}1\right)\right\}`$
$``$ $`{\displaystyle \frac{\lambda }{\lambda (1+\theta )\theta \sigma }}{\displaystyle \frac{\lambda +\theta }{\lambda +\theta +\theta \sigma }}`$
$`=`$ $`{\displaystyle \frac{\lambda (\lambda +\theta )}{\lambda (1+\theta )(\lambda +\theta )+\theta ^2(\lambda 1\sigma )\sigma }}`$
$``$ $`{\displaystyle \frac{1}{1+\theta }},`$
and, also from (4.6),

$`\varphi _{2,n+1}(\theta )`$ $``$ $`{\displaystyle \frac{\lambda }{\lambda +\theta (\lambda \sigma )}}\mathrm{exp}\left\{2k\sigma \left({\displaystyle \frac{\lambda }{\lambda +\theta }}1\right)\right\}`$
$``$ $`{\displaystyle \frac{\lambda }{\lambda +\theta +\theta (\lambda \sigma 1)}}{\displaystyle \frac{\lambda +\theta }{\lambda +\theta +2k\sigma \theta }}`$
$`=`$ $`{\displaystyle \frac{\lambda }{\lambda +\theta +\theta (\lambda \sigma 1)}}{\displaystyle \frac{\lambda +\theta }{\lambda +\theta +(\lambda 1)(\lambda \sigma )\theta }}`$
$`=`$ $`{\displaystyle \frac{\lambda (\lambda +\theta )}{\lambda (\lambda +\theta )(1+\theta (\lambda \sigma ))+\theta ^2(\lambda 1\sigma )(\lambda \sigma )(\lambda 1)}}`$
$``$ $`{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}}.`$
Taking limits as $`n\mathrm{}`$ proves the first two assertions. The last assertion follows as in Lemma 3.7. $`[]`$

###### Theorem 5.6

Let $`\mathrm{\Delta }_d`$ denote a random variable on the integers with distribution given by

$$𝐏\left[\mathrm{\Delta }_d>x\right]=𝐄\mathrm{exp}\left\{\left(\frac{\lambda }{\lambda \lambda _2}\right)^2(\lambda \sigma )(2\lambda \sigma )\varphi _d^2\lambda ^xW_{k,\sigma }W_{k,\sigma }^{}\right\},x𝐙,$$
(5.25)
and let $`D^{}=\mathrm{\Delta }_d+2n_d`$. Then

$`d_{TV}((D),(D^{}))=O\left(\mathrm{log}(\mathrm{\Lambda }\sigma )(\mathrm{\Lambda }\sigma )^{\gamma /(4\gamma )}\right),`$
uniformly in $`\mathrm{\Lambda }`$, $`k`$ and $`\sigma `$ such that $`k\sigma \rho _0`$, for any fixed $`0<\rho _0<\mathrm{}`$, where $`\gamma `$ is given as in (5.22). Hence $`d_{TV}((D),(D^{}))0`$ if $`\mathrm{\Lambda }\sigma \mathrm{}`$ and $`k\sigma `$ remains bounded. In particular, $`\gamma =1/2`$ if $`k\sigma 1`$, and the approximation error is then of order $`O(\mathrm{log}(\mathrm{\Lambda }\sigma )(\mathrm{\Lambda }\sigma )^{1/7})`$.

Proof: Fix $`G`$, and consider $`x`$ satisfying $`x\frac{G\mathrm{log}(\mathrm{\Lambda }\sigma )2\mathrm{log}\varphi _d}{\mathrm{log}\lambda }`$; set $`r(x)=x/2`$, $`r^{}(x)=xr(x)(x+1)/2`$. Then it follows from Theorem 5.4 and (5.7) that

$`\left|𝐏[D>2n_d+x]𝐏[D^{}>2n_d+x]\right|`$
$``$ $`(\eta _1^{}(r(x),r^{}(x))+\eta _2^{}(r(x),r^{}(x)))(\mathrm{\Lambda }\sigma )^{1/2}`$
$`+\eta _3^{}(r(x),r^{}(x))(\mathrm{\Lambda }\sigma )^{1/4}+\eta _4^{}(r(x),r^{}(x))(\mathrm{\Lambda }\sigma )^{\gamma /2}`$
$`=`$ $`O(\lambda ^{1/2}\left({\displaystyle \frac{k\sigma \mathrm{log}(\mathrm{\Lambda }\sigma )}{\mathrm{log}\lambda }}\right)^2(\mathrm{\Lambda }\sigma )^{(13G)/2}`$
$`+\lambda ^{1/2}\left({\displaystyle \frac{k\sigma \mathrm{log}(\mathrm{\Lambda }\sigma )}{\mathrm{log}\lambda }}\right)(\mathrm{\Lambda }\sigma )^{(1G)/2}`$
$`+\lambda ^{3/4}(\lambda \sigma )^2(\mathrm{\Lambda }\sigma )^{(13G)/4}`$
$`+\lambda ^{1\gamma /2}({\displaystyle \frac{\mathrm{log}(\mathrm{\Lambda }\sigma )}{\mathrm{log}\lambda }}+(\sigma ^2(\lambda 1)))^{1/2}(\mathrm{\Lambda }\sigma )^{(\gamma G(2\gamma ))/2}).`$
Also, from Lemma 5.5, recalling that $`(f_1^{(1)})^2=\lambda \sigma `$, we have the upper tail estimate

$`𝐏(\mathrm{\Delta }_d>x)`$
$``$ $`{\displaystyle \frac{(\lambda \lambda _2)^2}{\lambda ^2(2\lambda \sigma )}}\mathrm{log}\left(1+{\displaystyle \frac{\lambda ^2}{(\lambda \lambda _2)^2}}(2\lambda \sigma )(\mathrm{\Lambda }\sigma )^G\right)(\mathrm{\Lambda }\sigma )^G`$
$`=`$ $`O\left(\mathrm{log}(\mathrm{\Lambda }\sigma )(\mathrm{\Lambda }\sigma )^G\right).`$
Comparing the exponents of $`\mathrm{\Lambda }\sigma `$, and remembering that $`\gamma 1/2`$, the best choice of $`G`$ is $`G=\gamma /(4\gamma )`$, making $`G=(\gamma G(2\gamma ))/2`$; noting also that $`\lambda =O(1+\sigma +\sqrt{k\sigma })`$, the theorem is proved. $`[]`$

Remembering that the choices $`k\sigma =\rho `$ and $`\mathrm{\Lambda }=Lk`$ match this model with that of Section 2, we see that $`\mathrm{\Lambda }\sigma =L\rho `$, and that thus Theorem 5.6 matches Theorem 3.9 closely for $`\rho 1`$, but that the total variation distance estimate here becomes bigger as $`\rho `$ increases. Indeed, if $`\rho \mathrm{}`$ and $`\sigma =O(k)`$, then $`\gamma (k,\sigma )0`$, and no useful approximation is obtained. This reflects the fact that, when $`|\lambda _2|/\lambda `$ is close to $`1`$, the martingale $`W^{(1)}(n)`$ only slowly comes to dominate the behaviour of the two type branching process; for example, from (5.13),

$$\widehat{M}^+(n)=\frac{1}{\lambda \lambda _2}\left(\frac{\lambda ^{n+1}}{f_1^{(1)}}W^{(1)}(n)\frac{\lambda _2^{n+1}}{f_1^{(2)}}W^{(2)}(n)\right)$$

then retains a sizeable contribution from $`W^{(2)}(n)`$ until $`n`$ becomes extremely large. This is in turn a consequence of taking the shortcuts to have length $`1`$, rather than $`0`$; as a result, the big multiplication, by a factor of $`2\rho `$, occurs only at the second time step, inducing substantial fluctuations of period $`2`$ in the branching process, which die away only slowly when $`\rho `$ is large. However, if $`\rho \mathrm{}`$ and $`k=O(\sigma ^{1\epsilon })`$ for any $`\epsilon >0`$, then $`lim\; inf\gamma (k,\sigma )>0`$, and it becomes possible for $`(D)`$ and $`(D^{})`$ to be asymptotically close in total variation. This can be deduced from the proof of the theorem by taking $`kL^\alpha `$ and $`\sigma L^{\alpha +\beta }`$, for choices of $`\alpha `$ and $`\beta `$ which ensure that $`\sigma ^2`$ dominates $`\rho `$. Under such circumstances, the effect of two successive multiplications by $`\sigma `$ in the branching process dominates that of a single multiplication by $`2\rho `$ at the second step, and approximately geometric growth at rate $`\lambda \sigma `$ results. However, as in all situations in which $`\rho `$ is a positive power of $`\mathrm{\Lambda }`$, interpoint distances are asymptotically bounded, and take one or at most two values with very high probability; an analogue of Corollary 3.10 could for instance also be proved.

If $`\rho =k\sigma `$ is small, we can again compare the distribution of $`W_{k,\sigma }`$ with the NE$`(1)`$ distribution of the limiting variable $`W`$ in the Yule process (see ), using the fact that its Laplace transforms satisfy the Poincaré equation (5.24). Define the operator $`\mathrm{\Xi }`$ by

$`(\mathrm{\Xi }\varphi )_1(\theta )`$ $`:=`$ $`g^1(\varphi _1\left({\displaystyle \frac{\theta }{\lambda }}\right),\varphi _2\left({\displaystyle \frac{\theta }{\lambda }}\right))`$
$`=`$ $`\varphi _2\left({\displaystyle \frac{\theta }{\lambda }}\right)\left({\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}\varphi _1\left({\displaystyle \frac{\theta }{\lambda }}\right)+1{\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}\right)^\mathrm{\Lambda };`$
$`(\mathrm{\Xi }\varphi )_2(\theta )`$ $`:=`$ $`g^2(\varphi _1\left({\displaystyle \frac{\theta }{\lambda }}\right),\varphi _2\left({\displaystyle \frac{\theta }{\lambda }}\right))`$
$`=`$ $`\varphi _2\left({\displaystyle \frac{\theta }{\lambda }}\right)\left({\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}\varphi _1\left({\displaystyle \frac{\theta }{\lambda }}\right)+1{\displaystyle \frac{\sigma }{\mathrm{\Lambda }}}\right)^{2k\mathrm{\Lambda }}.`$
Let

$$𝒢:=\{\gamma =(\gamma _1,\gamma _2):[0,\mathrm{})^2𝐑:\gamma _𝒢:=\underset{\theta >0}{sup}\mathrm{max}\left\{\frac{|\gamma _1(\theta )|,|\gamma _2(\theta )|}{\theta ^2}\right\}<\mathrm{}\},$$

and

$``$ $`:=`$ $`\{\psi =(\psi _1,\psi _2):[0,\mathrm{})^2𝐑:{\displaystyle \frac{\psi _1(\theta )(1\theta )}{\theta ^2}}\text{ is bounded},`$
$`{\displaystyle \frac{\psi _2(\theta )(1\theta (\lambda \sigma ))}{\theta ^2}}\text{ is bounded}\}.`$
Then $``$ contains $`\varphi _{k,\sigma }=(\varphi _1,\varphi _2)`$ as defined in (5.23), since

$$𝐄\{(f_1^{(1)})^1W_{k,\sigma }|\widehat{M}(0)=𝐞^{(1)}\}=1;𝐄\{(f_1^{(1)})^1W_{k,\sigma }|\widehat{M}(0)=𝐞^{(2)}\}=\lambda \sigma ,$$

and taking limits in (5.3) shows that $`\mathrm{Var}W_{k,\sigma }`$ exists. We next show that $`\mathrm{\Xi }`$ is a contraction on $``$.

###### Lemma 5.7

The operator $`\mathrm{\Xi }`$ is a contraction on $``$, and, for all $`\psi ,\chi `$,

$`\mathrm{\Xi }\psi \mathrm{\Xi }\chi _𝒢`$ $``$ $`\left({\displaystyle \frac{2k\sigma +1}{\lambda ^2}}\right)\psi \chi _𝒢.`$
Remark. Note that

$`{\displaystyle \frac{2k\sigma +1}{\lambda ^2}}`$ $`=`$ $`{\displaystyle \frac{\lambda ^2(\lambda 1)(\sigma +1)}{\lambda ^2}}<1.`$
Proof: For all $`\psi ,\chi `$ and $`\theta >0`$, observe that $`\psi \chi 𝒢`$. We then compute

$`\left|(\mathrm{\Xi }\psi )_1(\theta )(\mathrm{\Xi }\chi )_1(\theta )\right|`$ $``$ $`\left|\psi _2\left({\displaystyle \frac{\theta }{\lambda }}\right)\chi _2\left({\displaystyle \frac{\theta }{\lambda }}\right)\right|`$
$`+\sigma \left|\psi _1\left({\displaystyle \frac{\theta }{\lambda }}\right)\chi _1\left({\displaystyle \frac{\theta }{\lambda }}\right)\right|,`$
so that

$`{\displaystyle \frac{\left|(\mathrm{\Xi }\psi )_1(\theta )(\mathrm{\Xi }\chi )_1(\theta )\right|}{\theta ^2}}`$ $``$ $`{\displaystyle \frac{1}{\lambda ^2}}{\displaystyle \frac{\left|\psi _2\left(\frac{\theta }{\lambda }\right)\chi _2\left(\frac{\theta }{\lambda }\right)\right|}{\left(\frac{\theta }{\lambda }\right)^2}}`$ (5.26)
$`+{\displaystyle \frac{\sigma }{\lambda ^2}}{\displaystyle \frac{\left|\psi _1\left(\frac{\theta }{\lambda }\right)\chi _1\left(\frac{\theta }{\lambda }\right)\right|}{\left(\frac{\theta }{\lambda }\right)^2}}`$
$``$ $`{\displaystyle \frac{\sigma +1}{\lambda ^2}}\psi \chi _𝒢.`$
Similarly,

$`\left|(\mathrm{\Xi }\psi )_2(\theta )(\mathrm{\Xi }\chi )_2(\theta )\right|`$ $``$ $`\left|\psi _2\left({\displaystyle \frac{\theta }{\lambda }}\right)\chi _2\left({\displaystyle \frac{\theta }{\lambda }}\right)\right|`$
$`+2k\sigma \left|\psi _1\left({\displaystyle \frac{\theta }{\lambda }}\right)\chi _1\left({\displaystyle \frac{\theta }{\lambda }}\right)\right|,`$
and

$`{\displaystyle \frac{\left|(\mathrm{\Xi }\psi )_2(\theta )(\mathrm{\Xi }\chi )_2(\theta )\right|}{\theta ^2}}`$ $``$ $`\left({\displaystyle \frac{2k\sigma +1}{\lambda ^2}}\right)\psi \chi _𝒢.`$
Taking the maximum of the bounds finishes the proof. $`[]`$

Thus, for any starting function $`\psi =(\psi _1,\psi _2)`$ and for $`\varphi _{k,\sigma }=(\varphi _1,\varphi _2)`$ given in (5.23), we have

$`\varphi _{k,\sigma }\psi _𝒢`$ $``$ $`\mathrm{\Xi }\varphi _{k,\sigma }\mathrm{\Xi }\psi _𝒢+\mathrm{\Xi }\psi \psi _𝒢`$
$``$ $`{\displaystyle \frac{2k\sigma +1}{\lambda ^2}}\varphi _{k,\sigma }\psi _𝒢+\mathrm{\Xi }\psi \psi _𝒢,`$
so that

$`\varphi _{k,\sigma }\psi _𝒢`$ $``$ $`{\displaystyle \frac{\lambda ^2}{\lambda ^2(2k\sigma +1)}}\mathrm{\Xi }\psi \psi _𝒢.`$ (5.27)
Hence a function $`\psi `$ such that $`\mathrm{\Xi }\psi \psi _𝒢`$ is small provides a good approximation to $`\varphi _{k,\sigma }`$.

As a candidate $`\psi `$, we try

$`\psi _{(1)}(\theta )`$ $`=`$ $`{\displaystyle \frac{1}{1+\theta }},`$
$`\psi _{(2)}(\theta )`$ $`=`$ $`{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}};`$ (5.28)
Lemma 5.5 shows that this pair dominates $`\varphi _{k,\sigma }`$.

###### Lemma 5.8

For $`\psi `$ given in (5.28), we have

$$\mathrm{\Xi }\psi \psi _𝒢\frac{2k\sigma (\lambda ^2\lambda \sigma 1+k\sigma )}{\lambda ^2}.$$

Proof: For $`\theta >0`$, we have

$`(\mathrm{\Xi }\psi )_1(\theta )\psi _1(\theta )`$
$`=`$ $`{\displaystyle \frac{\lambda }{\lambda +\theta (\lambda \sigma )}}\left(1{\displaystyle \frac{\sigma \theta }{\mathrm{\Lambda }(\lambda +\theta )}}\right)^\mathrm{\Lambda }{\displaystyle \frac{1}{1+\theta }}`$
$`=`$ $`{\displaystyle \frac{1}{1+\theta }}\left\{{\displaystyle \frac{\lambda (1+\theta )}{\lambda +\theta (\lambda \sigma )}}\left(1{\displaystyle \frac{\sigma \theta }{(\lambda +\theta )}}\right)1\right\}+R_1,`$
where

$`R_1`$ $`=`$ $`{\displaystyle \frac{\lambda }{\lambda +\theta (\lambda \sigma )}}\left[\left(1{\displaystyle \frac{\sigma \theta }{\mathrm{\Lambda }(\lambda +\theta )}}\right)^\mathrm{\Lambda }1+{\displaystyle \frac{\sigma \theta }{\lambda +\theta }}\right].`$
Moreover,

$`{\displaystyle \frac{1}{1+\theta }}\left\{{\displaystyle \frac{\lambda (1+\theta )}{\lambda +\theta (\lambda \sigma )}}\left(1{\displaystyle \frac{\sigma \theta }{\lambda +\theta }}\right)1\right\}`$
$`={\displaystyle \frac{\theta ^2\sigma (1\lambda )}{(1+\theta )(\lambda +(\lambda \sigma )\theta )(\lambda +\theta )}}.`$
From Taylor’s expansion, it follows that

$`|R_1|`$ $``$ $`{\displaystyle \frac{\lambda \mathrm{\Lambda }(\mathrm{\Lambda }1)\sigma ^2\theta ^2}{2(\lambda +(\lambda \sigma )\theta )\mathrm{\Lambda }^2(\lambda +\theta )^2}}`$
$``$ $`{\displaystyle \frac{\sigma ^2\theta ^2}{2\lambda ^2}}.`$
Hence

$`{\displaystyle \frac{\left|(\mathrm{\Xi }\psi )_1(\theta )\psi _1(\theta )\right|}{\theta ^2}}`$ $``$ $`{\displaystyle \frac{\sigma (2(\lambda 1)+\sigma )}{2\lambda ^2}}.`$ (5.29)
Similarly,

$`(\mathrm{\Xi }\psi )_2(\theta )\psi _2(\theta )`$
$`=`$ $`{\displaystyle \frac{\lambda }{\lambda +\theta (\lambda \sigma )}}\left(1{\displaystyle \frac{\sigma \theta }{\mathrm{\Lambda }(\lambda +\theta )}}\right)^{2k\mathrm{\Lambda }}{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}}`$
$`=`$ $`{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}}\left\{{\displaystyle \frac{\lambda (1+\theta (\lambda \sigma ))}{\lambda +\theta (\lambda \sigma )}}\left(1{\displaystyle \frac{2k\sigma \theta }{\lambda +\theta }}\right)1\right\}+R_2,`$
where

$`R_2`$ $`=`$ $`{\displaystyle \frac{\lambda }{\lambda +\theta (\lambda \sigma )}}\left[\left(1{\displaystyle \frac{\sigma \theta }{\mathrm{\Lambda }(\lambda +\theta )}}\right)^{2k\mathrm{\Lambda }}1+{\displaystyle \frac{2k\sigma \theta }{\lambda +\theta }}\right].`$
Using (4.6), we obtain

$`{\displaystyle \frac{1}{1+\theta (\lambda \sigma )}}\left\{{\displaystyle \frac{\lambda (1+\theta (\lambda \sigma ))}{\lambda +\theta (\lambda \sigma )}}\left(1{\displaystyle \frac{2k\sigma \theta }{\lambda +\theta }}\right)1\right\}`$
$`=`$ $`{\displaystyle \frac{\theta ^2(\lambda 1)(\lambda \sigma )(1+\lambda \sigma \lambda ^2)}{(1+\theta (\lambda \sigma ))(\lambda +(\lambda \sigma )\theta )(\lambda +\theta )}}`$
$`=`$ $`{\displaystyle \frac{2k\sigma \theta ^2(1+\lambda \sigma \lambda ^2)}{(1+\theta (\lambda \sigma ))(\lambda +(\lambda \sigma )\theta )(\lambda +\theta )}}.`$
From Taylor’s expansion, it now follows that

$`|R_2|`$ $``$ $`{\displaystyle \frac{2k\mathrm{\Lambda }(2k\mathrm{\Lambda }1)\lambda \sigma ^2\theta ^2}{2(\lambda +(\lambda \sigma )\theta )\mathrm{\Lambda }^2(\lambda +\theta )^2}}`$
$``$ $`{\displaystyle \frac{2k^2\sigma ^2\theta ^2}{\lambda ^2}}.`$
Hence

$`{\displaystyle \frac{\left|(\mathrm{\Xi }\psi )_2(\theta )\psi _2(\theta )\right|}{\theta ^2}}`$ $``$ $`{\displaystyle \frac{2k\sigma (\lambda ^2\lambda \sigma 1+k\sigma )}{\lambda ^2}},`$
completing the proof, since

$$2(\lambda ^2\lambda \sigma 1+k\sigma )=2(\lambda 1)+2(3k1)\sigma >2(\lambda 1)+\sigma .$$

$`[]`$

This enables us to prove the exponential approximation to $`(W_{k,\sigma })`$ when $`k\sigma `$ is small.

###### Theorem 5.9

As $`k\sigma 0`$, $`(W_{k,\sigma })\mathrm{NE}(1)`$.

Proof: Let $`\varphi _{k,\sigma }`$ be as in (5.23), and $`\psi `$ as in (5.28). Then $`(\varphi _{k,\sigma })_1`$ is the Laplace transform of

$$((f_1^{(1)})^1W_{k,\sigma }):=((f_1^{(1)})^1W_{k,\sigma }|\widehat{M}(0)=𝐞^{(1)}),$$

and $`\psi _1`$ that of NE$`(1)`$, and $`(f_1^{(1)})^1=(\lambda \sigma )^{1/2}1`$ as $`k\sigma 0`$. Hence it is enough to show that

$$\underset{k\sigma 0}{lim}\varphi _{k,\sigma }\psi _𝒢=0.$$

However, using Lemma 5.8 and (5.27), we obtain

$`\varphi _{k,\sigma }\psi _𝒢`$
$`\left({\displaystyle \frac{\lambda ^2}{\lambda ^212k\sigma }}\right)\mathrm{\Xi }\psi \psi _𝒢`$
$`2k\sigma {\displaystyle \frac{\lambda ^2\lambda \sigma 1+k\sigma }{\lambda ^212k\sigma }}`$
$`2k\sigma {\displaystyle \frac{k\sigma (5+2\sigma )}{2k\sigma (\sigma +1)}}(1+2k\sigma (\sigma +1))`$
$`k\sigma (1+2k\sigma )(5+2\sigma )0,`$ (5.30)
since $`k\sigma 0`$. This proves the theorem. $`[]`$

Again we can use this result to derive an approximation to the distribution of the distance for $`D`$, based on a corresponding distribution derived from the NE(1) distribution. The starting point is the following result.

###### Theorem 5.10

Let $`W,W^{}`$ be independent NE(1) variables. Then, for all $`\theta >0`$,

$`\left|𝐄\mathrm{exp}\left\{\theta (\lambda \sigma )W_{k,\sigma }W_{k,\sigma }^{}\right\}𝐄e^{\theta WW^{}}\right|`$
$``$ $`5\theta ^2k\sigma \left\{(3\sigma /2)+(1+2k\sigma )(5+2\sigma )\right\}.`$
Proof: As in the proof of Theorem 3.14, with $`\varphi _{k,\sigma }`$ as in (5.23) and $`\psi `$ as in (5.28), and because, from (4.9), $`\lambda \sigma =(f_1^{(1)})^2`$, we have

$`𝐄\mathrm{exp}\left\{\theta (\lambda \sigma )W_{k,\sigma }W_{k,\sigma }^{}\right\}𝐄e^{\theta WW^{}}`$
$`=`$ $`𝐄\left\{(\varphi _{k,\sigma })_1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}𝐄\psi _1(\theta W)`$
$`=`$ $`𝐄\left\{(\mathrm{\Xi }\varphi _{k,\sigma })_1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}𝐄\left\{(\mathrm{\Xi }\psi )_1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}`$
$`+𝐄\left\{(\mathrm{\Xi }\psi )_1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}𝐄\left\{\psi _1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}`$
$`+𝐄\left\{\psi _1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}𝐄\psi _1(\theta W).`$
Now (5.26) in the proof of Lemma 5.7 gives

$`\left|𝐄\left\{(\mathrm{\Xi }\varphi )_1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}𝐄\left\{(\mathrm{\Xi }\psi _{k,\sigma })_1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}\right|`$
$``$ $`\theta ^2(f_1^{(1)})^2{\displaystyle \frac{\sigma +1}{\lambda ^2}}\varphi _{k,\sigma }\psi _𝒢𝐄\{(W_{k,\sigma }^{})^2\}`$
$``$ $`\theta ^2(1+\kappa ^2){\displaystyle \frac{\sigma +1}{\lambda ^2}}\varphi _{k,\sigma }\psi _𝒢`$
$``$ $`3\theta ^2{\displaystyle \frac{\sigma +1}{\lambda ^2}}\varphi _{k,\sigma }\psi _𝒢,`$
from (4.11), (5.3) and (5.7), and (5) then implies that the above expression can be bounded by

$`3\theta ^2{\displaystyle \frac{\sigma +1}{\lambda ^2}}k\sigma (1+2k\sigma )(5+2\sigma ).`$
Similarly, from (5.29) in the proof of Lemma 5.8,

$`\left|𝐄\left\{(\mathrm{\Xi }\psi )_1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}𝐄\left\{\psi _1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}\right|`$ $``$ $`3\theta ^2{\displaystyle \frac{\sigma \{2(\lambda 1)+\sigma \}}{2\lambda ^2}}.`$
Then, with $`W\mathrm{NE}(1)`$ independent of $`W_{k,\sigma }^{}`$, we have

$$𝐄\left\{\psi _1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}=𝐄\left\{e^{\theta (f_1^{(1)})^1WW_{k,\sigma }^{}}\right\}=𝐄\left\{(\varphi _{k,\sigma })_1(\theta W)\right\},$$

and hence, from (5) in the proof of Theorem 5.9, it follows that

$`\left|𝐄\left\{\psi _1(\theta (f_1^{(1)})^1W_{k,\sigma }^{})\right\}𝐄\psi _1(\theta W)\right|`$ $`=`$ $`\left|𝐄\left\{(\varphi _{k,\sigma })_1(\theta W)\right\}𝐄\psi _1(\theta W)\right|`$
$``$ $`2\theta ^2k\sigma (1+2k\sigma )(5+2\sigma ).`$
Since $`\lambda 1<2k\sigma `$ and $`\lambda ^2>\sigma +1`$, the assertion follows from the triangle inequality. $`[]`$

Recalling that

$$𝐄e^{\theta WW^{}}=_0^{\mathrm{}}\frac{e^y}{1+\theta y}𝑑y,$$

we can now derive the analogue of Theorem 3.15.

###### Theorem 5.11

As in Theorem 5.6, let $`\mathrm{\Delta }_d`$ denote a random variable on the integers with distribution given by

$`𝐏\left[\mathrm{\Delta }_d>x\right]=𝐄\mathrm{exp}\left\{\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(\lambda \sigma )(2\lambda \sigma )\varphi _d^2\lambda ^xW_{k,\sigma }W_{k,\sigma }^{}\right\},x𝐙.`$
Let $`T`$ denote a random variable on $`𝐑`$ with distribution given by

$`𝐏\left[T>z\right]={\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{e^y}{1+2ye^{2z}}}𝑑y.`$
Then

$`\underset{z𝐑}{sup}\left|𝐏\left[\frac{\lambda 1}{2}\mathrm{\Delta }_d>z\right]𝐏[T>z]\right|`$ $`=`$ $`O\left\{(k\sigma )^{1/3}\left(1+\mathrm{log}\left(1/k\sigma \right)\right)\right\},`$
uniformly in $`k\sigma 2`$.

Proof: We use an argument similar to the proof of Theorem 3.15. Putting

$`\stackrel{~}{c}(\lambda )={\displaystyle \frac{\mathrm{log}\lambda }{\lambda 1}}={\displaystyle \frac{\mathrm{log}(1+2\frac{\lambda 1}{2})}{2\frac{\lambda 1}{2}}},`$
we have, as before,

$$1\stackrel{~}{c}(\lambda )1\frac{\lambda 1}{2};$$

we also write

$`\beta (\lambda )`$ $`:=`$ $`\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2\left(\lambda {\displaystyle \frac{\sigma }{2}}\right)\varphi _d^2.`$
We use the following bounds. First, from the characteristic equation (4.6), we have

$`0\lambda 1`$ $`=`$ $`{\displaystyle \frac{2k\sigma }{\lambda \sigma }}2k\sigma .`$
Then, since $`\sqrt{a+b}\sqrt{a}+\sqrt{b}`$ for $`a,b0`$, it follows that

$`1+\sigma \lambda `$ $``$ $`1+\sigma +\sqrt{\sigma (2k1)}.`$
Thus, and because $`\lambda ^1\varphi _d1`$ and $`\lambda _2<0`$, we have

$`\beta (\lambda )`$ $``$ $`1+(\sigma /2)+\sqrt{\sigma (2k1)}`$
and

$`\beta (\lambda )`$ $``$ $`\left({\displaystyle \frac{1}{\lambda \lambda _2}}\right)^2`$
$`=`$ $`1{\displaystyle \frac{2\sigma (4k1)+\sigma ^2}{(\sigma +1)^2+4\sigma (2k1)}}.`$
This in turn gives

$`|\beta (\lambda )1|`$ $``$ $`\mathrm{max}\{(\sigma /2)+\sqrt{\sigma (2k1)},{\displaystyle \frac{2\sigma (4k1)+\sigma ^2}{(\sigma +1)^2+4\sigma (2k1)}}\}`$
$`=:`$ $`\mathrm{\Gamma }(\sigma ,k)`$
$`=`$ $`O\left(\mathrm{max}\{\sigma ,\sqrt{k\sigma }\}\right).`$
For the main part of the distribution, we write

$`𝐏\left[\frac{\lambda 1}{2}\mathrm{\Delta }_d>z\right]𝐏[T>z]`$ (5.33)
$`=`$ $`𝐏\left[\frac{\lambda 1}{2}\mathrm{\Delta }_d>z\right]{\displaystyle _0^{\mathrm{}}}e^y\left(1+2y\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )}\right)^1𝑑y`$
$`+{\displaystyle _0^{\mathrm{}}}e^y\left(1+2y\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )}\right)^1𝑑y𝐏[T>z\stackrel{~}{c}(\lambda )]`$
$`+𝐏[T>z\stackrel{~}{c}(\lambda )]𝐏[T>z].`$
Now, for (5.33), Theorem 5.10 yields

$`\left|𝐏\left[\frac{\lambda 1}{2}\mathrm{\Delta }_d>z\right]{\displaystyle _0^{\mathrm{}}}e^y\left(1+2y\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )}\right)^1𝑑y\right|`$
$`=`$ $`\left|𝐄\mathrm{exp}\left\{2\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )}W_{k,\sigma }W_{k,\sigma }^{}\right\}{\displaystyle _0^{\mathrm{}}}e^y\left(1+2y\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )}\right)^1𝑑y\right|`$
$``$ $`4\beta (\lambda )^2e^{4z\stackrel{~}{c}(\lambda )}5k\sigma \left\{(3\sigma /2)+(1+2k\sigma )(5+2\sigma )\right\}`$
$``$ $`(2\lambda \sigma )^2e^{4z}5k\sigma \left\{(3\sigma /2)+(1+2k\sigma )(5+2\sigma )\right\}.`$
With (3.18), we have, for (5.33), that

$`\left|{\displaystyle _0^{\mathrm{}}}e^y\left(1+2y\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )}\right)^1𝑑y𝐏[T>z\stackrel{~}{c}(\lambda )]\right|`$
$``$ $`2e^{2z\stackrel{~}{c}(\lambda )}{\displaystyle \frac{|\beta (\lambda )1|}{\mathrm{max}\{1,2\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )},2e^{2z\stackrel{~}{c}(\lambda )}\}}}`$
$``$ $`2{\displaystyle \frac{e^{2z\stackrel{~}{c}(\lambda )}}{\mathrm{max}\{1,2e^{2z\stackrel{~}{c}(\lambda )}\}}}|\beta (\lambda )1|`$
$``$ $`\mathrm{\Gamma }(\sigma ,k).`$
Similarly, for (5.33), because $`1\stackrel{~}{c}(\lambda )\frac{\lambda 1}{2}k\sigma `$ and from Taylor’s expansion, it follows that

$`\left|𝐏[T>z\stackrel{~}{c}(\lambda )]𝐏[T>z]\right|`$
$`=`$ $`\left|{\displaystyle _0^{\mathrm{}}}e^y\left(1+2ye^{2z\stackrel{~}{c}(\lambda )}\right)^1𝑑y{\displaystyle _0^{\mathrm{}}}e^y\left(1+2ye^{2z}\right)^1𝑑y\right|`$
$``$ $`2e^{2z}{\displaystyle \frac{|e^{2z(1\stackrel{~}{c}(\lambda ))}1|}{\mathrm{max}\{1,2e^{2z\stackrel{~}{c}(\lambda )},2e^{2z}\}}}.`$
If $`z>0`$, this gives

$$|𝐏[T>z\stackrel{~}{c}(\lambda )]𝐏[T>z]|2z(1\stackrel{~}{c}(\lambda ))2k\sigma z;$$

if $`z0`$, we have

$`|𝐏[T>z\stackrel{~}{c}(\lambda )]𝐏[T>z]|`$ $``$ $`2|z|(1\stackrel{~}{c}(\lambda ))e^{2z\stackrel{~}{c}(\lambda )}2k\sigma |z|e^{2z(1k\sigma )}.`$
Hence we conclude that, uniformly in $`k\sigma 1/2`$,

$`𝐏\left[\frac{\lambda 1}{2}\mathrm{\Delta }_d>z\right]𝐏[T>z]`$ (5.34)
$``$ $`5k\sigma e^{4z}(2\lambda \sigma )^2\left\{(3\sigma /2)+(1+2k\sigma )(5+2\sigma )\right\}`$
$`+\mathrm{\Gamma }(\sigma ,k)+2k\sigma |z|\mathrm{min}\{1,e^{2z(1k\sigma )}\}`$
$``$ $`C_1\left\{k\sigma (e^{4z}+1)+\sqrt{k\sigma }\right\},`$
for some constant $`C_1`$.

For the large values of $`z`$, where the bound given in (5.34) becomes useless, we can estimate the upper tails of the random variables separately. First, for $`x𝐙`$, we have

$`𝐏\left[\mathrm{\Delta }_d>x\right]=𝐄\mathrm{exp}\left\{2\beta (\lambda )\lambda ^x(f_1^{(1)})^2W_{k,\sigma }W_{k,\sigma }^{}\right\},`$
so that, by Lemma 5.5, it follows that

$`𝐏\left[\frac{\lambda 1}{2}\mathrm{\Delta }_d>z\right]`$
$`=`$ $`𝐄\mathrm{exp}\left\{2\beta (\lambda )e^{2z\stackrel{~}{c}(\lambda )}(f_1^{(1)})^2W_{k,\sigma }W_{k,\sigma }^{}\right\}`$
$``$ $`\left({\displaystyle \frac{\lambda \lambda _2}{\lambda }}\right)^2(2\lambda \sigma )^1\varphi _d^2e^{2z\stackrel{~}{c}(\lambda )}\mathrm{log}\left(1+\left({\displaystyle \frac{\lambda }{\lambda \lambda _2}}\right)^2(2\lambda \sigma )\varphi _d^2e^{2z\stackrel{~}{c}(\lambda )}\right)`$
$``$ $`4\lambda e^{2z\stackrel{~}{c}(\lambda )}\mathrm{log}\left(1+(2\lambda \sigma )e^{2z\stackrel{~}{c}(\lambda )}\right)`$
$``$ $`4\lambda e^{2z\left(1k\sigma \right)}\mathrm{log}\left(1+\left(2+\sigma +2\sqrt{\sigma (2k1)}\right)e^{2z}\right),z\frac{\lambda 1}{2}𝐙.`$
For the upper tail of $`T`$, as in (3.16) and with $`z>0`$, we have

$`𝐏[T>z\stackrel{~}{c}(\lambda )]`$ $``$ $`e^{2z\stackrel{~}{c}(\lambda )}(1+z\stackrel{~}{c}(\lambda ))(1+z)e^{2z\left(1k\sigma \right)}.`$
Combining these two tail estimates, we find that, for $`z>0`$,

$`\left|𝐏[T>z\stackrel{~}{c}(\lambda )]𝐏[T>z]\right|`$ $``$ $`C_2(1+z)e^{2z(1\sigma k)},`$ (5.35)
uniformly in $`k\sigma 1/2`$, for some constant $`C_2`$. Applying the bound (5.34) when $`z(62k\sigma )^1\mathrm{log}(1/k\sigma )`$ and (5.35) for all larger $`z`$, and remembering that $`T`$ has bounded density, so that the discrete nature of $`\mathrm{\Delta }_d`$ requires only a small enough correction, a bound of the required order follows. $`[]`$

Acknowledgement. We would like to thank Svante Janson for very helpful discussions concerning the comparison with .