You are given a rooted tree with n nodes. 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.
This problem is from a puzzles worksheet shared in our college.
Solution stated:
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. E[X] = E[X1] + E[X2] + ... E[Xn] = \sum 1* P(i is chosen| i is removed) =\sum 1/depth[i]
I am unable to understand why P(i is chosen |i is removed) is used here, why not P(i is chosen) only is used here? Can someone explain a bit in detail?
Thanks.
Here, the random variable $X_i$ is 1 iff it is chosen given it is removed, because it can be removed even if an ancestor is chosen as well, but then it would not be 1 and also it would not be 1 if it was chosen but it had already been removed before. Thus this is the definition that is correct and makes sense.