IBM Ponder This #091 · 2005 年 11 月

固定参数 p∈[0,1]。从完整的无限二叉树开始，每条边独立地以概率 p 保留。取与根连通的部分作为随机树。例如，仅剩根节点的概率为 (1-p)^2。

丢弃所有包含无穷多个顶点的随机树以后，剩下的有限树的顶点数期望是多少？用 p 表示。原题提醒，可能通过不严谨的推导碰巧得到正确答案，因此仍应考虑严谨证明需要哪些步骤。

官方 2005 年 11 月 17 日提示：可以先计算有多少概率生成无限树；最终所求是以“树为有限”为条件的期望，而不是无条件期望。

解答

认真尝试后再打开

待补充。