Expected cuts to strip a rooted tree
Question
You have a rooted tree. At each step, pick uniformly at random one of the nodes still present other than the root, and delete it along with its entire subtree. Repeat until only the root is left. What is the expected number of steps?
Short answer
, where is the depth of (root at depth 0). Node costs a step only if it is picked itself, which happens exactly when it is chosen before any of its non-root ancestors. By symmetry among those nodes this has probability ; sum by linearity.
Adapted from OpenQuant; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solutionLessons behind this question
- Expectation, Mean, and Variance
- Counting and Combinatorics
- Conditional Expectation and Variance Revisited
Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.
Read it free