Trivial

The word "trivial" is tossed around quite a bit by theoretical computer science folks, and it's sometimes difficult to tell if the word is used in jest or earnestly. An example follows as a short writeup for a homework question of mine.

Cartels

The Juarez Cartel is being investigated by the Federales. The n members 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 node v let Xv be an IRV that is 1 if v is arrested before any of its ancestors and 0 otherwise. Use linearity of expectation. Your solution can use Θ notation.
Following the hint, if Xv 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 arrested1.

  1. trivial algebra omitted