Proof. The output will be a subtree with labels \(A_v(b)\setminus W\) and child laws obtained from the target marginals of the local transition. We first identify which children can be retained while discarding at most \(\mathrm e^{-m_j}\) of the transition mass at each retained node with outgoing level \(j\). Keep the input tree fixed throughout this analysis. At a node whose outgoing level is \(j\), use the transition of Section 2 with its child distribution and capacity \(m_j\). All nodes use the same set \(W\). At fixed \(W\), write \(d_v(W)\) for the probability of local failure at \(v\), and \(t_{vb}(W)\) for the probability of local non-failure with target \(b\). Thus \[ d_v(W)+\sum_{b\in\operatorname{Ch}(v)}t_{vb}(W)=1. \tag{10}\] All these probabilities refer to the child laws of the fixed input tree, before any pruning or conditioning.

Pruning. For the remainder of the construction, fix \(W\) and put \(\epsilon_j=\mathrm e^{-m_j}\). Declare all leaves good. Working upward, declare a node \(v\) with outgoing level \(s\) good if \[ \sum_{\substack{b\in\operatorname{Ch}(v)\\b\ \mathrm{good}}}t_{vb}(W) \ge1-\epsilon_s. \tag{11}\] The attempt succeeds exactly when the root is good.

To bound the probability that the root is bad, define a nonnegative potential on every node of the input tree. Set \(D_v(W)=0\) at leaves and, at a node with outgoing level \(s\), define recursively \[ D_v(W)=\frac{d_v(W)+\sum_{b\in\operatorname{Ch}(v)}t_{vb}(W)D_b(W)}{\epsilon_s}. \tag{12}\] Every bad node satisfies \(D_v(W)>1\). Indeed, assuming this for its bad children, the numerator in (12) is at least \[d_v(W)+\sum_{b\ \mathrm{bad}}t_{vb}(W)>\epsilon_s,\] where the last inequality follows from (10) and the failure of (11). This proves the assertion by backward induction.

Expected potential. We now average over \(W\sim\mu_\rho\). Fix a child \(b\) of a node \(v\) with outgoing level \(s\), and abbreviate its incoming label to \(A_b\). Every label in the entire subtree below \(b\) is disjoint from \(A_b\): each such label lies on a path containing the arc into \(b\). The transition at any node in that subtree only inspects \(W\) on the union of that node’s child labels. By its recursive definition, \(D_b(W)\) therefore depends only on \(W\) outside \(A_b\).

This statement concerns every node of the fixed input tree, before conditioning on that node being good or being retained. Figure 1 shows the disjointness that makes this possible.

In the local transition at \(v\), \[t_{vb}(W)\le \mathbb P\bigl(\mathrm{target}=b,\ Z(Y)\ge\mathrm e^{-10m_s}\mid W\bigr).\] We may consequently apply (6) with \(f(W)=D_b(W)\). Together with (5) and \(\epsilon_s^{-1}=\mathrm e^{m_s}\), the recurrence gives \[ \mathbb ED_v(W) \le \mathrm e^{-8m_s} +\mathrm e^{12m_s}\sum_{b\in\operatorname{Ch}(v)}\nu_v(b)\,\mathbb ED_b(W). \tag{13}\] This step controls the dependence caused by reusing \(W\). Since the child weights sum to one, backward induction yields \[\mathbb ED_v(W)\le \sum_{j=s}^k \exp\left(12\sum_{h=s}^{j-1}m_h-8m_j\right).\] In particular, if \(o\) is the root, then \[\begin{align*} \mathbb P(o\text{ is bad}) &\le\mathbb ED_o(W)\\ &\le\sum_{j=1}^k \exp\left(12\sum_{h<j}m_h-8m_j\right) <\tfrac14. \end{align*}\] For the last inequality, geometric growth gives \(\sum_{h<j}m_h\le m_j/15\), and the \(m_j\) are distinct positive integers. Thus the sum is at most \(\sum_{m\ge1}\mathrm e^{-7m}<1/4\).

The reduced tree. On success, start from the good root. At any good node \(v\) with outgoing level \(j\), put \[\gamma_v(W)=\sum_{b\ \mathrm{good}}t_{vb}(W)\ge1-\epsilon_j.\] Retain each good child \(b\) with \(t_{vb}(W)>0\), give it weight \(t_{vb}(W)/\gamma_v(W)\), replace its incoming label by \[T_b=A_v(b)\setminus W,\] and continue recursively into \(b\). The result is a pruned and reweighted subtree of the input tree. It has the same depth because \(\gamma_v>0\) at every retained non-leaf node. Its labels are subsets of the old labels, so it is disjoint. Since \(A_v(b)\subseteq W\cup T_b\) on every retained arc, it also satisfies (9). A retained child has \(t_{vb}>0\), which implies \(|T_b|\le\lfloor m_j/2\rfloor\).

This new child law is the target marginal of the joint transition conditioned on local non-failure and a good target. Denote this conditioning event by \(E_v\). For the spread bound, use the source: (4) gives \(T\subseteq A_v(c)\) for every transition, and the unconditioned source has law \(\nu_v\) even at fixed \(W\). Thus, for every nonempty \(J\subseteq X\), \[\begin{align*} \mathbb P(J\subseteq T\mid E_v,W) &\le\frac{\mathbb P_{c\sim\nu_v}(J\subseteq A_v(c))}{\gamma_v(W)}\\ &\le\frac{\alpha_j^{|J|}}{1-\epsilon_j} \le\left(\frac{\alpha_j}{1-\epsilon_j}\right)^{|J|}. \end{align*}\] This proves all the assertions. The quantities \(t_{vb}(W)\) define the entire construction deterministically; sources and targets are auxiliary random variables used to analyze its weights. ◻

Proof of Theorem 3. If \(r=1\), the conclusion is immediate. Suppose \(r<1\), and set \[a=4\sigma,\qquad \rho=\mathrm e^{50}a, \qquad s=\lfloor\log_2\ell_k\rfloor+1.\] In particular \(0<\rho<1\). Start with \(\mathcal T\) and make successive attempts using fresh independent sets of law \(\mu_\rho\). A failed attempt leaves the current tree unchanged. After a successful attempt, retain the tree provided by Lemma 4. Conditionally on the complete past, the current tree is fixed and the next draw still has law \(\mu_\rho\).

After \(t\) successes, the capacity at original level \(i\) is \[ m_i(t)=\left\lfloor\frac{\ell_i}{2^t}\right\rfloor, \tag{14}\] using \(\lfloor\lfloor x\rfloor/2\rfloor=\lfloor x/2\rfloor\). Levels of zero capacity form an initial segment. After each success, choose any one path through that segment and keep its ending subtree, deleting the segment. All committed labels are empty, so each path of the retained subtree extends to a full path by adjoining the chosen empty prefix. This preserves the recovery guarantee and every bound at a retained node. If no levels remain, only the root is left. Fix a tie-breaking rule for these choices. The remaining positive capacities still satisfy \(m_{i+1}(t)\ge16m_i(t)\), since \(\lfloor16x\rfloor\ge16\lfloor x\rfloor\).

At a remaining original level \(i\), a valid spread parameter after \(t\) successes is \[ \alpha_i(t)=\sigma \prod_{u=0}^{t-1} \left(1-\mathrm e^{-\lfloor\ell_i/2^u\rfloor}\right)^{-1}. \tag{15}\] The positive integers \(\lfloor\ell_i/2^u\rfloor\) in this product are distinct. The infinite product over all positive integers is less than \(4\), because \[\begin{align*} \sum_{m=1}^{\infty}-\log(1-\mathrm e^{-m}) &\le \frac{1}{1-\mathrm e^{-1}}\sum_{m=1}^{\infty}\mathrm e^{-m}\\ &=\frac{\mathrm e^{-1}}{(1-\mathrm e^{-1})^2}<\log 4. \end{align*}\] Consequently \(\alpha_i(t)\le4\sigma=a\). The initial tree satisfies these bounds, and Lemma 4 proves them inductively after every success. Thus every attempt before completion has conditional success probability at least \(3/4\).

After \(s\) successes, (14) is zero at every level. Composing (9) through the successful reductions shows that the union of their draws contains the labels of a path in the original tree. The expected waiting time for each next success is at most \(4/3\): conditionally on the past, its tail is bounded by that of a geometric random variable with success probability \(3/4\). Hence the expected number of attempts needed is at most \(4s/3\). By Markov’s inequality, completion occurs within \(4s\) attempts with probability at least \(2/3\).

Predraw \(4s\) independent sets of law \(\mu_\rho\), including any that the procedure ultimately does not use, and take their union \(W_*\). It has law \(\mu_{r_*}\), where \[r_*=1-(1-\rho)^{4s} \le4s\rho =16\mathrm e^{50}\sigma s \le16\mathrm e^{50}\sigma(1+\log_2\ell_k)=r.\] With probability at least \(2/3\), \(W_*\) contains a path union. The same bound holds for \(\mu_r\) by monotonicity. ◻