Consider a rooted tree $T$ and $n$ leaf nodes which are all at depth $R$. 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.



Probability process involving blocking paths of rooted tree
Consider a binary tree of depth $R$ so that $n=2^R$. We will show that in this case, it is impossible to satisfy (i) and (ii) with $q \le 1/8$. A more precise estimate can be obtained using the generating function for Catalan numbers, but the goal is just to show that if (i) and (ii) hold then $q$ is bounded away from zero as $R$ grows; in particular $q=\Theta (1/R)$ is not compatible with (i) and (ii).


The number of minimal edge-cutsets of size $k$ that separate the root from level $R$ is at most the number of full binary trees with $k$ parent nodes, which is less than $4^k$ (It is actually a Catalan number, see [1].)
In order to separate the root from the leaves, one of the cutsets must be in $S$ and this event has probability at most
$\sum\_{k \ge 2} 4^k q^{-k}$ by (ii). In particular, this probability is at most $1/2$ for $q \le 1/8$. Thus to satisfy both (i) and (ii) we must have $q>1/8$.


[1] <https://math.stackexchange.com/questions/1944275/rooted-binary-trees-and-catalan-numbers/1944303>


