\label{lb:3}
\left|{\ensuremath{\mathbb{P}}}\left(\prod_{k=1}^t\frac{1}{\deg(X_k^\star)}> \theta\right)-\Phi\left(\frac{\mu t+\log\theta}{\sigma\sqrt t}\right)\right| & \leq & \frac{\varrho}{\sigma^3\sqrt{t}}.\end{aligned}$$ We may now combine (\[lb:1\]), (\[lb:2\]), (\[lb:3\]) to obtain $$\begin{aligned}
{\ensuremath{\mathbb{E}}}[{\ensuremath{\mathcal{D}}}_x(t)] & \geq &  \Phi\left(\frac{\mu t+\log\theta}{\sigma\sqrt t}\right) - \frac{1}{\theta N}-\frac{2t^2}{N}- \frac{\varrho}{\sigma^3\sqrt{t}}.\end{aligned}$$ With $t$ as in (\[def:t\]) and $\theta=(\log N)/N$, the right-hand side is $\Phi(\lambda)+o(1)$, thanks to our assumptions on $\mu,\sigma,\varrho$. This establishes the lower bound (\[lowerbound\]).

The upper-bound
===============

Following @lubetzky2010cutoff, we call $x\in{\ensuremath{\mathcal{X}}}$ a *root* (written $x\in{\ensuremath{\mathcal{R}}}$) if the (directed) ball of radius $h$ centered at $x$ (denoted by ${\ensuremath{\mathcal{B}}}_x$) is a tree, where $$\begin{aligned}
\label{def:h}
h & := & \left\lfloor\frac{\log N}{10\log \Delta}\wedge\log\log N\right\rfloor.\end{aligned}$$ Note that $1<<h<<\omega_\star$ by assumptions (\[assume:Delta\]) and (\[assume:sigma\]). The first proposition below shows that we may restrict our attention to paths between roots. The second proposition provides a good control on such paths.

\[pr:root\] $$\begin{aligned}
\max_{x\in{\ensuremath{\mathcal{X}}}}P^h(x, {\ensuremath{\mathcal{X}}}\setminus{\ensuremath{\mathcal{R}}}) & \xrightarrow[]{{\ensuremath{\mathbb{P}}}} & 0.\end{aligned}$$

For $t$ as in (\[def:t\]), \[pr:up\] $$\min_{x\in{\ensuremath{\mathcal{R}}}}\min_{y\in{\ensuremath{\mathcal{R}}}\setminus{\ensuremath{\mathcal{B}}}_x}P^t(x,\pi(y))\geq \frac{1-\Phi(\lambda)-o_{\ensuremath{\mathbb{P}}}(1)}{N}.$$

Let us first see how those results imply the upper-bound (\[upperbound\]). Observe that $$\begin{aligned}
{\ensuremath{\mathcal{D}}}(t+h)&\leq & \max_{x\in{\ensuremath{\mathcal{X}}}}P^h\left(x,{\ensuremath{\mathcal{X}}}\setminus{\ensuremath{\mathcal{R}}}\right)+\max_{x\in {\ensuremath{\mathcal{R}}}}{\ensuremath{\mathcal{D}}}_x(t)\, .\end{aligned}$$ The first term is $o_{\ensuremath{\mathbb{P}}}(1)$ by Proposition \[pr:root\]. For the second one, we write $$\begin{aligned}
{\ensuremath{\mathcal{D}}}_x(t) & = & \sum_{y\in {\ensuremath{\mathcal{R}}}\setminus{\ensuremath{\mathcal{B}}}_x}\left(\frac{1}{N}-P^t(x,\pi(y))\right)_++\sum_{y\in {\ensuremath{\mathcal{B}}}_x\cup({\ensuremath{\mathcal{X}}}\setminus{\ensuremath{\mathcal{R}}})}\left(\frac{1}{N}-P^t(x,\pi(y))\right)_+.\end{aligned}$$ Proposition \[pr:up\] ensures that the first sum is bounded by $\Phi(\lambda)+o_{\ensuremath{\mathbb{P}}}(1)$ uniformly in $x\in{\ensuremath{\mathcal{R}}}$. To see 