them. We exploit this degree of freedom to generate the walk $\{X_k\}_{k\geq 0}$ and the pairing simultaneously, as follows. Initially, all half-edges are unpaired and $X_0=x$; then at each time $k\geq 1$,

1.  if $X_{k-1}$ is unpaired, we pair it with a uniformly chosen other unpaired half-edge; otherwise, $\pi(X_{k-1})$ is already defined and no new pair is formed.

2.  in both cases, we let $X_{k}$ be a uniformly chosen neighbour of $\pi(X_{k-1})$.

The sequence $\{X_k\}_{k\geq 0}$ is then exactly distributed according to the annealed law. Now, if we sample uniformly from ${\ensuremath{\mathcal{X}}}$ instead of restricting the random choice made at (i) to unpaired half-edges, the uniform neighbour chosen at step (ii) also has the uniform law on ${\ensuremath{\mathcal{X}}}$. This creates a coupling between the process $\{X_k\}_{k\geq 1}$ and a sequence $\{X_k^\star\}_{k\geq 1}$ of <span style="font-variant:small-caps;">iid</span> samples from ${\ensuremath{\mathcal{X}}}$, valid until the first time $T$ where the uniformly chosen half-edge or its uniformly chosen neighbour is already paired. As there are less than $2k$ paired half-edges by step $k$, a crude union-bound yields $${\ensuremath{\mathbb{P}}}\left(T\leq t\right)\leq \frac{2t^2}{N}.$$ Consequently, $$\begin{aligned}
\label{lb:2}
\left|{\ensuremath{\mathbb{P}}}\left(\prod_{k=1}^t\frac{1}{\deg(X_k)}> \theta\right) - {\ensuremath{\mathbb{P}}}\left(\prod_{k=1}^t\frac{1}{\deg(X_k^\star)}> \theta\right)\right| & \leq & \frac{2t^2}{N}.\end{aligned}$$ On the other hand, since $\{X_1^\star,\ldots,X_t^\star\}$ are <span style="font-variant:small-caps;">iid</span>, Berry-Esseen’s inequality implies $$\begin{aligned}
