3.1. Proofs of Lemmas 3.1, 3.2 and 3.3

To prove Lemmas 3.1, 3.2 and 3.3 we will make use of the following two preliminary results on the concentration of Binomial random variables about their mean. The first of these results is Theorem 1.3 in [Reference Bollobás7], while the second is Theorem 2.1 in [Reference Janson, Luczak and Rucinski15].

Lemma 3.4 Let $S\sim \textrm{Bin}(n,p)$ , and suppose that $np\geq 1$ and $1\leq h\leq (1-p)n/3$ . Then

\begin{equation*}\mathbb{P}(S\geq np+h)\leq \frac{(p(1-p)n)^{1/2}}{h\sqrt{2 \pi}}\exp\left\{-\frac{h^2}{2p(1-p)n}+\frac{h}{p(1-p)n}+\frac{h^3}{2(1-p)^3n^3}\right\}.\end{equation*}

We are now ready to start with the proofs of the lemmas stated in the previous section.

Proof of Lemma 3.1. We want to bound

\begin{equation*}\mathbb{P}\Big(1+\sum_{i=1}^{t}(\tau_i-1)>0\ \forall t\in [k] \Big)\end{equation*}

from above, where $\tau_i\sim \textrm{Bin}(n-i,p)$ are independent. We do this by adding extra terms to the sum $\sum_{i=1}^{t}(\tau_i-1)$ to create a random walk with identically distributed steps. To this end, let $(B_i)_{i\in [n]}$ be a sequence of independent random variables, also independent from $(\tau_i)_{i \in [n]}$ , and such that $B_i\sim \textrm{Bin}(i,p)$ for every $i \in [n]$ . Moreover, define $S_t = \sum_{i=1}^{t}B_i$ for $t\in [n]$ . Let

\begin{equation*}P = \mathbb{P}\Big(S_{k}\ge \frac{k^2}{2}p-\frac{k}{n^{1/2}}\Big).\end{equation*}

Since $S_{k} \sim \textrm{Bin}\left(k(k+1)/2,p\right)$ , an application of Lemma 3.5(b) with $t=kn^{-1/2} + kp/2$ yields that $P\geq c$ for some $c>0$ . Now using the independence of $(\tau_i)_{i\in [n]}$ and $(B_i)_{i \in [n]}$ we obtain that

\begin{equation*}\mathbb{P}\bigg(1+\sum_{i=1}^{t}(\tau_i-1)>0\ \forall t \in [k] \bigg) =P^{-1}\mathbb{P}\bigg(1+\sum_{i=1}^{t}(\tau_i-1)>0\ \forall t \in [k],\, S_{k}\ge\frac{k^2}{2}p-\frac{k}{n^{1/2}}\bigg).\end{equation*}

Setting $R_t = \sum_{i=1}^{t}(\tau_i + B_i-1)$ , we see that the last quantity is bounded from above by

\begin{align*}c^{-1}\mathbb{P}\left(1+R_t>0\ \forall t \in [k], 1+R_{k}\ge\frac{k^2}{2}p - \frac{k}{n^{1/2}}\right)\end{align*}

so noting that $\tau_i+B_i \overset{iid}{\sim}\textrm{Bin}(n,p)$ for every $i\in [n]$ completes the proof.

Proof of Lemma 3.2. Write

\begin{equation*}K=K(A,n) = \lceil An^{2/3}\rceil+1\end{equation*}

and recall that

\begin{equation*}H=H(A,n) = \Big\lceil \frac{\lceil An^{2/3}\rceil^2}{2}p - \frac{\lceil An^{2/3}\rceil}{n^{1/2}} \Big\rceil.\end{equation*}

We want to use Lemma 3.4 to bound from above the quantity

\begin{equation*}\frac{K-1}{n} \mathbb{P}(R_{K}\ge H),\end{equation*}

where we recall that $(R_t)_{t\ge 0}$ is a random walk with $R_0=0$ and i.i.d. steps each having distribution $\textrm{Bin}(n,p)-1$ . Letting $B_{j,p}$ be a binomial random variable with parameters j and p, setting $h\,{:}\,{\raise-1.5pt{=}}\, H-K\lambda/n^{1/3}$ (which is of order $A^2n^{1/3}$ since $\lambda<A/3$ ) and observing that

\begin{equation*}\frac{h}{p(1-p)nK}+\frac{h^3}{2(1-p)^3(nK)^3}=O(1),\end{equation*}

applying Lemma 3.4 we obtain

(4) \begin{align}\mathbb{P}(R_{K}\ge H) &= \mathbb{P}( B_{nK,p} \geq K+H)\nonumber\\[2pt] &=\mathbb{P}( B_{nK,p} \geq nKp+H-K\lambda/n^{1/3})\nonumber\\[2pt] &\leq \frac{(p(1-p)nK)^{1/2}}{h\sqrt{2\pi}}\exp\left\{-\frac{1}{2}\frac{h^2}{p(1-p)nK}+\frac{h}{p(1-p)nK}+\frac{h^3}{2(1-p)^3(nK)^3}\right\}\nonumber\\[2pt] &\leq c \frac{K^{1/2}}{A^2n^{1/3}}\exp\left\{-\frac{1}{2}\frac{h^2}{p(1-p)nK}\right\}\nonumber\\[2pt] &\leq \frac{c}{A^{3/2}}\exp\left\{-\frac{1}{2}\frac{h^2}{p(1-p)nK}\right\}.\end{align}

Define

\begin{equation*}x(A,n, \lambda) = \frac{h}{\sqrt{p(1-p)nK}}=\frac{H-K\lambda/n^{1/3}}{\sqrt{p(1-p)nK}}.\end{equation*}

Elementary estimates using the fact that $A=o(n^{1/12})$ and $\lambda=o(n^{1/12})$ show that

\begin{equation*}x(A,n, \lambda) = \frac{A^{3/2}}{2} - \lambda A^{1/2} + o(A^{1/2}n^{-1/6}).\end{equation*}

From (4) we therefore have, for large n,

\begin{align*}\frac{K-1}{n} \mathbb{P}(R_{K}\ge H) &\le c\frac{A}{n^{1/3}} \frac{1}{A^{3/2}}e^{-x(A,n,\lambda)^2/2}\\ &\le \frac{c}{\sqrt{A}n^{1/3}}\exp\left(-\frac{A^3}{8}+\frac{\lambda A^2}{2} - \frac{\lambda^2 A}{2} \right),\end{align*}

which completes the proof of Lemma 3.2.

Before we prove Lemma 3.3, we will need the following bound, which is an easy application of Lemma 3.5.

Lemma 3.6 Suppose that $B_{N,p}$ is a binomial random variable with parameters $N\ge 1$ and $p\in[0,1]$ . Let $C\in(0,\infty)$ be constant. Then for all $x\in(0, C(Np)^{2/3}]$ we have that

\begin{equation*}\mathbb{P}\left(B_{N,p}\ge Np + x\right)\leq c\exp\left(-\frac{x^2}{2Np}\right)\end{equation*}

where c is another finite constant.

Proof. Applying Lemma 3.5, we have

\begin{equation*}\mathbb{P}\left(B_{N,p}\ge Np + x\right) \le \exp\Big(-Np\Big[\Big(1+\frac{x}{Np}\Big)\log\Big(1+\frac{x}{Np}\Big) - \frac{x}{Np}\Big]\Big),\end{equation*}

and since $\log(1+t)>t-t^2/2$ for every $t>0$ ,

\begin{align*}\mathbb{P}\left(B_{N,p}\ge Np + x\right) &\le \exp\Big(-Np\Big[\Big(1+\frac{x}{Np}\Big)\Big(\frac{x}{Np}-\frac{x^2}{2(Np)^2}\Big)-\frac{x}{Np}\Big]\Big)\\ &= \exp\Big(-Np\Big[\frac{x^2}{2(Np)^2} - \frac{x^3}{2(Np)^3}\Big]\Big)\\ &= \exp\Big(-\frac{x^2}{2Np}+\frac{x^3}{2(Np)^2}\Big),\end{align*}

which establishes the result with $c=\exp(C^3/2)$ .

Proof of Lemma 3.3. Writing

\begin{equation*}K = K(A,n) = \lceil An^{2/3}\rceil+1\ \text{and}\ H = H(A,n) = \Big\lceil \frac{\lceil An^{2/3}\rceil^2}{2n} - \frac{\lceil An^{2/3}\rceil}{n^{1/2}} \Big\rceil,\end{equation*}

we aim to bound

\begin{equation*}\frac{1}{K}\sum_{j=H+1}^{K(n-1)}\mathbb{P}(R_{K} \ge j)\end{equation*}

from above. We first note that

(5) \begin{equation}\frac{1}{K}\sum_{j=H+1}^{K(n-1)}\mathbb{P}(R_{K} \ge j) \le \frac{1}{K}\sum_{j=H+1}^{\lfloor K^{2/3}\rfloor} \mathbb{P}(R_K\ge j) + n\mathbb{P}(R_K \ge K^{2/3}).\end{equation}

To bound the second term on the right-hand side of (5) observe that, since $A=o(n^{1/12})$ and $\lambda = o(n^{1/12})$ , we have $K\ge nKp - K^{2/3}/2$ when n is large. Thus, when n is large,

(6) \begin{align}n\mathbb{P}(R_K \ge K^{2/3}) &= n\mathbb{P}(B_{nK,p}\ge K + K^{2/3})\nonumber\\[3pt] &\leq n\mathbb{P}(B_{nK,p}\ge nKp+K^{2/3}/2).\end{align}

Using the second inequality in part (a) of Lemma 3.5 we obtain

(7) \begin{align}(6)&\le n \exp\left\{-\frac{K^{4/3}}{8(nKp+\frac{1}{6}K^{2/3})}\right\} \leq n\exp\left\{-cA^{1/3}n^{2/9}\right\}\end{align}

and for sufficiently large n we have that

\begin{align*}(7)\leq \frac{1}{A^2n^{1/3}}e^{-\frac{A^3}{8}+\frac{\lambda A^2}{2} - \frac{\lambda^2 A}{2}}.\end{align*}

Next, for the first term on the right-hand side of (5), note that

(8) \begin{align}\frac{1}{K}\sum_{j=H+1}^{\lfloor K^{2/3}\rfloor} \mathbb{P}(R_K\ge j)&=\frac{1}{K}\sum_{j=H+1}^{\lfloor K^{2/3}\rfloor} \mathbb{P}(B_{nK,p}\ge K+j)\nonumber\\[3pt] &=\frac{1}{K}\sum_{j=H+1}^{\lfloor K^{2/3}\rfloor} \mathbb{P}(B_{nK,p}\ge nKp+j-K\lambda n^{-1/3}).\end{align}

Since $A=o(n^{1/12})$ and $\lambda=o(n^{1/12})$ , we have $K\lambda n^{-1/3}=o(K^{2/3})$ , and therefore we may apply Lemma 3.6 to obtain

\begin{align*}(8)\le \frac{c}{K}\sum_{j=H+1}^{\lfloor K^{2/3} \rfloor}\exp\left\{-\frac{(j-K\lambda n^{-1/3})^2}{2nKp}\right\}\leq \frac{c}{\sqrt{K}}\mathbb{P}\left(G\ge \frac{H+1-K\lambda/n^{1/3}}{\sqrt{nKp}}\right),\end{align*}

where G denotes a Gaussian random variable with mean zero and unit variance. Recalling the standard bound $\mathbb{P}(G\geq t)\leq (t\sqrt{2\pi})^{-1}e^{-t^2/2}$ , which is valid for every $t>0$ , we obtain

\begin{equation*}\mathbb{P}\left(G\ge \frac{H+1-K\lambda/n^{1/3}}{\sqrt{nKp}}\right) \leq \frac{1}{\sqrt{2\pi}}\frac{\sqrt{nKp}}{H+1-K\lambda/n^{1/3}}\exp\Big(-\frac{(H+1-K\lambda/n^{1/3})^2}{2nKp}\Big).\end{equation*}

An easy computation reveals that

\begin{equation*}\frac{(H+1-K\lambda/n^{1/3})^2}{2nKp}\ge \frac{A^3}{8}-\lambda\frac{A^2}{2}+\lambda^2\frac{A}{2}+o(1),\end{equation*}

and consequently we obtain

\begin{align*}\frac{c}{\sqrt{K}}\mathbb{P}\left(G\ge \frac{H+1-K\lambda/n^{1/3}}{\sqrt{nKp}}\right) \le \frac{c}{A^2n^{1/3}}\exp\left\{-\frac{A^3}{8}+\lambda\frac{A^2}{2}-\lambda^2\frac{A}{2}\right\},\end{align*}

as required.

There are three places in our proof of the upper bounds stated in Theorem 1.1 where unspecified constants appear. One of these is from Lemma 3.1. The constant appearing within this result could be eliminated by amending the argument to use $k/n^\gamma$ rather than $k/n^{1/2}$ , for e.g. $\gamma=5/12$ , and strengthening our assumption on A appropriately to ensure that the error coming from Lemma 3.5 is smaller than our desired bound.

Another step requiring a more detailed analysis comes from the application of Lemma 3.4 in the proof of Lemma 3.2. Similarly to the first case above, this should be possible but would require stronger conditions on the relationship between A and $\lambda$ , or error bounds that depend on $A/\lambda$ .

Finally, a further constant appears when we apply Corollary 2.4 in (3). Finding the correct constant here would require a different approach; either an improvement to Corollary 2.4, or an attempt to apply other results about random walks to $(R_t)_{t\ge0}$ . The latter option would be complicated by the fact that the step distribution of $R_t$ depends on n.

4.1. Rearranging Bernoullis and applying the ballot theorem: proof of Proposition 4.3

We first introduce a technical result which will be used to transform $(R_t)_{t\in [T_1]}$ into a process with i.i.d. increments.

The reader can think of the $I_j^i$ as Bernoulli(p)-distributed, so that $X_i\sim \textrm{Bin}(N-i,p)$ and $\tilde X_i\sim \textrm{Bin}(N-(L+1)/2,p)$ . The idea behind the proof is that $X_1$ has more summands than $X_L$ , so if we transfer some of the summands from $X_1$ to $X_L$ , we do not change the value of $\sum_{i=1}^L X_i$ but we decrease $X_1$ . Then we move on to $X_2$ and transfer some of its summands to $X_{L-1}$ , which decreases $\sum_{i=1}^2 X_i$ without changing $\sum_{i=1}^L X_i$ ; and so on. We postpone the details until Section 4.3.

Before we can proceed with the proof of Proposition 4.3, we need one more tool. We can use Lemma 4.5 to transform $(R_t)_{t\in [T_1]}$ into a process with i.i.d. increments, but in order to apply the generalised ballot theorem, Theorem 2.1, we need our increments also to have mean zero and for their distribution not to depend on n. The following lemma is slightly more general than we will need.

Lemma 4.6 Take $n\in\mathbb{N}$ , $h_n\ge 0$ , $a_n\in(-1,\infty)$ satisfying $na_n\in\mathbb{Z}$ , $b_n\in(-1,n-1)$ and $t_n\in\mathbb{N}$ . Suppose that $M_t = 1 + \sum_{i=1}^t (W_i-1)$ where the $W_i$ are independent $\textrm{Bin}(n(1+a_n),(1+b_n)/n)$ random variables. Let $\mu_n = (1+a_n)(1+b_n)$ . Then

\begin{multline*}\mathbb{P}\big(M_t>0\,\,\,\,\forall t\in [t_n], \, M_{t_n}\in[h_n,2h_n]\big)\\ \ge (\mu_n\wedge 1)^{2h_n} \mu_n^{t_n-1} e^{(1-\mu_n)t_n}\mathbb{P}\big(\hat M_t > 0 \,\,\,\,\forall t\in[t_n],\, \hat M_{t_n}\in[h_n,2h_n]\big) - \frac{t_n}{n}(1+a_n)(1+b_n)^2\end{multline*}

where $\hat M_t= 1+\sum_{i=1}^{t}(\hat W_i-1)$ , and $(\hat W_i)_{i=1}^{t_n}$ is a sequence of independent Poisson random variables with mean one.

We delay the proof, which uses a fairly standard Poisson approximation for the binomial distribution and then a simple change of measure to remove the drift, until Section 4.4 and proceed with the proof of Proposition 4.3.

Proof of Proposition 4.3. As previously mentioned, we want to bound

\begin{equation*}\mathbb{P}\left(R_t>0\ \forall t\in [T_1], R_{T_1}\in [H,2H]\right)\end{equation*}

by means of the generalised ballot theorem, Theorem 2.1. To this end, we first need to turn the process $(R_t)_{t\in [T_1]}$ into a random walk with i.i.d. steps having mean zero. In order to obtain identically distributed steps we will make use of Lemma 4.5.

Recall that $H=\lceil n^{1/3}/A\rceil$ and $R_t=1+\sum_{i=1}^{t}(\delta_i-1)$ , where each $\delta_i$ is the sum of $n-\lfloor n^{2/5} \rfloor -i$ i.i.d. Ber(p) random variables. It follows from Lemma 4.5, with $N=n-\lfloor n^{2/5}\rfloor$ and $L=T_1$ , that there exists a sequence $(\tilde \delta_i)_{i\in [T_1]}$ of i.i.d random variables with $\tilde \delta_i\sim \textrm{Bin}(n-\lfloor n^{2/5}\rfloor - (T_1+1)/2,p)$ for which, setting $\tilde R_t = 1+\sum_{i=1}^{t}(\tilde \delta_i-1)$ , we obtain

(20) \begin{equation}\mathbb{P}\left(R_t>0\ \forall t\in [T_1],\, R_{T_1}\in [H,2H]\right) \geq \mathbb{P}\left(\tilde R_t>0\ \forall t\in [T_1],\, \tilde R_{T_1}\in [H,2H]\right).\end{equation}

In order to evaluate the probabilities appearing in the above sum by means of the generalised ballot theorem, we still have to turn $(\tilde R_t)_{t\in [T_1]}$ into a process whose increments have mean zero. We do this by applying Lemma 4.6 with $h_n=H$ , $t_n=T_1=2\lfloor n^{2/3}/A^2\rfloor-1$ , $a_n = -\lfloor n^{2/5}\rfloor/n - (T_1+1)/(2n)$ and $b_n = \lambda/n^{1/3}$ . Since $|\lambda|\le A/3$ , it is easy to see that there exists a constant $c>0$ (not depending on n) such that

\begin{equation*}(\mu_n\wedge 1)^{2h_n} \ge c.\end{equation*}

Also, using the inequality $1+x\ge e^{x-x^2}$ valid for $x\ge -1/2$ , for sufficiently large n we have

\begin{equation*}\mu_n^{t_n-1} e^{(1-\mu_n)t_n} = \mu_n^{-1}(1+(\mu_n-1))^{t_n} e^{(1-\mu_n)t_n} \ge \mu_n^{-1} e^{-(\mu_n-1)^2 t_n} \ge c\end{equation*}

for some constant $c>0$ . Finally, since

\begin{equation*}\frac{t_n}{n}(1+a_n)(1+b_n)^2 \asymp \frac{t_n}{n} \asymp \frac{1}{A^2 n^{1/3}},\end{equation*}

from Lemma 4.6 we obtain that

(21) \begin{align}&\mathbb{P}\left(\tilde R_t>0\ \forall t\in [T_1],\, \tilde R_{T_1}\in [H,2H]\right)\nonumber\\ &\quad \ge c\mathbb{P}\left(\hat R_t>0\ \forall t\in [T_1],\, \hat R_{T_1}\in [H,2H]\right) - \frac{C}{A^2 n^{1/3}} \end{align}

for some constants $c>0$ and $C<\infty$ , where $\hat R_t = 1+\sum_{i=1}^t (\hat \delta_i-1)$ and $(\hat\delta_i)_{i=1}^{T_1}$ is a sequence of independent Poisson random variables with parameter 1.

We are now in a position to apply Theorem 2.1. Recalling that $H = \lceil n^{1/3}/A\rceil$ and $T_1 = 2\lfloor n^{2/3}/A^2\rfloor-1$ , for all $k\in[H-1,2H-1]$ we have $k\leq 2H=O(\sqrt{T_1})$ . We can therefore conclude from Theorem 2.1 that

\begin{align*}&\mathbb{P}\left(\hat R_t>0\ \forall t\in [T_1],\, \hat R_{T_1}\in [H,2H]\right) \\ &\quad \ge \mathbb{P}\left(\hat R_t-1>0\ \forall t\in [T_1],\, \hat R_{T_1}-1\in [H-1,2H-1]\right) \\ &\quad \ge c\sum_{k=H-1}^{2H-1} \frac{k+1}{T_1^{3/2}},\end{align*}

which is of order $An^{-1/3}$ . Substituting this bound into (21) gives

\begin{equation*}\mathbb{P}\left(\tilde R_t>0\ \forall t\in [T_1],\, \tilde R_{T_1}\in [H,2H]\right) \ge \frac{cA}{n^{1/3}} - \frac{C}{A^2 n^{1/3}}.\end{equation*}

Taking A sufficiently large that the first term dominates, and then recalling (20), gives theresult.

4.2. Adding independent binomials and approximating with Brownian motion: Proof of Proposition 4.4

Recall that $R_t = 1+\sum_{i=1}^t (\delta_i-1)$ where $(\delta_i)_{i=1}^{T_2}$ is a sequence of independent $\textrm{Bin}(n-K-i,p)$ random variables. Recall also that $H=\lceil n^{1/3}/A\rceil$ , $K=\lfloor n^{2/5}\rfloor$ , $T_1 = 2\lfloor n^{2/3}/A^2\rfloor -1$ and $T_2 = \lceil An^{2/3}\rceil$ . Throughout this section we write $T = T_2-T_1$ .

Our first task in this section is to replace $R_t$ with a sum of i.i.d. random variables. We do this by adding an independent $\textrm{Bin}(K+i,p)$ random variable to $\delta_i$ for each i, and checking that the sum of these additional random variables cannot be too large using Lemma 3.5.

Lemma 4.7 For $t\in[0,\infty)$ , define

\begin{equation*}g(t) = -\frac{n^{1/3}}{2A} + \frac{9t}{A^2n^{1/3}} + \frac{pt^2}{2}.\end{equation*}

Then there exists $c>0$ such that for all large n,

\begin{equation*}\mathbb{P}(R_t>0\;\; \forall t\in [\![ T_1, T_2]\!] \,|\, R_{T_1}=H ) \ge \mathbb{P}\big(S_t > g(t)\;\; \forall t\in[\![ 1,T]\!]\big) - T e^{-cAn^{1/6}},\end{equation*}

where $S_t = \sum_{i=1}^t (\Delta_i-1)$ , and $(\Delta_i)_{i=1}^{T}$ is a sequence of independent Bin(n,p) random variables.

The proof of Lemma 4.7 is in Section 4.3. Next, in order to apply a Brownian approximation to our random walk, we would like the step distribution not to depend on n.

Lemma 4.8 For $t\in[0,\infty)$ , define

\begin{equation*}\gamma(t) = -\frac{n^{1/3}}{4A} + \frac{9t}{A^2n^{1/3}} + \frac{pt^2}{2}.\end{equation*}

Let g and $(S_t)_{t=0}^T$ be as in Lemma 4.7. Then there exist constants $c,C\in(0,\infty)$ such that

\begin{align*}&\mathbb{P}\big(S_t > g(t)\;\; \forall t\in[\![ 1,T]\!]\big)\\ &\ge c e^{\lambda A^2/2 - \lambda^2 A/2}\mathbb{P}\big(\hat S_t > \gamma(t)\;\;\forall t\in[\![ 1,T]\!],\, \hat S_{T}\le\gamma(T)+\tfrac{3n^{1/3}}{8A}\big) - C\exp\Big(- \frac{n^{1/3}}{4A}\Big),\end{align*}

where $\hat S_t = \sum_{i=1}^t( \hat\Delta_i-1)$ and $(\hat\Delta_i)_{i=1}^{T}$ is a sequence of independent Poisson random variables of parameter 1.

Again we delay the proof, which is similar to the proof of Lemma 4.6, until Section 4.4 and proceed with the proof of Proposition 4.4. As mentioned above, our strategy is to approximate the random walk $(\hat S_t)_{t=0}^{T}$ appearing in Lemma 4.8 with Brownian motion. We will use an accurate bound of Komlós, Major and Tusnády due to its ease of application, although we will not really need the additional precision gained over the earlier result of Strassen [Reference Strassen31, Theorem 1.5]. The following rephrasing of the original theorem is from [Reference Chatterjee9].

Theorem 4.9 (Komlós et al. [Reference Komlós, Major and Tusnády18]).Let $(\xi_i)_{i\geq 1}$ be a sequence of i.i.d. random variables with $\mathbb{E}[\xi_1]=0$ and $\mathbb{E}[\xi_1^{2}]=1$ . Suppose that there exists $\theta>0$ such that $\mathbb{E}\left[e^{\theta |\xi_1|}\right]<\infty$ . For each $k\in\{0\}\cup\mathbb{N}$ , let $U_k = \sum_{i=1}^k \xi_i$ . Then for every $N\in \mathbb{N}$ it is possible to construct a version of $(U_k)_{k=0}^N$ and a standard Brownian Motion $(B_s)_{s\in[0,N]}$ on the same probability space such that, for every $x\geq 0$ ,

\begin{equation*}\mathbb{P}\left(\max_{k\leq N}\left|U_k-B_k\right|>M\log N + x\right)\leq C e^{-c x},\end{equation*}

where M, C and $c>0$ do not depend on N.

Applying this with $N=T$ and $U_k = \hat S_k$ , we immediately obtain the following corollary.

Corollary 4.10 Suppose that $\hat S_t = \sum_{i=1}^t \hat{\Delta}_i$ , where $(\hat \Delta_i)_{i=1}^{T}$ is a sequence of independent Poisson random variables of parameter 1, and that $(B_s)_{s\ge 0}$ is a standard Brownian motion. There exist constants $c,C\in(0,\infty)$ such that for any $x_n\ge 0$ and any function $\gamma:[0,\infty)\to\mathbb{R}$ ,

\begin{align*}\mathbb{P}\big(\hat S_t &> \gamma(t)\;\;\forall t\in[\![ 1,T]\!],\, \hat S_{T}\le\gamma(T)+\tfrac{3n^{1/3}}{8A}\big)\\ &\ge \mathbb{P}\big(B_s > \gamma(s) + M\log T + x_n\;\;\forall s\in[0,T],\, B_{T}\le\gamma(T)+\tfrac{3n^{1/3}}{8A} - M\log T - x_n\big) - C e^{-c x_n}.\end{align*}

We have now reduced our task to bounding the probability that a Brownian motion remains above a curve up to time T and is not too far above the curve at time T.

Proposition 4.11 There exists a constant $c>0$ such that for any $x_n$ satisfying $A^3\ll x_n \ll n^{1/3}/A$ , any constant M (not depending on n) and $\gamma$ as in Lemma 4.8, for large n,

\begin{equation*}\mathbb{P}\big(B_s > \gamma(s) + M\log T + x_n\;\;\forall s\in[0,T],\, B_{T}\le\gamma(T)+\tfrac{3n^{1/3}}{8A} - M\log T - x\big) \ge \frac{c}{A^{3/2}}e^{-A^3/8}.\end{equation*}

The proof of Proposition 4.11 involves considering two time intervals, $[0,T/2]$ and $[T/2,T]$ , and approximating $\gamma(T)$ by a straight line on each of these intervals. We carry out the details in Section 4.5.

We now have all the ingredients to prove Proposition 4.4 and therefore Theorem 1.1.

Proof of Proposition 4.4. We simply combine Lemmas 4.7 and 4.8, Corollary 4.10 and Proposition 4.11.

4.3. Proofs of Lemmas 4.1, 4.2, 4.5 and 4.7: creating i.i.d. sequences

We first prove Lemma 4.1, which replaces $\eta_i$ , the number of unseen vertices that become active at the ith step of the exploration process, with an independent Binomial random variable that does not depend on the history of the exploration process.

Proof of Lemma 4.1. From the description of the exploration process provided at the beginning of Section 3, recall that $u_t$ is the vertex that is explored at step t. Let us denote by $\mathcal{A}^*_t$ the set of unseen vertices that become active at step $t-1$ of the process (with $\mathcal A^*_1 = \{u_1\}$ ), and let $\mathcal A_t = \bigcup_{i=0}^t \mathcal A^*_i$ , the set of all active or explored vertices after step $t-1$ . Also, write $X^t_v$ for the indicator that $u_t$ is a neighbour of vertex v.

For each $t=1,2,\ldots,n-K$ , if $|\mathcal A_t| < K+t$ then let $\mathcal B^*_t$ be any subset of the vertices [n] such that

• $\mathcal A^*_t \subset \mathcal B^*_t$ ;

• $\mathcal B^*_t \cap \mathcal A_{t-1} = \emptyset$ ;

• $\big|\mathcal B^*_t \cup \mathcal A_{t-1}\big| = K+t$ .

If $|\mathcal A_t| \ge K+t$ then let $\mathcal B^*_t = \mathcal A^*_t$ . Then let

\begin{equation*}r_t = \big| \mathcal B^*_t \cup \mathcal A_{t-1}\big| - K - t \ge 0.\end{equation*}

Take a sequence $\hat X_1^t, \hat X_2^t,\ldots$ of independent Bernoulli random variables of parameter p, also independent of everything else.

Note that

\begin{equation*}\eta_t = \sum_{v\not\in\mathcal A_t} X^t_v\end{equation*}

and define

\begin{equation*}\delta_t = \sum_{v\not\in\mathcal B^*_t\cup\mathcal A_{t-1}} X^t_v + \sum_{i=1}^{r_t} \hat X^t_j.\end{equation*}

Then, since

\begin{equation*}\big|\big(\mathcal B^*_t\cup\mathcal A_{t-1}\big)^c\big| + r_t = n - K - t,\end{equation*}

and the random variables $\{X^i_v \,{:}\, v\in \mathcal A_{i-1}^c\}$ are independent and independent of $\{X^j_v \,{:}\, v\in \mathcal A_{j-1}^c\}$ for any $j\neq i$ , we see that $(\delta_t)_{t=1}^{n-K}$ is a sequence of independent random variables such that $\delta_t \sim \textrm{Bin}(n-K-t,p)$ .

We also observe that if $|\mathcal A_t| < K+t$ , then $|\mathcal B^*_t \cup \mathcal A_{t-1}| = K+t$ and so $r_t=0$ . Since we also have $\mathcal A^*_t \subset \mathcal B^*_t$ , we see that if $|\mathcal A_t| < K+t$ then $\eta_t \ge \delta_t$ . Thus, recalling that $\tau_0$ denotes the first time at which the set of active vertices is empty and since $\{\tau_0>T_2\}=\{1+\sum_{i=1}^{t}(\eta_{i}-1)>0\ \forall t\in [T_2]\}$ we obtain

\begin{align*}\mathbb{P}\left(|\mathcal{C}(v)|>T_2\right) &= \mathbb{P}\Big(1+\sum_{i=1}^{t}(\eta_i - 1)>0 \forall t\in [T_2]\Big)\\ &\ge \mathbb{P}\Big(1+\sum_{i=1}^{t}(\eta_i - 1)>0 \forall t\in [T_2]\text{ and } |\mathcal A_t| < K+t \forall t\in [\tau_0 \wedge T_2]\Big)\\ &\ge \mathbb{P}\Big(1+\sum_{i=1}^{t}(\delta_i - 1)>0 \forall t\in [T_2] \text{ and } |\mathcal A_t| < K+t \forall t\in [\tau_0 \wedge T_2]\Big),\end{align*}

where the last inequality follows from the fact that on the event $\{|\mathcal{A}_t|<K+t\forall t\in [T_2]\}$ we have $\eta_{t}\geq \delta_t$ for $t\in [T_2]$ (and $\tau_0\wedge T_2=T_2$ on $\{1+\sum_{i=1}^{t}(\eta_{i}-1)>0\ \forall t\in [T_2]\}$ ). Now

\begin{align*}&\mathbb{P}\Big(1+\sum_{i=1}^{t}(\delta_i - 1)>0 \forall t\in [T_2] \text{ and } |\mathcal A_t| < K+t \forall t\in [\tau_0 \wedge T_2]\Big)\\ &\ge \mathbb{P}\Big(1+\sum_{i=1}^{t}(\delta_i - 1)>0 \forall t\in [T_2]\Big) - \mathbb{P}\Big(\exists t\in [\tau_0\wedge T_2] : |\mathcal A_t| \ge K+t\Big).\end{align*}

Since $|\mathcal A_t| = Y_t + t$ , the result follows.

Next we prove Lemma 4.2, which ensures that the probability that the number of active vertices becomes too large is small.

Proof of Lemma 4.2. Let $\zeta_i\overset{i.i.d.}{\sim}\textrm{Bin}(n,p)$ . A union bound gives

(22) \begin{align}\nonumber\mathbb{P}\left(\exists i\leq \tau_0\wedge T_2\,{:}\,Y_i\geq \lfloor n^{2/5}\rfloor \right) &\leq \sum_{i=1}^{T_2}\mathbb{P}\left(Y_i\geq \lfloor n^{2/5}\rfloor,i\leq \tau_0\right)\\ &\leq\sum_{i=1}^{T_2}\mathbb{P}\bigg(1+\sum_{j=1}^{i}(\zeta_j-1)\geq \lfloor n^{2/5}\rfloor,i\leq \tau_0\bigg)\end{align}

(23) \begin{align}&\leq \sum_{i=1}^{T_2}\mathbb{P}\bigg(1+\sum_{j=1}^{i}(\zeta_j-1)\geq \lfloor n^{2/5}\rfloor\bigg).\end{align}

Denoting by $B_{N,q}$ a binomial random variable with parameters N and q, by Lemma 3.5 we see that for $i\in [T_2]$ ,

(24) \begin{align}\nonumber\mathbb{P}\bigg(1+\sum_{j=1}^{i}(\zeta_j-1)\geq \lfloor n^{2/5}\rfloor\bigg)&=\mathbb{P}\left(B_{in,p}\geq inp-i\lambda n^{-1/3}+\lfloor n^{2/5}\rfloor-1\right)\\ &\leq \mathbb{P}\left(B_{in,p}\geq inp+ n^{2/5}\left(1-c\frac{A|\lambda|}{n^{1/15}}\right)\right).\end{align}

Now, $A=o(n^{1/30})$ and $|\lambda|\leq A/3$ , so $A|\lambda|=o\left(n^{1/15}\right)$ and hence for large enough n we obtain

(25) \begin{align}(24)\leq \mathbb{P}\left(B_{in,p}\geq inp+ n^{2/5}/2 \right)\leq \exp\left\{-\frac{n^{4/5}/4}{2inp+\frac{1}{3}n^{2/5}}\right\}.\end{align}

Since $i\leq T_2$ we see that (25) $\leq e^{-cn^{2/15}/A}$ for some positive constant $c>0$ . Finally, since $A,\lambda=o(n^{1/30})$ as $n\rightarrow \infty$ we conclude that

\begin{align*} e^{-cn^{2/15}/A}=o\left(A^{-1/2}n^{-1/3}e^{-\frac{A^3}{8}+\frac{\lambda A^2}{2}-\frac{\lambda^2A}{2}}\right).\\[-35pt]\end{align*}

Lemma 4.5 involves rearranging Bernoulli random variables to produce an i.i.d. sequence.

Proof of Lemma 4.5. Recall the convention that the empty sum is zero. By hypothesis,

(26) \begin{equation}X_i=\sum_{j=1}^{N-i}I_j^{i},\end{equation}

where $(I_j^{i})_{i,j\geq 1}$ are i.i.d. non-negative random variables. Let $\ell = (L+1)/2$ ; recall that L is odd, so $\ell\in \mathbb{N}$ . Define

\begin{equation*}\tilde{X}_i = \left\{ \begin{aligned}& \sum_{j=1}^{N-\ell}I_j^{i}, && 1\leq i\leq \ell\\ & \sum_{j=1}^{N-i}I_j^{i} + \sum_{j=N-\ell+1}^{N-(L+1-i)}I_j^{L+1-i}, && \ell<i\leq L.\\\end{aligned}\right.\end{equation*}

Observe that $(\tilde{X}_i)_{i=1}^{L}$ is a sequence of i.i.d. random variables and $\tilde{X}_i\overset{d}{=}\sum_{j=1}^{N-\ell}I_j^{1}$ , $1\leq i\leq L$ . Next we claim that

(27) \begin{equation}\sum_{i=1}^{t}\tilde{X}_i\leq \sum_{i=1}^{t}X_i\end{equation}

for all $1\leq t\leq L$ . To see this, observe first that when $1\leq t\leq \ell$ we have that

\begin{align*}\sum_{i=1}^{t}\tilde{X}_i=\sum_{i=1}^{t}\sum_{j=1}^{N-\ell}I_j^{i}\leq \sum_{i=1}^{t}\sum_{j=1}^{N-i}I_j^{i}= \sum_{i=1}^{t}X_i.\end{align*}

Next, for $\ell<t\leq L$ we have that

\begin{equation*}\sum_{i=1}^{t}\tilde{X}_i = \sum_{i=1}^{\ell}\tilde{X}_i +\sum_{i=\ell+1}^{t}\tilde{X}_i =\sum_{i=1}^{\ell}\sum_{j=1}^{N-\ell}I_j^{i}+\sum_{i=\ell+1}^{t}\sum_{j=1}^{N-i}I_j^{i}+\sum_{i=\ell+1}^{t}\sum_{j=N-\ell+1}^{N-(L+1-i)}I_j^{L+1-i}.\end{equation*}

Making the change of variable $k=L+1-i$ , we see that

\begin{equation*}\sum_{i=\ell+1}^{t}\sum_{j=N-\ell+1}^{N-(L+1-i)}I_j^{L+1-i} = \sum_{k=L+1-t}^{\ell-1}\sum_{j=N-\ell+1}^{N-k}I_j^{k} = \sum_{k=L+1-t}^{\ell}\sum_{j=N-\ell+1}^{N-k}I_j^{k},\end{equation*}

where the last equality follows from the fact that the term corresponding to $k=\ell$ is zero.

Therefore

(28) \begin{align}\sum_{i=1}^{t}\tilde{X}_i &= \sum_{i=1}^{\ell}\sum_{j=1}^{N-\ell}I_j^{i}+\sum_{i=\ell+1}^{t}\sum_{j=1}^{N-i}I_j^{i}+\sum_{i=L+1-t}^{\ell}\sum_{j=N-\ell+1}^{N-i}I_j^{i}\end{align}

\begin{align}&\le\sum_{i=1}^{\ell}\sum_{j=1}^{N-\ell}I_j^{i}+\sum_{i=\ell+1}^{t}\sum_{j=1}^{N-i}I_j^{i}+\sum_{i=1}^{\ell}\sum_{j=N-\ell+1}^{N-i}I_j^{i}\nonumber\\ &= \sum_{i=1}^t X_i\nonumber\end{align}

as claimed. The second statement of the lemma simply follows by taking $t=L$ in (28), in which case the subsequent inequality is an equality.

Lemma 4.7 provides an alternative way of producing i.i.d. sequences of Binomial random variables, by adding independent binomials to the original sequence.

Proof of Lemma 4.7. Recall that $R_t=1+\sum_{i=1}^{t}(\delta_i-1)$ . As we did in Section 4.2, write $T=T_2-T_1$ . Let $(L_i)_{i\in [T_2]}$ be a sequence of independent random variables, also independent of $(\delta_i)_{i\in [T_2]}$ and such that $L_i\sim \textrm{Bin}(K+i,p)$ . Then, setting

(29) \begin{equation}S_t = \sum_{i=T_1+1}^{T_1+t}(\delta_i+L_i-1),\end{equation}

we see that $\delta_i+L_i \overset{i.i.d.}{\sim}\textrm{Bin}(n,p)$ . Let $\mathcal L_t = \sum_{i=T_1+1}^{T_1+t}L_i$ . Then for any $f\,{:}\,\mathbb{N}\to\mathbb{R}$ ,

(30) \begin{align}\mathbb{P}(R_t>0 \;\;\forall t\in [\![ T_1, T_2]\!] \,|\, R_{T_1}=H)&= \mathbb{P}\big(R_{T_1+t}-R_{T_1} > -H \;\;\forall t\in[T] \big)\nonumber\\[3pt] &= \mathbb{P}\big(S_t - \mathcal L_t > -H \;\; \forall t\in[T] \big)\nonumber\\[3pt] &\ge \mathbb{P}\big(S_t > \mathcal L_t - H \;\; \forall t\in[T],\, \mathcal L_t \le f(t)+H\;\;\forall t\in[T] \big)\nonumber\\[3pt] &\ge \mathbb{P}\big(S_t > f(t)\;\;\forall t\in[T]\big) - \mathbb{P}\big(\exists t\in[T] : \mathcal L_t > f(t)+H\big).\end{align}

We now let $f(t) = \mathbb{E}[\mathcal L_t] + \frac{A^{1/2}}{n^{5/12}}(T_1+t) - H$ and aim to show that

(31) \begin{equation}\mathbb{P}\big(\exists t\in[T] \,{:}\, \mathcal L_t > f(t)+H\big) \le T e^{-cAn^{1/6}}.\end{equation}

Indeed, a union bound gives

\begin{equation*}\mathbb{P}\big(\exists t\in[T] \,{:}\, \mathcal L_t > f(t)+H\big) \le \sum_{t=1}^{T} \mathbb{P}\Big( \mathcal L_t \ge \mathbb{E}[\mathcal L_t] + \frac{A^{1/2}}{n^{5/12}}(T_1+t) \Big),\end{equation*}

and then applying Lemma 3.5 yields

(32) \begin{equation}\mathbb{P}\big(\exists t\in[T] \,{:}\, \mathcal L_t > f(t)+H\big) \le \sum_{t=1}^{T} \exp\bigg(-\frac{A(T_1+t)^2 n^{-5/6}}{2(K+T_1+1/2)tp+t^2p+\frac{2A^{1/2}(T_1+t)}{3n^{5/12}}}\bigg).\end{equation}

One may easily check that for some finite constant C, we have

\begin{equation*}2(K+T_1+1/2)tp \le CT_1 t/n \le C(T_1+t)^2/n,\end{equation*}

\begin{equation*}t^2p \le Ct^2/n \le C(T_1+t)^2/n\end{equation*}

and

\begin{equation*}\frac{2A^{1/2}(T_1+t)}{3n^{5/12}} \le C\frac{T_1}{n}(T_1+t)\le C(T_1+t)^2/n.\end{equation*}

Thus, for some $c>0$ ,

\begin{equation*}\exp\bigg(-\frac{A(T_1+t)^2 n^{-5/6}}{2(K+T_1+1/2)tp+t^2p+\frac{2A^{1/2}(T_1+t)}{3n^{5/12}}}\bigg) \le \exp(-cAn^{1/6})\end{equation*}

which combines with (32) to give (31).

Substituting (31) into (30) proves the Lemma with f in place of g. It therefore suffices to check that $f(t)\le g(t)$ for all t when n is large. This holds since

\begin{equation*}\mathcal L_t\sim \textrm{Bin}\bigg(\sum_{i=T_1+1}^{T_1+t}(K+i),p\bigg) = \textrm{Bin}\big((K+T_1)t + t(t+1)/2,p\big),\end{equation*}

and we have

\begin{equation*}p(K+T_1+1/2)t \le \frac{8t}{n^{1/3}A^2},\;\; A^{1/2}n^{-5/12}T_1 \le \frac{n^{1/3}}{2A} \;\;\text{and}\;\; A^{1/2}n^{-5/12}t \le \frac{t}{n^{1/3}A^2}.\end{equation*}

These estimates show that $f(t)\le g(t)$ and complete the proof.

4.4. Proofs of Lemmas 4.6 and 4.8: Poisson approximation and a change of measure

The proof of Lemma 4.6 uses two standard ingredients: a coupling between Binomial and Poisson random variables, and a change of measure to remove the drift from a random walk.

Proof of Lemma 4.6. Note that $\mathbb{E}[W_i] = (1+a_n)(1+b_n) = \mu_n$ for each i. By [Reference van der Hofstad32, Theorem 2.10] we can construct a coupling between $(W_i)_{i\in\mathbb{N}}$ and a sequence $W_i^{\prime}$ of i.i.d. Poisson random variables with parameter $\mu_n$ , such that

\begin{equation*}\mathbb{P}(W_i\neq W_i^{\prime}) \le \sum_{i=1}^{n(1+a_n)} \Big(\frac{1+b_n}{n}\Big)^2 = \frac{(1+a_n)(1+b_n)^2}{n}.\end{equation*}

Let $M_t^{\prime} = 1 + \sum_{i=1}^t (W_i^{\prime}-1)$ . Then

(33) \begin{align*}\mathbb{P}\big(M_t>0\,\,\,\,\forall t\in[t_n], \, M_{t_n}&\in[h_n,2h_n]\big)\\ &\ge \mathbb{P}\big(M_t^{\prime}>0\,\,\,\,\forall t\in[t_n], \, M_{t_n}^{\prime}\in[h_n,2h_n]\big) - \mathbb{P}\big(\exists i\in[t_n] : W_i\neq W_i^{\prime}\big),\end{align*}

and a union bound gives that

(34) \begin{equation}\mathbb{P}\big(\exists i\in[t_n] : W_i\neq W_i^{\prime}\big) \le t_n\frac{(1+a_n)(1+b_n)^2}{n}.\end{equation}

We now seek to remove the drift from the sequence $M^{\prime}_t$ by using a change of measure. Define a new probability measure $\mathbb{Q}$ by setting, for $B\in\sigma(W_1^{\prime},\ldots,W_{t_n}^{\prime})$ ,

\begin{equation*}\mathbb{Q}(B) = \mathbb{E}\bigg[\unicode{x1D7D9}_B \prod_{i=1}^{t_n} \mu_n ^{-W_i^{\prime}}\bigg] \mathbb{E}\Big[\mu_n^{- W_1^{\prime}}\Big]^{-t_n} = \mathbb{E}\left[\unicode{x1D7D9}_B\mu_n^{-\sum_{i=1}^{t_n}W^{\prime}_i}\right]\mathbb{E}\Big[\mu_n^{- W_1^{\prime}}\Big]^{-t_n}.\end{equation*}

Note that $\sum_{i=1}^{t_n} W^{\prime}_i = M_{t_n}^{\prime}+t_n-1$ and, since $W_1^{\prime}$ is Poisson with parameter $\mu_n$ , $\mathbb{E}\big[\mu_n^{- W_1^{\prime}}\big]= e^{\mu_n(1/\mu_n-1)} = e^{1-\mu_n}$ . Thus

(35) \begin{equation}\mathbb{Q}(B) = \mathbb{E}\Big[\unicode{x1D7D9}_B \mu_n^{- M_{t_n}^{\prime}-t_n+1}\Big] e^{(\mu_n-1)t_n}.\end{equation}

We write $\mathbb{E}_\mathbb{Q}$ for expectation with respect to the probability measure $\mathbb{Q}$ . It is straightforward to check that, under $\mathbb{Q}$ , the $W_i^{\prime}$ are independent Poisson random variables of parameter 1.

By the definition of $\mathbb{Q}$ , we have

\begin{align*}&\mathbb{P}\big(M_t^{\prime}>0\,\,\forall t\in[\![ 0,t_n]\!], \, M_{t_n}^{\prime}\in[h_n,2h_n]\big)\\[3pt] &= \mathbb{E}_\mathbb{Q}\Big[\mu_n^{M^{\prime}_{t_n}+t_n-1} \unicode{x1D7D9}_{\{M_t^{\prime}>0\,\forall t\in[\![ 0,t_n]\!], \, M_{t_n}^{\prime}\in[h_n,2h_n]\}}\Big]e^{(1-\mu_n)t_n}\\[3pt] &\ge (\mu_n\wedge 1)^{2h_n} \mu_n^{t_n-1}\mathbb{Q}\big(M_t^{\prime}>0\,\,\forall t\in[\![ 0,t_n]\!], \, M_{t_n}^{\prime}\in[h_n,2h_n]\big)e^{(1-\mu_n)t_n}.\end{align*}

Since $(W_i^{\prime})_{i=1}^{t_n}$ is a sequence of independent Poisson random variables of parameter 1 under $\mathbb{Q}$ , substituting this and (34) into (33) gives the result.

The proof of Lemma 4.8 is similar to that of Lemma 4.6, but we will need to delve deeper into the details of the coupling between the Binomial and Poisson random variables.

Proof of Lemma 4.8. We follow almost the same proof as Lemma 4.6, noting that $\mathbb{E}[\Delta_i] = np$ for each i. By [32, Theorem 2.10] we can couple $(\Delta_i)_{i=1}^T$ with a sequence $(\Delta_i^{\prime})_{i=1}^T$ of i.i.d. Poisson random variables with parameter np. Write $S_t^{\prime} = \sum_{i=1}^t (\Delta_i^{\prime}-1)$ . Then we obtain

(36) \begin{align}\nonumber&\mathbb{P}\big(S_t>g(t)\,\,\,\,\forall t\in[\![ 0,T]\!]\big)\\[3pt] \nonumber&\geq \mathbb{P}\big(S_t>g(t)\,\,\forall t\in[\![ 0,T]\!],\, S^{\prime}_t>g(t)+\tfrac{n^{1/3}}{4A}\,\,\forall t\in[\![ 0,T]\!]\big) \\[3pt] \nonumber&=\mathbb{P}\big(S_t^{\prime}>g(t) + \tfrac{n^{1/3}}{4A}\,\,\,\,\forall t\in[\![ 0,T]\!]\big)\\[3pt] \nonumber&\quad -\mathbb{P}\big(S_t^{\prime}>g(t) + \tfrac{n^{1/3}}{4A}\,\,\,\,\forall t\in[\![ 0,T]\!],\, \exists t \in [\![ 0,T]\!] \,{:}\, S_t\leq g(t)\big)\\[3pt]&\ge \mathbb{P}\big(S_t^{\prime}>g(t) + \tfrac{n^{1/3}}{4A}\,\,\,\,\forall t\in[\![ 0,T]\!]\big) - \mathbb{P}\Big(\max_{t\le T}|S_t-S_t^{\prime}|> \tfrac{n^{1/3}}{4A}\Big),\end{align}

where the last inequality follows from the fact that

\begin{align*}&\mathbb{P}\big(S_t^{\prime}>g(t) + \tfrac{n^{1/3}}{4A}\,\,\,\,\forall t\in[\![ 0,T]\!],\,\exists t \in [\![ 0,T]\!] \,{:}\, S_t\leq g(t)\big)\\[3pt] &\quad \leq \mathbb{P}(\exists t \in [\![ 0,T]\!] \,{:}\, |S^{\prime}_t-S_t|>\tfrac{n^{1/3}}{4A})=\mathbb{P}\big(\max_{t\le T}|S_t-S_t^{\prime}|> \tfrac{n^{1/3}}{4A}\big).\end{align*}

To estimate the last probability, we see that

(37) \begin{equation}\mathbb{P}\Big(\max_{t\le T} |S_t - S_t^{\prime}| > \frac{n^{1/3}}{4A}\Big) \le \mathbb{P}\bigg(\sum_{i=1}^T |\Delta_i-\Delta^{\prime}_i| > \frac{n^{1/3}}{4A}\bigg) \le \mathbb{E}[e^{|\Delta_1 - \Delta_1^{\prime}|}]^T e^{-n^{1/3}/(4A)},\end{equation}

where for the last inequality we used the i.i.d. property of the increments $\Delta_i-\Delta_i^{\prime}$ . To continue our bounds we need some more detail about the coupling of $\Delta_1$ and $\Delta^{\prime}_1$ from the proof of [Reference van der Hofstad32, Theorem 2.10]. We break $\Delta_1$ up into a sum of n i.i.d. Bernoulli random variables of parameter p, which we call $(\beta_j)_{j=1}^n$ , and couple these with n Poisson random variables $(\beta^{\prime}_j)_{j=1}^n$ of parameter p, so that

\begin{equation*}\Delta_1 = \sum_{j=1}^n \beta_{j} \text{ and } \Delta^{\prime}_1 = \sum_{j=1}^n \beta^{\prime}_{j}.\end{equation*}

The coupling is arranged so that for each i and j,

• $\mathbb{P}(\beta_{j} = \beta^{\prime}_{j} = 0) = 1-p$ ,

• $\mathbb{P}(\beta_{j} = \beta^{\prime}_{j} = 1) = pe^{-p}$ ,

• $\mathbb{P}(\beta_{j} = 1,\,\beta^{\prime}_{j}=0) = e^{-p}-(1-p)$ and

• $\mathbb{P}(\beta_{j} = 1,\,\beta^{\prime}_{j}=k) = \mathbb{P}(\beta^{\prime}_{j}=k) = \frac{e^{-p}p^k}{k!}$ for $k\ge 2$ .

We deduce (using the inequality $e^{-x}\le 1-x+x^2/2$ , valid for all $x\ge 0$ ) that

\begin{align*}\mathbb{E}[e^{|\beta_{j}-\beta^{\prime}_{j}|}] &= 1-p+pe^{-p} + e(e^{-p}-(1-p)) + \sum_{k=2}^\infty e^{k-1}\frac{e^{-p}p^k}{k!}\\ &\le 1 + e\frac{p^2}{2} + p^2 e e^{-p} \sum_{k=0}^\infty \frac{(ep)^k}{(k+2)!} \le 1 + cp^2\end{align*}

for some finite constant c. Thus

\begin{equation*}\mathbb{E}[e^{|\Delta_1 - \Delta_1^{\prime}|}] \le (1+cp^2)^n \le \exp(cp^2 n),\end{equation*}

and substituting this into (37) gives

(38) \begin{equation}\mathbb{P}\Big(\max_{t\le T} |S_t - S_t^{\prime}| > \frac{n^{1/3}}{4A}\Big) \le \exp\Big(cp^2nT- \frac{n^{1/3}}{4A}\Big)\le C\exp\Big(- \frac{n^{1/3}}{4A}\Big)\end{equation}

for some finite constant C.

We now consider the first quantity on the right-hand side of (36) and use the same change of measure as in (35) with $\mu_n = pn$ to remove the drift from $S_t^{\prime}$ . Noting that $g(t) + \frac{n^{1/3}}{4A} = \gamma(t)$ , by the definition of $\mathbb{Q}$ , for any $\ell\ge0$ ,

(39) \begin{align}&\mathbb{P}\big(S_t^{\prime}>g(t) + \tfrac{n^{1/3}}{4A}\,\,\,\,\forall t\in[\![ 0,T]\!]\big)\nonumber\\[3pt] &\ge\mathbb{P}\big(S_t^{\prime}>\gamma(t)\,\,\,\,\forall t\in[\![ 0,T]\!],\, S_T^{\prime} \le \gamma(t)+\ell\big)\nonumber\\[3pt] &=\mathbb{E}_\mathbb{Q}\Big[(pn)^{S^{\prime}_T + T}\unicode{x1D7D9}_{\{S_t^{\prime}>\gamma(t)\,\,\,\,\forall t\in[\![ 0,T]\!],\, S_T^{\prime} \le \gamma(t)+\ell\}}\Big]e^{(1-pn)T}\nonumber\\[3pt] &\ge (pn\wedge 1)^{\ell}(pn)^{\gamma(T)+T} e^{(1-pn)T} \mathbb{Q}\big(S_t^{\prime}>\gamma(t)\,\,\,\,\forall t\in[\![ 0,T]\!],\, S_T^{\prime} \le \gamma(t)+\ell\big).\end{align}

Taking $\ell = \frac{3n^{1/3}}{8A}$ and recalling that $pn = 1+\lambda n^{-1/3}$ and

\begin{equation*}\gamma(T) = -\frac{n^{1/3}}{4A} + \frac{9T}{A^2 n^{1/3}} + \frac{pT^2}{2} = \frac{A^2 n^{1/3}}{2} + O\Big(\frac{n^{1/3}}{A}\Big),\end{equation*}

and using that $|\lambda|\le A/3$ , $|A|=o(n^{1/30})$ and $1+x\geq e^{x-x^2}$ for all $x>-1/2$ we have

\begin{equation*}(pn\wedge 1)^\ell \ge c\end{equation*}

and

\begin{equation*}(pn)^{\gamma(T)} = (1+\lambda n^{-1/3})^{A^2 n^{1/3}/2 + O(n^{1/3}/A)} \ge ce^{\lambda A^2/2},\end{equation*}

and using the more precise inequality $1+x\ge e^{x-x^2/2-|x|^3}$ for all $x>-1/2$ ,

\begin{equation*}(pn)^T e^{(1-pn)T} = ((1+\lambda n^{-1/3})e^{-\lambda n^{-1/3}})^T \ge e^{-\lambda^2 n^{-2/3} T/2 - O(\lambda^3 T/n)} \ge c e^{-\lambda^2 A/2}.\end{equation*}

Substituting these estimates into (39), we obtain

\begin{align*}&\mathbb{P}\big(S_t^{\prime}>g(t) + \tfrac{n^{1/3}}{4A}\,\,\,\,\forall t\in[\![ 0,T]\!]\big)\\ &\quad \ge c e^{\lambda A^2/2 - \lambda^2 A/2}\mathbb{Q}\big(S_t^{\prime}>\gamma(T)\,\,\,\,\forall t\in[\![ 0,T]\!],\, S_T^{\prime} \le \gamma(T)+\tfrac{3n^{1/3}}{8A}\big).\end{align*}

Since $(S_t^{\prime})_{t=1}^{T}$ is a sum of independent Poisson random variables of parameter 1 under $\mathbb{Q}$ , substituting this and (38) into (36) gives the result.

4.5. The probability a Brownian motion stays above a curve: proof of Proposition 4.11

Recall that

\begin{equation*}\gamma(s)=-\frac{n^{1/3}}{4A}+\frac{9s}{A^2n^{1/3}}+\frac{ps^2}{2}\end{equation*}

and write

\begin{equation*}P_n(T) = \mathbb{P}\big(B_s > \gamma(s) + M\log T + x_n\;\;\forall s\in[0,T],\, B_{T}\le\gamma(T)+\tfrac{3n^{1/3}}{8A} - M\log T - x\big);\end{equation*}

our aim in this section is to bound $P_n(T)$ from below.

Define

\begin{equation*}\phi(s) = \gamma(s) + \frac{n^{1/3}}{8A} = -\frac{n^{1/3}}{8A} + \frac{9s}{A^2n^{1/3}} + \frac{ps^2}{2}\end{equation*}

and

\begin{equation*}\psi_T = \gamma(T) + \frac{n^{1/3}}{4A} = \frac{9T}{A^2n^{1/3}} + \frac{pT^2}{2}.\end{equation*}

Note that since $x_n\ll n^{1/3}/A$ , for large n we have $M\log T + x_n\le n^{1/3}/(8A)$ , so

(40) \begin{equation}P_n(T) \ge \mathbb{P}\big(B_s > \phi(s) \;\;\forall s\in[0,T],\, B_{T}\le\psi_T\big).\end{equation}

We approximate the curve $\phi(s)$ given above with two straight lines defined, for $s\in [0,T/2]$ , by

\begin{equation*}\ell_1(s) = \phi(0) + \Big(\frac{\phi(T/2)-\phi(0)}{T/2}\Big)s = -\frac{n^{1/3}}{8A} + \Big(\frac{9}{A^2 n^{1/3}}+\frac{pT}{4}\Big)s\end{equation*}

and

\begin{equation*}\ell_2(s) = \phi(T/2) + \Big(\frac{\phi(T)-\phi(T/2)}{T/2}\Big)s = -\frac{n^{1/3}}{8A} + \frac{9T}{2A^2 n^{1/3}}+\frac{pT^2}{8} + \Big(\frac{9}{A^2 n^{1/3}}+\frac{3pT}{4}\Big)s.\end{equation*}

Also define

\begin{align*}I &= \Big[\psi_T/2 - A^{1/2}n^{1/3},\, \psi_T/2\Big]\\ &= \Big[\frac{9T}{2A^2n^{1/3}} + \frac{pT^2}{4} - A^{1/2}n^{1/3},\, \frac{9T}{2A^2n^{1/3}} + \frac{pT^2}{4}\Big].\end{align*}

See Figure 1 for reference. Note that $\psi_T/2 - A^{1/2}n^{1/3} > \phi(T/2)$ when n is large, so the interval I falls entirely above the curve $\phi$ .

Figure 1. We want our Brownian motion to stay above the blue curve, and the two green lines $\ell_1$ and $\ell_2$ show linear approximations to this curve on the two half-intervals. The dashed red line shows roughly where we expect our Brownian motion to be, given that it stays above the curve. This is a caricature of the true picture, and not to scale.

Since $\phi$ is convex, the linear interpolations $\ell_1$ and $\ell_2$ fall above the curve and therefore (40) is at least

\begin{equation*}\mathbb{P}\big(B_s > \ell_1(s)\;\; \forall s\in[0,T/2],\, B_s > \ell_2(s-T/2) \;\;\forall s\in[T/2,T],\, B_T \le \psi_T\big).\end{equation*}

For a lower bound, we may also insist that at time $T/2$ our Brownian motion falls within the interval I. Moreover, it will be convenient for us to know that at time T, our Brownian motion is some distance above the curve. To this end define

\begin{equation*}I'\,{:}\,{\raise-1.5pt{=}}\, \left[\psi_T - \frac{n^{1/3}}{16A},\psi_T\right] = \left[ l_2(T/2)+\frac{n^{1/3}}{16A}, l_2(T/2)+\frac{n^{1/3}}{8A}\right].\end{equation*}

Putting all this together we obtain

(41) \begin{align}&P_n(T) \ge \int_I \mathbb{P}\big(B_s > \ell_1(s)\;\; \forall s\in[0,T/2],\, B_{T/2} \in \,\textrm{d} w\big) \nonumber \\[3pt] &\quad \cdot \mathbb{P}_w\big(B_s > \ell_2(s)\;\; \forall s\in[0,T/2],\, B_{T/2} \in I'\big).\end{align}

Here $\mathbb{P}_w$ denotes a probability measure under which our Brownian motion starts from w rather than 0.

Lemma 4.12 For any $\mu,y\in\mathbb{R}$ , $t>0$ , $x>y$ and $z>y+\mu t$ ,

\begin{align*}&\mathbb{P}_x(B_s > y + \mu s \;\;\forall s\le t,\, B_t \in \,\textrm{d} z) \\ &\quad = \frac{1}{\sqrt{2\pi t}} \exp\Big(-\frac{(z-x)^2}{2t}\Big)\Big(1-\exp\Big(\frac{2(x-y)(\mu t+y-z)}{t}\Big)\Big)\,\textrm{d} z.\end{align*}

Proof. We begin with an exponential change of measure to balance the drift $\mu$ . Letting $(\mathcal{F}_s)_{s\ge 0}$ be the natural filtration of our Brownian motion, define $\mathcal P_x$ , with expectation operator $\mathcal E_x$ , by setting

\begin{equation*}\frac{\,\textrm{d} \mathcal P_x}{\,\textrm{d}\mathbb{P}_x}\Big|_{\mathcal F_t} = e^{\mu B_t - \mu x - \mu^2 t/2}.\end{equation*}

Then under $\mathcal P_x$ , $(B_s)_{s\ge 0}$ is a Brownian motion with drift $\mu$ started from x, and therefore

\begin{align*}\mathbb{P}_x(B_s > y + \mu s \;\;\forall s\le t,\, B_t \in \,\textrm{d} z) &= \mathcal E_x\big[ e^{-\mu B_t + \mu^2 t/2 + \mu x}\unicode{x1D7D9}_{\{B_s > y + \mu s \;\;\forall s\le t,\, B_t \in \,\textrm{d} z\}}\big]\\[3pt] &= e^{-\mu z + \mu^2 t/2 + \mu x}\mathcal P_x(B_s > y + \mu s \;\;\forall s\le t,\, B_t \in \,\textrm{d} z)\\[3pt] &= e^{-\mu z + \mu^2 t/2 + \mu x}\mathbb{P}_x(B_s > y \;\;\forall s\le t,\, B_t + \mu t \in \,\textrm{d} z).\end{align*}

We now recall that, as a consequence of the reflection principle for Brownian motion, for $x>y$ and $w>y$ ,

\begin{equation*}\mathbb{P}_x(B_s > y \;\;\forall s\le t,\, B_t \in dw) = \frac{1}{\sqrt{2\pi t}}\Big(\exp\Big(-\frac{(w-x)^2}{2t}\Big) - \exp\Big(-\frac{(w+x-2y)^2}{2t}\Big)\Big)\,\textrm{d} w.\end{equation*}

Since the ratio within the second exponential expands as

\begin{equation*}-\frac{(w+x-2y)^2}{2t}=-\frac{(w-x)^2}{2t}+\frac{2(yx-wx+yw-y^2)}{t},\end{equation*}

grouping by $-(w-x)^2/2t$ we obtain

\begin{align*}&\mathbb{P}_x(B_s > y \;\;\forall s\le t,\, B_t \in dw)\\[3pt] &\quad = \frac{1}{\sqrt{2\pi t}}\exp\Big(-\frac{(w-x)^2}{2t}\Big)\left(1-\exp\Big(\frac{2(yx-wx+yw-y^2)}{t}\Big)\right).\end{align*}

Taking $w=z-\mu t$ and substituting into the expression above, and then simplifying, gives the result.

We now use Lemma 4.12 to obtain a lower bound for the probability that $B_t$ stays above the line $l_1(s)$ and finishes near $w\in I$ at time $T/2$ .

Corollary 4.13 For $w\in I$ ,

\begin{equation*}\mathbb{P}\big(B_s > \ell_1(s)\;\; \forall s\in[0,T/2],\, B_{T/2} \in \,\textrm{d} w\big) \ge \frac{c}{\sqrt T} e^{-w^2/T}\,\textrm{d} w.\end{equation*}

Proof. We apply Lemma 4.12 with $x=0$ , $z=w$ , $y=-n^{1/3}/(8A)$ , $\mu = \frac{9}{A^2 n^{1/3}} + \frac{pT}{4}$ and $t=T/2$ . With these parameters, $w>y+\mu t$ and hence Lemma 4.12 tells us that

\begin{align*}\mathbb{P}\big(B_s > \ell_1(s)\;\; \forall s&\in[0,T/2],\, B_{T/2} \in \,\textrm{d} w\big)\\ &= \frac{1}{\sqrt{\pi T}} e^{-w^2/T} \Big(1-\exp\Big(-2\Big(w+\frac{n^{1/3}}{8A} - \frac{9T}{2A^2 n^{1/3}} - \frac{pT^2}{8}\Big)\frac{n^{1/3}}{4AT}\Big)\Big)\,\textrm{d} w.\end{align*}

Since $w\in I$ , we have $w\ge \frac{9T}{2A^2 n^{1/3}} + \frac{pT^2}{4} - A^{1/2}n^{1/3}$ and therefore

\begin{equation*}\Big(w+\frac{n^{1/3}}{8A} - \frac{9T}{2A^2 n^{1/3}} - \frac{pT^2}{8}\Big)\frac{n^{1/3}}{4AT} \ge \Big(\frac{pT^2}{8}-A^{1/2}n^{1/3}\Big)\frac{n^{1/3}}{4AT} \ge c\end{equation*}

for some $c>0$ , and the result follows.

Next we bound from below the second probability that appears in the integral (41), again by means of Lemma 4.12.

Corollary 4.14 For $w\in I$ and A sufficiently large,

\begin{equation*}\mathbb{P}_w\big(B_s > \ell_2(s)\;\; \forall s\in[0,T/2],\, B_{T/2} \in I' \big) \ge \frac{c}{\sqrt{T}} \int_{I'}^{} e^{-(z-w)^2/T} \,\textrm{d} z.\end{equation*}

Proof. We now apply Lemma 4.12 with $x=w$ , $y=-\frac{n^{1/3}}{8A} + \frac{9T}{2A^2 n^{1/3}} + \frac{pT^2}{8}$ , $\mu = \frac{9}{A^2 n^{1/3}} + \frac{3pT}{4}$ and $t=T/2$ . This tells us that

(42) \begin{align}&\mathbb{P}_w\big(B_s > \ell_2(s)\;\; \forall s\in[0,T/2],\, B_{T/2} \in I' \big)\nonumber\\[3pt] &\quad = \frac{1}{\sqrt{\pi T}} \int_{I'}^{} e^{-(z-w)^2/T} \Big(1-\exp\Big(\frac{2(w-y)(\mu t +y - z)}{t}\Big)\Big)\,\textrm{d} z,\end{align}

we want an upper bound for the exponential term

\begin{equation*}\exp\Big(\frac{2(w-y)(\mu t +y - z)}{t}\Big).\end{equation*}

To this end observe that, since $z\geq \phi(T)+n^{1/3}/16A$ and

\begin{equation*}\phi(T)=-\frac{n^{1/3}}{8A}+\frac{9T}{A^2n^{1/3}}+\frac{pT^2}{2}, \end{equation*}

then

\begin{equation*}\mu t +y - z =\frac{9T}{A^2n^{1/3}}+\frac{pT^2}{2}-\frac{n^{1/3}}{8A}-z\leq -\frac{n^{1/3}}{16A}.\end{equation*}

Also, since $w\in I$ we obtain

\begin{align*}(w-y)(\mu t +y -z)\leq -\frac{n^{1/3}}{16A}(w-y)&\leq -\frac{n^{1/3}}{16A}\left(\frac{pT^2}{8}+\frac{n^{1/3}}{8A}-A^{1/2}n^{1/3}\right)\\&=-\frac{n^{1/3}}{16A}\frac{pT^2}{8}(1-o(1)),\end{align*}

whence

\begin{equation*}\frac{2(w-y)(\mu t +y -z)}{t}=\frac{4(w-y)(\mu t +y -z)}{T}\leq -\frac{4}{T}\frac{n^{1/3}}{16A}\frac{pT^2}{8}(1-o(1))\sim -\frac{1}{32}.\end{equation*}

Plugging this estimate into (42) we obtain the desired result.

Proof of Proposition 4.11. Substituting Corollaries 4.13 and 4.14 into (41), and recalling the definition of I $^{\prime}$ we obtain

(43) \begin{equation}P_n(T)\ge \frac{c}{T} \int_{\psi_T-\frac{n^{1/3}}{16A}}^{\psi_T} \int_{\psi_T/2-A^{1/2}n^{1/3}}^{\psi_T/2} e^{-w^2/T - (z-w)^2/T} \,\textrm{d} w \, \,\textrm{d} z.\end{equation}

Using the substitutions $u = w - \psi_T/2$ and $v = z - \psi_T$ , the term on the right-hand side of the inequality in (43) equals

\begin{equation*}\frac{c}{T} \int_{-\frac{n^{1/3}}{16A}}^{0} \int_{-A^{1/2}n^{1/3}}^0 e^{-(u+\psi_T/2)^2/T - (v-u+\psi_T/2)^2/T} \,\textrm{d} u \, \,\textrm{d} v\end{equation*}

which, after multiplying out the quadratic terms in the exponent, becomes

\begin{equation*}\frac{c}{T} \int_{-\frac{n^{1/3}}{16A}}^{0} \int_{-A^{1/2}n^{1/3}}^0 e^{-2u^2/T + 2uv/T - \psi_T^2/(2T) - v^2/T - v\psi_T/T} \,\textrm{d} u \, \,\textrm{d} v.\end{equation*}

Since $u,v\le 0$ , we have $2uv/T\ge 0$ and therefore the integral over u is at least

\begin{equation*}\int_{-A^{1/2}n^{1/3}}^0 e^{-2u^2/T} \,\textrm{d} u \ge c A^{1/2}n^{1/3} \ge c\sqrt T.\end{equation*}

We deduce that

(44) \begin{equation}P_n(T) \ge \frac{c}{\sqrt{T}} \int_{-\frac{n^{1/3}}{16A}}^{0} e^{ - \psi_T^2/(2T) - v^2/T - v\psi_T/T} \,\textrm{d} v.\end{equation}

Now

\begin{equation*}\frac{\psi_T}{T} = \frac{9}{A^2n^{1/3}} + \frac{pT}{2} = \frac{A}{2n^{1/3}} + O\Big(\frac{1}{A^2 n^{1/3}}\Big),\end{equation*}

so the exponent on the right-hand side of (44) is $e^{-\psi_T^2/2T - O(1)}$ ; thus (44) becomes

\begin{equation*}P_n(T)\ge \frac{c}{\sqrt{T}} \cdot \frac{n^{1/3}}{16A} e^{ - \psi_T^2/(2T) } \ge \frac{c}{A^{3/2}} e^{ - \psi_T^2/(2T) }.\end{equation*}

It then remains only to note that

\begin{equation*}\frac{\psi_T^2}{2T} = \frac{1}{2T}\Big(\frac{9T}{A^2 n^{1/3}} + \frac{pT^2}{2}\Big)^2 = \frac{81T}{2A^2 n^{1/3}} + \frac{9pT^2}{2A^2 n^{1/3}} + \frac{p^2 T^3}{8} = \frac{A^3}{8} + O(1),\end{equation*}

and the proof is complete.