# pr.probability – Probability process involving blocking paths of rooted tree

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.

Posted on Categories Articles