数学期望和组合计数有许多共通之处,可以看作是带系数的计数。
Part 1 记号和定义
在本文中:
-
仅讨论在值域中均匀随机的随机变量;
-
设 为某随机变量,即取值在值域中随机的变量,则 为 取到 的概率;
-
设 为某随机变量,则 表示 的期望值,即 或 ;
Part 2 性质和技巧
把期望看作带系数计数 与 考虑组合意义 都是常用的推导方法。
2.0 约定
- 证明中只用到了 且没有特殊说明:这里只证明值域离散(随机变量只能取整数)的情况下的性质,值域连续(随机变量可以取实数)的情况下也有这些性质,将这些证明中的 换成 即可证明;
- 证明中用到了 且没有特殊说明:这些性质只有在值域连续的情况下才能存在;
2.1 基础性质
设 和 为某两随机变量(不一定无关,即它们可能会互相影响)。
-
可加性:
证明
Q.E.D.
-
线性性:
对于某常数 ,有:
证明
Q.E.D.
-
无关可乘性:
若 与 无关,即一个的取值不会影响到另一个,则有:
证明
Q.E.D.
2.2 常用技巧
若无特殊说明,公式中出现的变量均为随机变量。
-
发生事件期望所需次数:
若某事件每次发生的概率为 ,其中 是一个确定的实数,则发生该事件所需的期望次数为 。
证明
Q.E.D.
-
分配:
即每一个 中一共有 项相乘,第 项可以是 中的任意一个。
拆括号后运用期望的可加性即可证明,第二条是第一条的拓展。
-
个值域相同的随机变量的第 小值的期望:
设 个在 间的连续随机变量 ,则 。
设 个在 间的离散随机变量 ,则 。
证明
先证明第一条。
引入另一个 间的连续随机变量 ,设 为 的概率,那么 。
考虑给所有随机变量升序排序,相同则按原来的位置排,那么一共有 种顺序,其中 排在前 位的一共有 种顺序,具体的考虑插入即可。
那么 。
第二条相当于第一条把 乘上 然后取整转化为离散情况。
Q.E.D.
Part 3 例题
3.1 期望参与答案计算
-
查看题解
考虑设第 次洗牌后第一张牌的情况为 (是王牌则 ,否则 ),那么显然 。
发现答案等价于 ,根据 2.2 中的分配技巧,这个东西相当于:
即每一个 中一共有 项相乘,第 项可以是 中的任意一个。
考虑一项一项填入 中,由于不同的 互相独立且本质相同,则 。而相同的 取值肯定一样,那么我们只需要关心有多少个不同的 。
设 表示确定了前 项,其中一共有 个不同的 。显然 ,转移考虑下一位填入的 是否出现过:
最后答案即为 。
时间复杂度 。