Expected number of subtree removals

Quant Interview Question asked in JumpTrading

You are given a rooted tree. On each step, you randomly choose a node and remove the subtree rooted by that node and the node itself until all of them have been removed (that is, the root has been chosen). Find the expected number of steps in this process.

---

Try to solve this problem yourself before moving on to the solution below

.
.
.
.
.
.

---

Solution

Every node has an equal probability of being selected. We also know that to remove a particular node, one of its ancestors or the node itself must be chosen.

So the number of ancestors of one particular node i = Depth [i]

P(i is removed) = Depth[i] / Size of the tree
P(i is chosen) = 1 / size of the tree
P(i is removed | i is chosen) = 1

We use the Bayes theorem: P(A|B) = P(B|A)P(A)/P(B)

Hence P(i is chosen | i is removed) = 1/Depth[i]

We now use Linearity of Expectation to find the expected number of subtree removals.
Define indicator variable X_i =1 if i node was chosen; 0 otherwise.

\(X = X_1 + X_2 … X_n \\ \)

\(E[X] = \sum_{i=1}^n E[X_i]\)

\(E[X] = \sum 1* P(X_i \text{ was chosen } | i \text{ was removed}) \)

\(E[X] = \sum_{i=1}^n \frac{1}{\text{Depth}[i]}\)

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!