Skip to content

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

∑v≠root1d(v)\sum_{v\ne\text{root}}\dfrac{1}{d(v)}, where d(v)d(v) is the depth of vv (root at depth 0). Node vv costs a step only if it is picked itself, which happens exactly when it is chosen before any of its d(v)−1d(v)-1 non-root ancestors. By symmetry among those d(v)d(v) nodes this has probability 1d(v)\tfrac1{d(v)}; 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 solution

Lessons behind this question

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