# Probability process involving blocking paths of rooted tree

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.

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$$.