期望的线性性

do_while_true · 2021-06-27 18:02:05 · 个人记录

期望的线性性：两个(或多个)随机变量的和的期望等于期望的和。

证明

连续变量：

如何证明期望的线性性质？ - StarDust的回答 - 知乎 https://www.zhihu.com/question/59209320/answer/1518199609

可以由两个推广至多个。

栗子一：Codeforces 208C C. Game on Tree

删掉树的期望次数=每个点被选择的期望次数的和。

考虑每个点被选择的期望次数，只与它和它的祖先有关，其他的点没有关系可以忽略。

设这个点的深度为 d，考虑这个点被选择当且仅当它比它所有祖先都先被删掉，也就是长度为 d 的排列，共有 d! 种，钦定一个点在最前面有 (d-1)! 种，所以概率为 \frac{(d-1)!}{d!}=\frac{1}{d!}。

答案即为 \sum \frac{1}{d_i}