深度为n的满二叉树边随机染色，根到叶全白路径概率求解

嘿，咱们一步步来拆解这个问题，比起直接算重叠的全白路径，用对立事件来简化计算会轻松太多：

直接求「存在至少一条根到叶子的全白路径」的概率会因为路径共享边变得非常复杂，所以先算它的对立事件：所有根到叶子的路径都至少包含一条黑边。记这个对立事件的概率为Q(n)，那么我们要求的概率P(n) = 1 - Q(n)。

深度为n的满二叉树，根节点连接两个完全独立的深度为n-1的满二叉子树（左、右子树）。对于左子树来说，「所有经过左子树的路径都非全白」的概率由两种情况组成：

• 根到左子树的边是黑色：概率0.5，此时不管左子树内部的边是什么颜色，这些路径都不可能是全白的；
• 根到左子树的边是白色：概率0.5，此时左子树内部的所有路径必须都非全白（也就是左子树满足Q(n-1)）。

所以左子树满足条件的概率是 0.5 + 0.5*Q(n-1)，右子树同理。由于左右子树独立，整体对立事件的概率就是两者的乘积：

Q(n) = [0.5*(1 + Q(n-1))]^2

初始条件：当n=1时，树只有2个叶子，所有路径都非全白的概率是两条边全黑的概率，即0.5*0.5=0.25，所以Q(1)=0.25，对应的P(1)=1-0.25=0.75。

令d(n) = 1 - Q(n)（也就是我们最终要求的P(n)），把它代入递推式并化简：

d(n) = 1 - [(1 + (1 - d(n-1)))/2]^2
d(n) = d(n-1) - d(n-1)²/4

当n足够大时，d(n)会变得很小（因为Q(n)趋近于1，几乎所有路径都非全白），此时d(n-1)²/4是高阶小项，我们可以用近似公式1/(1-x) ≈ 1+x（当x很小时）对式子取倒数：

1/d(n) ≈ 1/[d(n-1)*(1 - d(n-1)/4)] ≈ 1/d(n-1) + 1/4

这是一个调和级数形式的递推——每一步1/d(n)都会比前一项增加1/4。当n很大时，初始项的影响可以忽略，我们得到：

1/d(n) ≈ n/4 + 常数

也就是说d(n) ≈ 4/(n + C)（C是常数），即d(n) = Θ(1/n)，也就是我们要求的P(n)=Θ(1/n)。

对应选项 B) Θ(1/n)

内容的提问来源于stack exchange，提问作者asaf92