\subsection{Sparse independent selections}

The same distance forests give a finite bound with the selection
probability as a parameter. This can be useful when \(L\) varies with
\(n\), although its fixed-length exponent is weaker than
Theorem~\ref{thm:main}.

\begin{proposition}\label{prop:biased-selection}
Let \(L\ge14\) be an integer, and put \(r=\lfloor L/2\rfloor>6\),
\(R=L-1\), and \(\alpha_L=3R/r-4>0\).
Define
\[
 n_{\rm prob}(L)=\left\lceil\max\left\{8,\,
 8^{r/(r-6)},\,L^{2/\alpha_L}\right\}\right\rceil.
\]
For every \(n\ge n_{\rm prob}(L)\), writing
\(N=n+(L-1)\binom n2\), we have
\[
 \edimm(S_L(K_n))\le
 \left\lfloor8Nn^{-1+6/r}\right\rfloor.
\]
\end{proposition}
\begin{proof}
For a signed sum of independent Bernoulli variables with total variance
\(V>0\), every atom has probability at most \(\sqrt{\pi/(8V)}\).
Indeed, replace a negative Bernoulli variable by its complement and
absorb the constant. Fourier inversion bounds each atom by
\[
 \frac1{2\pi}\int_{-\pi}^{\pi}
 e^{-2V\sin^2(t/2)}\,dt
 \le\frac1{2\pi}\int_{-\infty}^{\infty}
 e^{-2Vt^2/\pi^2}\,dt
 =\sqrt{\frac{\pi}{8V}}.
\]
Here \(\sin(|t|/2)\ge |t|/\pi\) for \(|t|\le\pi\).

Select each vertex independently with probability \(0<p\le1/2\).
Let \(W\) be the selected set and put \(w=np\).
For \(n\ge8\), each generic forest group contains at least \(n/2\)
vertices and has variance at least \(w/4\). Each exceptional group
contains \(2(n-3)\ge n\) vertices and has variance at least \(w/2\).
Their largest atoms are therefore less than \(\sqrt{2/w}\) and
\(1/\sqrt w\), respectively. The conditioning and leaf-elimination
proof of Lemma~\ref{lem:distance-forest} applies with these atom bounds.
For \(w>1\), the two classes of pairs have total collision
probability less than
\[
 \frac{L^2n^4}{8}\left(\frac2w\right)^{R/2}
 \quad\hbox{and}\quad
 \frac{n^3}{2}\frac{w^{-r/2}}{1-w^{-1/2}}.
\]
The first count bounds all pairs among the \(L\binom n2\) edges.
The second sums the exceptional depths as a geometric series.

Choose \(p=4n^{-1+6/r}\). The threshold gives \(p\le1/2\),
\(w=4n^{6/r}\ge4\), and \(n^{\alpha_L}\ge L^2\).
Thus the two displayed probabilities are at most \(1/8\) and
\(2^{-r}\le1/128\). Also \(\alpha_L\ge2-3/r>0\), since
\(R\ge2r-1\), so the threshold is well defined.
By Markov's inequality, \(\Pr(|W|>2Np)\le1/2\).
The sum of this probability and the collision bound is less than one.
Some selection resolves all edges and has size at most
\(\lfloor2Np\rfloor\), as required.
\end{proof}