子树移除

设整棵树（含根）当前节点数为 $n$。对任意节点 $i$，要让它被删除，必须在某一步选到它自己或它的某个祖先。

记 $\mathrm{Depth}(i)$ 为节点 $i$ 的祖先个数（不含自身），则“选到祖先链上的任一点”这个事件的大小为 $\mathrm{Depth}(i)+1$ 个节点，因此

$$\Pr(i\text{ 在下一步被删除})=\frac{\mathrm{Depth}(i)+1}{n}.$$

用指示变量 $X_i$ 表示“节点 $i$ 在某一步中是被选中的节点（从而触发一次删除）”。总步数为

$$X=X_1+X_2+\cdots+X_n.$$

在给定节点 $i$ 最终会被删除的前提下，$i$ 自己成为触发删除的被选节点的条件概率为

$$\Pr(i\text{ 被选中}\mid i\text{ 被删除})=\frac{1}{\mathrm{Depth}(i)+1}.$$

由期望线性性得到

$$\mathbb{E}[X]=\sum_{i}\mathbb{E}[X_i]=\sum_{i}\frac{1}{\mathrm{Depth}(i)+1}.$$

---

Original Explanation

Every node in the tree has an equal probability of being selected. If a node is to be removed, we know that either the node itself, or one of the node's ancestors must have been chosen.

The number of ancestors of a node $i$ is $\textrm{Depth}[i]$

$$\begin{equation} P(i \ \textrm{is removed}) = \textrm{Depth}[i] \ / \ \textrm{Size of Tree} \end{equation}$$ $$\begin{equation} P(i \ \textrm{is chosen}) = 1 \ / \ \textrm{Size of Tree} \end{equation}$$ $$\begin{equation} P(i \ \textrm{is removed} \ | \ i \textrm{ is chosen} ) =1 \end{equation}$$

We can use Bayes theorem to solve this problem where: $P(A|B) = \frac{P(B | A) * P(A)}{P(B)}$ and therefore $P(i\ \textrm{is chosen} \ |\ i\ \textrm{is removed}) = 1 / \textrm{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.

$$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]}$$