嵌套集合中两种随机选取元素方式的概率一致性问题

这是个很经典的概率问题，咱们先拿具体例子拆解，再用数学推导验证，就能把道理讲得明明白白。

先看直观例子 #

假设咱们有两本书（对应两个大小不同的集合）：

• 书X（小集合）：只有10页（每个页面是集合里的元素）
• 书Y（大集合）：有90页

方式1：直接选所有(集合,元素)元组

所有可能的元组总数是10+90=100个。随便选一个，不管是书X还是Y里的页面，每个页面被选中的概率都是1/100——因为每个元组被选中的概率均等。

方式2：先选集合，再选元素

第一步：随机选一本书，选书X和书Y的概率各是1/2。
第二步：从选中的书里随机选一页：

• 书X里的任意一页被选中的概率是：(1/2) * (1/10) = 1/20 = 5%
• 书Y里的任意一页被选中的概率是：(1/2) * (1/90) = 1/180 ≈ 0.56%

一眼就能看出来：小集合（书X）里的页面，被选中的概率远高于大集合里的页面。

再用数学公式通用推导 #

设总共有n个集合，第i个集合的大小为s_i，所有集合的总元素数为S = s₁ + s₂ + ... + sₙ。

方式1的概率

每个元素对应的(集合,元素)元组只有1个，总共有S个元组，所以任意元素被选中的概率是：

P₁ = 1/S

方式2的概率

先选第i个集合的概率是1/n，再从该集合中选到目标元素的概率是1/s_i，所以目标元素被选中的总概率是：

P₂ = (1/n) * (1/s_i)

对比两种概率

当集合大小不均时，S = Σs_i，对于小集合（s_i更小），1/(n*s_i)会大于1/S；反之大集合的元素概率会更小。只有当所有集合大小相等（s₁=s₂=...=sₙ）时，S = n*s_i，此时P₁=P₂，两种方式概率一致。

结论 #

两种选取方式下，元素被选中的概率不一致——第二种方式会让小集合中的元素拥有更高的选中概率。

内容的提问来源于stack exchange，提问作者WGroleau