结论

  • 抛n次硬币，记x为正面朝上次数，求x的k次幂的期望
  • 有m张不同的牌，随机洗牌并取牌顶，重复n次，记x为取到某特定牌的次数，求x的k次幂的期望

形如以上，满足以下条件的问题：

  1. 随机变量是指标函数之和
  2. 每个指标函数有明确定义的期望，最好互相独立
  3. 允许多重元组并考虑重复时的概率

可以将问题转换为求k元组的个数。

思路

以有m张不同的牌，随机洗牌并取牌顶，重复n次，记x为取到某特定牌的次数，求x的k次幂的期望为例子：

记 为指示函数，表示第i次洗牌是否为好，其中 ：

  • 表示该次洗牌所需特定牌在牌顶
  • 表示其他情况

那么可以将x表示为

所求期望转换为

将其展开

故而有

每一个 元组 ，我们关心的是这 个编号是否都是好编号，故可以认为：

每个元组贡献的期望值为这组编号全是好编号的概率

把所有可能的元组的概率加起来，就等于 ​

而k元组个数可以通过dp简单求得

简单例子

有2张牌，抽取3次，求的期望

设 是每次洗牌是否为“好”的指示变量：

展开

转换为元组考虑

考虑所有 的 2 元组，共 个：

元组
(1,1)
(1,2), (2,1)
(1,3), (3,1)
(2,2)
(2,3), (3,2)
(3,3)

其他

写CF1278F时学到的新东西，觉得好神奇又好像有点典，故而记录

CF1278F