前言

帮助学习期望概率的几道题。

换教室

用期望的线性性分解问题就行了。

在这题里，邮票可以只有拥有和未拥有之分。

有几种做法

花的钱可以用购买次数的期望和购买次数平方的期望的线性组合来表示。

f[i] 表示拥有了 i 张，还需购买次数的期望； g[i] 则表示拥有了 i 张，还需购买次数的平方的期望。

[f[i] = frac{i}n(f[i]+1) + frac{n-i}n(f[i+1]+1) ]

(g[i]) 的推导可以帮助萌新成长为不算很萌的萌新。

我开始的时候挺疑惑：用了全期望公式后，后面的那个东西是不是没法维护？
但其实可以的。在全期望公式的每个概率后面乘的那个东西其实是下一个状态的 " '还需购买次数加一'的平方"的期望，在用一次期望的线性性分解，于是：

[g[i] = frac{i}n(g[i]+2f[i]+1) + frac{n-i}n(g[i+1]+2f[i+1]+1) ]

但这种理解并不够。

从这种 “定义balabala……” 的视角下很难对题目有清晰的思路，看到题一开始就用直觉搞这种定义有可能会踩坑，这样会踩坑的一个可能原因是将注意力集中在所定义的东西上，由于定义所含的信息量不够大或者忽略了一些细节，就很有可能踩坑了。

但这题的样本空间是无限大的，我还没法清晰地解释这道题。

或许应该重新看看全期望公式了。

题解链接在标题，我在这里简（bu）述（hui）。

推荐阅读这个题解。

每次操作的对象是一个叶节点，结果是这个叶节点不是叶节点了，其增加了两个为叶节点的儿子，样本空间是一堆有 n 个叶节点的二叉树。

对于第一问，用期望的线性性将叶节点深度平均值的期望值转化为叶节点总深度的期望值除以 n 。

设 (f[i]) 表示叶子节点为 (i) 个的树的叶节点总深度的期望, 由于 (f[i]) 可以用期望的线性性分解为 dfs 序为 1~i 的叶节点的深度的期望的和，所以有：

[f[i] = dfrac{i*f[i-1]+2*(i-1)}{i-1} ]

对于第二问，我看题解是直接套期望的第一定义式算的（就是平均值那个），所以我也试试。

设 (p[i][h]) 为有 i 个节点的树深度为 h 的概率。

看不懂，撤了撤了。