$v$).

A second approximation consists in eliminating those paths whose weight exceeds some given threshold $\theta > 0$ (the correct choice turns out to be $\theta\approx \frac 1N$): $$P^t(x,\pi(y))\approx \sum_{u,v}{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\ind_{{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\leq \theta} \ind_{\{\pi(u)=v\}} \, .$$ Conditionally on the two trees of height $t/2$, this is a weighted sum of weakly dependent Bernoulli variables, and the large-weight truncation should prevent it from deviating largely from its expectation. We make this argument rigorous in Section \[sec:completion\], using Stein’s method of exchangeable pairs. Provided the exposure process did not reveal too many pairs of matched half-edges, the conditional expectation of $\ind_{\{\pi(u)=v\}}$ remains close to $1/N$, and we obtain the new approximation $$N P^t(x,\pi(y))\approx \sum_{u,v}{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\ind_{{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\leq \theta} \, .$$

Now, the right-hand side corresponds to the quenched probability (conditionally on the graph) that the product of the weights seen by two independent <span style="font-variant:small-caps;">nbrw</span> of length $t/2$, one starting from $x$ and the other from $y$, does not exceed $\theta$. The last step consists in approximating those trajectories by independent uniform samples from ${\ensuremath{\mathcal{X}}}$, which we denote by $X_1^\star,\ldots,X_t^\star$. We obtain $$\begin{aligned}
\sum_{u,v}{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\ind_{{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\leq \theta}&\approx& {\ensuremath{\mathbb{P}}}\left[\frac{1}{\deg(X_1^\star)}\cdots\frac{1}{\deg(X_t^\star)}\leq \theta\right]\\
&\approx& {\ensuremath{\mathbb{P}}}\left[\frac{\sum_{k=1}^t(\mu-\log \deg(X^\star_k))}{\sigma\sqrt{t}}\leq \frac{\mu t+\log \theta}{\sigma\sqrt{t}}\right]\\
&\approx & 1-\Phi(\lambda)\, ,\end{aligned}$$ by the central limit theorem, since $\theta\approx 1/N$ and $t\approx 