# Cartels

Following the hint, ifThe Juarez Cartel is being investigated by the Federales. Thenmembers of the cartel are organized in a perfect binary tree (recall that in a perfect binary tree, all leaves are at the same depth and each internal node has two children). Each day, the Federales select a node uniformly at random from the tree. They then arrest this node and all nodes below it - subordinates are arrested due to incriminating information obtained from the selected node. All arrested nodes are removed from the tree.What is the expected number of days until all nodes are removed?Hint: for each nodevletX_{v}be an IRV that is 1 ifvis arrested before any of its ancestors and 0 otherwise. Use linearity of expectation. Your solution can use Θ notation.

*X*

_{v}is our IRV, the probability of the IRV should be $$\frac{1}{log \ell +1}$$ where ℓ = height of the tree. We can then see that by linearity of expectation $$\sum_{i=0}^n \frac{1}{\ell +1}$$ and instead of summing over the tree, we can notice that we can sum at each level of the tree and bound it from above by its height as was done in the class version of recursion trees/master method derivation. \[ \sum_{i=0}^{\ell} \frac{2^i}{\ell +1} \] if we rewrite the sum as a recurrence relation: $$A(i) = \sum_{i=0}^{\ell} \frac{2^i}{\ell +1}$$ $$A(i) = A(i-1) + \frac{2^i}{\ell +1}$$ we can see that a trivial loose upper bound for this is

*O*(

*n*) and that a tighter bound is $$\Theta\left(\frac{n}{log n}\right)$$ days until everyone is arrested

^{1}.

- trivial algebra omitted↩