指定约束下随机子集前4个并集的期望大小求解
我最近碰到这么个概率问题,想和大家探讨一下求解思路:
假设$A_1, A_2, A_3, A_4, A_5, A_6$是从集合${1, 2, \ldots, 200}$里随机均匀选出的子集,每个子集$A_i$的大小都是14,而且这6个子集的并集大小固定为60。我现在想算出前4个子集的并集$|\bigcup_{i=1}^4 A_i|$的期望值。
我自己先尝试了一种近似的处理思路,分享给大家:
我知道并集大小可以用容斥原理来近似,只保留前两项的话,有这么个公式:
$$
|\bigcup_{i=1}^6 A_i| \approx \sum_{i=1}^6 |A_i| - \binom{6}{2} |A_1 \cap A_2|
$$
把已知的数值代入进去,就得到了:
$$
60 = 6 \times 14 - 15x
$$
这里我设$x = |A_1 \cap A_2|$——因为子集是对称选取的,任意两个子集的交集大小期望都相同。接下来解这个方程求$x$:
$$
60 = 84 - 15x \implies 15x = 24 \implies x = \frac{24}{15} = \frac{8}{5} = 1.6
$$
基于这个结果,我可以继续用类似的近似思路计算目标期望:前4个集合的并集大小期望近似为容斥前两项的计算结果:
$$
E\left[|\bigcup_{i=1}^4 A_i|\right] \approx 4 \times 14 - \binom{4}{2}x = 56 - 6 \times 1.6 = 56 - 9.6 = 46.4
$$
要说明的是,这个方法是近似解法,因为完整的容斥原理还包含更高阶的交集项没考虑进去,但如果高阶交集的期望很小的话,这个近似结果应该会比较接近真实值。
备注:内容来源于stack exchange,提问作者Abul Kalam

