t_\star+\lambda\omega_\star$. Consequently, $$\begin{aligned}
\sum_y \left(\frac{1}{N}-P^t(x,\pi(y))\right)_+&\approx& \Phi(\lambda)\, ,\end{aligned}$$ as desired. This argument is made rigorous in Sections \[sec:small\], \[sec:large\] and \[sec:collisions\].

The lower bound {#sec:lower-bound}
===============

Fix $t\geq 1$, two states $x,y\in{\ensuremath{\mathcal{X}}}$, and a parameter $\theta\in(0,1)$. Let $P^t_\theta(x,y)$ denote the contribution to $P^t(x,y)$ from paths having weight less than $\theta$. Note that $P^t_\theta(x,y)< P^t(x,y)$ if and only if some path of length $t$ from $x$ to $y$ has weight larger than $\theta$, implying in particular that $P^t(x,y)>\theta$. Thus, $$\begin{aligned}
\frac{1}{N}-P^t_\theta(x,y) & \leq & \left(\frac{1}{N}-P^t(x,y)\right)_+ 
+\frac{1}{N}{\bf 1}_{P^t(x,y)>\theta}.\end{aligned}$$ Summing over all $y\in{\ensuremath{\mathcal{X}}}$ and observing that there can not be more than $1/\theta$ half-edges $y\in{\ensuremath{\mathcal{X}}}$ satisfying $P^t(x,y)>\theta$, we obtain $$\begin{aligned}
1-\sum_{y\in{\ensuremath{\mathcal{X}}}}P^t_\theta(x,y) & \leq  & {\ensuremath{\mathcal{D}}}_x(t) + \frac{1}{\theta N}.\end{aligned}$$ Now, the left-hand side is the quenched probability (i.e., conditional on the underlying pairing) that a <span style="font-variant:small-caps;">nbrw</span> $\{X_k\}_{0\leq k \leq t}$ starting at $x$ satisfies $\prod_{k=1}^t\frac{1}{\deg(X_k)}> \theta$. Taking expectation w.r.t. the pairing, we arrive at $$\begin{aligned}
\label{lb:1}
{\ensuremath{\mathbb{P}}}\left(\prod_{k=1}^t\frac{1}{\deg(X_k)}> \theta\right) & \leq & {\ensuremath{\mathbb{E}}}[{\ensuremath{\mathcal{D}}}_x(t)] + \frac{1}{\theta N},\end{aligned}$$ where the average is now over both the <span style="font-variant:small-caps;">nbrw</span> and the pairing (annealed law). A useful property of the uniform pairing is that it can be constructed sequentially, the pairs being revealed along the way, as we need 