ARC150D-一类期望问题的思考方式

题意

• 给你一棵有根树，定义一个点合法当且仅当它到根上的点全为黑色，否则不合法。

• 最开始所有点为白色，每次选一个不合法的点涂黑，每个点可以被涂黑多次。

• 问所有点被涂黑的期望次数

思考1

这次想题引爆了某人概率论基础不扎实的炸弹。

考虑每个点被涂黑的顺序，是一个排列，取到每种排列的概率相同。

考虑使用全期望公式计算，先考虑固定一个排列时的答案。

先假设只有 \(3\) 个点，且顺序为 \(3,2,1\)，也就是赠券收集问题。

选第一个点的期望次数为 \(1\)，因为所有满足这个排列的样本点都是以 \(3\) 开头，选第二个点，期望次数是多少，或者说，选出第一个点后，下一个被选择的点，在顺序为 \(3,2,1\) 的前提下，是 \(2\) 的概率是多少？

\(\frac{1}{2}\) 的来历

选第二个点时，可以选的点有 \(3,2\)，选择每个点的概率相同，所以概率为 \(\frac{1}{2}\)

虽然原本每个点概率时相同的，但是我们求的时条件概率，条件概率的样本空间已经被改变了，所以选择每个点的概率不再相同。

\(\frac{2}{3}\) 的来历

考虑概率的定义，\(P=\frac{事件大小}{样本空间大小}\)，考虑该条件的集合和事件与条件的交集，因为此题样本空间无限大，所以考虑将一个无限长序列映射到我们的样本空间，容易发现这样的映射不会改变概率函数。

设 \(k\) 为已经选取的数的个数，\(n\) 为数的总数。 $$ \[\begin{align} P=&\lim\limits_{m\rightarrow \infty}\dfrac{n^{m-1}}{\sum\limits_{1\le i\le m} k^{i-1}\times n^{m-i}}\\ =&\dfrac{n^{m-1}}{\frac{n^{m}}{n-k}}\\ =&\frac{n-k}{n} \end{align}\] $$ 这是在正确的样本空间算出的正确结果。

从 Beyes 公式考虑： \[ \begin{align} P(下一个值为目标|满足排列限制)=&\dfrac{P(下一个值为目标\wedge满足排列限制)}{P(满足排列限制)}\\ =&\dfrac{\frac{1}{n}\times\frac{1}{(n-k-1)!}}{\frac{1}{(n-k)!}}\\ =&\dfrac{n-k}{n} \end{align} \] 神奇吧？

贝叶斯公式连接了条件概率和原问题的样本空间。

总结

样本空间无限大的时候要小心，不能轻易认为两个元素等价，因为此时 \(\infty \ne \infty\)。

用贝叶斯公式好好算算吧。

草率的断言概率为 \(\frac{1}{2}\)，很大一部分原因都是认为两个正无穷时相等的。

有了这个东西就可以愉快的推狮子 NTT 了。

思考2

其实这种题还有一种更加普遍的做法，期望线性性，考虑每个点被选的次数，相加可以得到最终答案。

期望线性性来源于期望的定义，一个随机变量是一个函数，定义域为样本空间，值域为 \(\R\)，随机变量的期望为其密度函数积分的收敛值。

因此，无论两个随机变量是否独立，它们的期望都是可加的。

感性理解的话，两个随机变量之和的期望等于这样一个随机变量的期望：每个样本点的取值为两个随机变量在该样本点的取值之和，期望可以粗略理解为随机变量在样本空间每个点的平均值，因此随机变量的期望可加。

所以可以考虑每个点被选的期望次数，如果选到了不在这个点到根路径上的点，那么我们忽略这一次选择，这样的忽略不会影响这个点被选的期望次数，然后问题变成了一条链上的最后一个点被选择的期望次数。

注意，我们只关心这个点被选择的期望次数。

考虑怎么求这玩意，因为整个过程在点到根路径上所有点被选择之后才会结束，所以像赠券收集问题一样倒序。假设有 \(k\) 个点还没选，总共 \(n\) 个点，其中 \(w\) 个点可以选，那么转移答案是 \(dp[k]=\frac{k}{w}dp[k+1]+\frac{w-k}{w}dp[k]+\frac{1}{w}\)

移项得到 \(dp[k]=dp[k+1]+\frac{1}{k}\)，实际上和 \(w\) 无关，所以就很好算了。

官方题解的说法是如果考虑可以选已经 good 的点，最终答案不变，我理解不了这个过程。

upd：其实现在也可以理解了，因为如果选了已经 good 的点，那么再选一次就行了。

有几个比较重要的地方，一是忽略和答案绝对无关的操作，二是考虑计算过程。