数学期望学习笔记

数学期望和组合计数有许多共通之处，可以看作是带系数的计数。

Part 1 记号和定义

在本文中：

• 仅讨论在值域中均匀随机的随机变量；

• 设 $x$ 为某随机变量，即取值在值域中随机的变量，则 $P_x(i)$ 为 $x$ 取到 $i$ 的概率；

• 设 $x$ 为某随机变量，则 $\mathbb E(x)$ 表示 $x$ 的期望值，即 $\sum\limits_{i} i\cdot P_x(i)$ 或 $\int i\cdot P_x(i)\,di$；

Part 2 性质和技巧

把期望看作带系数计数 与 考虑组合意义 都是常用的推导方法。

2.0 约定

• 证明中只用到了 $\sum$ 且没有特殊说明：这里只证明值域离散（随机变量只能取整数）的情况下的性质，值域连续（随机变量可以取实数）的情况下也有这些性质，将这些证明中的 $\sum\limits_{i}$ 换成 $\int\,di$ 即可证明；
• 证明中用到了 $\int$ 且没有特殊说明：这些性质只有在值域连续的情况下才能存在；

2.1 基础性质

设 $x$ 和 $y$ 为某两随机变量（不一定无关，即它们可能会互相影响）。

• 可加性：

  $\mathbb E(x+y)=\mathbb E(x)+\mathbb E(y)$

  证明

  $\begin{aligned} \mathbb E(x+y)&=\sum\limits_{i} i\cdot \sum \limits_{j}P_x(j)P_y(i-j)\\ &=\sum\limits_{j}P_x(j)\sum\limits_{k}P_y(k)\cdot(j+k)\\ &=\sum\limits_{j}j\cdot P_x(j)+\sum\limits_{k}k\cdot P_y(k) \end{aligned}$

  Q.E.D.

• 线性性：

  对于某常数 $\alpha$，有：

  $\mathbb E(\alpha x)=\alpha \mathbb E(x)$

  证明

  $\mathbb E(\alpha x)=\sum\limits_{i}\alpha \cdot P_x(i)=\alpha\sum\limits_{i}i\cdot P_x(i)=\alpha\mathbb E(x)$

  Q.E.D.

• 无关可乘性：

  若 $x$ 与 $y$ 无关，即一个的取值不会影响到另一个，则有：

  $\mathbb E(xy)=\mathbb E(x)\cdot\mathbb E(y)$

  证明

  $\mathbb E(xy)=\sum\limits_{i}\sum\limits_{j}ij\cdot P_x(i)P_y(j)=\mathbb E(x)\cdot \mathbb E(y)$

  Q.E.D.

2.2 常用技巧

若无特殊说明，公式中出现的变量均为随机变量。

• 发生事件期望所需次数：

  若某事件每次发生的概率为 $a$，其中 $a$ 是一个确定的实数，则发生该事件所需的期望次数为 $\frac{1}{a}$。

  证明

  $\mathbb E=a+(1-a)(\mathbb E+1)\\ \mathbb E=a+\mathbb E+1-a\mathbb E-a\\ a\mathbb E=1\\ \mathbb E=\frac{1}{a}$

  Q.E.D.

• 分配：

  $\mathbb E((a+b)(c+d))=\mathbb E(ac)+\mathbb E(ad)+\mathbb E(bc)+\mathbb E(bd)$

  $\mathbb E\left(\prod\limits_{i=1}^n\sum\limits_{j=1}^m x_{i,j}\right)=\\ \mathbb E(x_{1,1}\times x_{2,1}\times \dots \times x_{n,1})+E(x_{1,2}\times x_{2,1}\times \dots \times x_{n,1})+\dots+E(x_{1,m}\times x_{2,m}\times \dots \times x_{n,m})$

  即每一个 $\mathbb E()$ 中一共有 $n$ 项相乘，第 $i$ 项可以是 $x_{i,[1,m]}$ 中的任意一个。

  拆括号后运用期望的可加性即可证明，第二条是第一条的拓展。

• $n$ 个值域相同的随机变量的第 $k$ 小值的期望：

  设 $n$ 个在 $[0,1]$ 间的连续随机变量 $x_{1\sim n}$，则 $\mathbb E\left(\text{kth-min}_k\{x_i\}\right)=\frac{k}{n+1}$。

  设 $n$ 个在 $[1,m]$ 间的离散随机变量 $x_{1\sim n}$，则 $\mathbb E\left(\text{kth-min}_k\{x_i\}\right)=\frac{km}{n+1}$。

  证明

  先证明第一条。

  引入另一个 $[0,1]$ 间的连续随机变量 $y$，设 $P(i)$ 为 $i\le\text{kth-min}_k\{x_i\}$ 的概率，那么 $\mathbb E\left(\text{kth-min}_k\{x_i\}\right)=\frac{\int_0^1 P(i)\,di}{1}=P(y)$。

  考虑给所有随机变量升序排序，相同则按原来的位置排，那么一共有 $(n+1)!$ 种顺序，其中 $y$ 排在前 $k$ 位的一共有 $kn!$ 种顺序，具体的考虑插入即可。

  那么 $P(y)=\frac{kn!}{(n+1)!}=\frac{k}{n+1}=\mathbb E\left(\text{kth-min}_k\{x_i\}\right)$。

  第二条相当于第一条把 $x_i$ 乘上 $m$ 然后取整转化为离散情况。

  Q.E.D.

Part 3 例题

3.1 期望参与答案计算

• CF1523E Crypto Lights | 题解

• CF1278F Cards

  查看题解

  考虑设第 $i$ 次洗牌后第一张牌的情况为 $x_i$（是王牌则 $x_i=1$，否则 $x_i=0$），那么显然 $\mathbb E(x_i)=\frac{1}{m}$。

  发现答案等价于 $\mathbb E\left(\left(\sum\limits_{i=1}^n x_i\right)^k\right)$，根据 2.2 中的分配技巧，这个东西相当于：

  $\mathbb E(x_1^k)+\mathbb E(x_1^{k-1}x_2)+\dots+\mathbb E(x_n^k)$

  即每一个 $\mathbb E()$ 中一共有 $k$ 项相乘，第 $i$ 项可以是 $x_{[1,n]}$ 中的任意一个。

  考虑一项一项填入 $\mathbb E()$ 中，由于不同的 $x_p$ 互相独立且本质相同，则 $\forall p_1\not=p_2,\mathbb E(x_{p_1}x_{p_2})=\mathbb E(x_{p_1})\mathbb E(x_{p_2})=\frac{1}{m^2}$。而相同的 $x_p$ 取值肯定一样，那么我们只需要关心有多少个不同的 $x_p$。

  设 $f_{i,j}$ 表示确定了前 $i$ 项，其中一共有 $j$ 个不同的 $x_p$。显然 $f_{0,0}=1$，转移考虑下一位填入的 $x_p$ 是否出现过：

  $f_{i,j}=f_{i-1,j}\times j+f_{i-1,j-1}\times (n-j+1)\times \frac{1}{m}$

  最后答案即为 $\sum\limits_{i=0}^k f_{k,i}$。

  时间复杂度 $O(k^2)$。

• CF1842G Tenzing and Random Operations

3.2 期望参与时间复杂度计算

• 【2023NOIP模拟赛09】补幺梨