m$ possible trajectories to follow, so the chance is less than $$m\eta=o(1).$$

-   or the remainder of its trajectory after the first unpaired half-edge has weight less than ${\Delta{{w_{\textsc{min}}}}}/{\eta}$: this part consists of at most $t/2$ half-edges which can be coupled with uniform samples from ${\ensuremath{\mathcal{X}}}$ for a total-variation cost of ${mt^2}/{N}$, as in Section \[sec:lower-bound\]. Thus, the conditional chance is at most $$\begin{aligned}
    \qquad\qquad\frac{mt^2}{N}+{\ensuremath{\mathbb{P}}}\left(\prod_{k=1}^{t/2}\deg(X_k^\star) \geq  \frac{\eta}{\Delta{{w_{\textsc{min}}}}}\right)
    & = & o(1),\end{aligned}$$ by Chebychev’s inequality, since $\log\left(\frac{\eta}{\Delta{{w_{\textsc{min}}}}}\right) - \frac {\mu t}2 >>  \sigma\sqrt{\frac t2}$.

Proof of Lemma \[lm:large\] {#sec:large}
===========================

Set $m=\lceil\log N\rceil$. On $G(\pi)$, let $X^{(1)},\ldots,X^{(m)}$ and $Y^{(1)},\ldots,Y^{(m)}$ be $2m$ independent <span style="font-variant:small-caps;">nbrw</span>s of length $t/2$ starting at $x$ and $y$ respectively. Let $B$ denote the event that their trajectories form two disjoint trees and that for all $1\leq k\leq m$, $$\prod_{\ell=1}^{t/2} \frac{1}{\deg(X^{(k)}_\ell)}\prod_{\ell=1}^{t/2}\frac{1}{\deg(Y^{(k)}_\ell)}>\theta.$$ Then clearly, ${\ensuremath{\mathbb{P}}}\left(B|\pi\right)\geq {\overline{\ensuremath{\mathfrak{W}}}}^m$. Averaging w.r.t. the pairing $\pi$, we see that $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left({\overline{\ensuremath{\mathfrak{W}}}}>\Phi(\lambda)+\varepsilon\right) & \leq & \frac{{\ensuremath{\mathbb{P}}}\left(B\right)}{(\Phi(\lambda)+\varepsilon)^m}.\end{aligned}$$ Thus, it is enough to establish that ${\ensuremath{\mathbb{P}}}(B)  \leq \left(\Phi(\lambda)+o(1)\right)^m$. We do so by generating the $2m$ walks $X^{(1)},Y^{(1)},\ldots,X^{(m)},Y^{(m)}$ one after the other along with the underlying pairing, as above. Given that $X^{(1)},Y^{(1)},\ldots,X^{(\ell-1)},Y^{(\ell-1)}$ already satisfy the desired property, the conditional chance that $X^{(\ell)},Y^{(\ell)}$ also does is at most $\Phi(\lambda)+o(1)$, 