Consider a rooted tree $T$ of depth $R$ and $n$ leaf nodes. We would like to select a random subset $S$ of the edges of $T$, such that

(i) Every root-leaf path of $T$ contains at least one edge in $S$;

(ii) For any subset $U$ of the edges of $T$, there holds

$$

Pr( U subseteq S ) leq q^{|U|}

$$

for some $q = Theta(1/R)$.

Is it possible to generate $S$ in this manner?

To explain these two conditions, note that if we only want to satisfy condition (ii) for sets $U$ of cardinality one, there is a simple way to do it: select a random integer $J$ uniformly in the range ${ 1, …, R }$, and then set $S$ to be the edges at depth $J$.

Alternatively, if we want to satisfy condition (ii) with a slightly larger value $q = Theta(frac{log n}{R} )$, it is also easy to do it: each edge of $T$ goes into $S$ independently with probability $p = frac{log n}{R}$. Note then that with high probability condition (i) is satisfied.