从同一总体抽取的随机样本移除交叠元素后的平均规模计算

问题背景 #

我们有一个包含N个元素的总体（瓮模型），抽取m个独立样本（样本间是放回抽样，即每次抽取一个样本后将所有元素放回总体；单个样本内部是无放回抽样）。对于每个样本，我们移除所有至少出现在另一个样本中的元素，需要计算处理后每个样本的平均规模（即期望规模）。

已知约束：N<100，单个样本大小<10，样本数量m∈{2,3,4}。目前可以用蒙特卡洛模拟近似求解，但希望找到精确公式提升效率。

示例验证 #

• 当N=2，样本1大小1、样本2大小2时：
  • 样本1处理后平均规模：0
  • 样本2处理后平均规模：1
• 当N=3，样本1大小1、样本2大小2时：
  • 样本1处理后平均规模：1/3 ≈ 0.333
  • 样本2处理后平均规模：4/3 ≈ 1.333

精确解法推导 #

我们利用期望线性性来简化计算，无需考虑元素间的依赖关系：

1. 对于任意样本i（原始大小为k_i），我们关注其中单个元素x的保留概率：

   • 元素x在样本i中（已经被选中），且不在其他任何样本中时，才会被保留。
   • 由于样本间是独立抽样，x是否出现在其他样本与它是否在样本i中无关。
   • x不被选入某个其他样本j（j≠i）的概率为：$\frac{N - k_j}{N}$（从N-1个不含x的元素中选k_j个的组合数，除以总组合数）。
   • 因此，x不被选入所有其他样本的概率为：$\prod_{j \neq i} \frac{N - k_j}{N}$

2. 样本i的期望新规模等于原始大小乘以单个元素的保留概率：
   $$
   E_i = k_i \times \prod_{j \neq i} \frac{N - k_j}{N}
   $$

公式验证 #

用之前的示例验证：

• 示例1：N=2，k₁=1，k₂=2
  • $E_1 = 1 \times \frac{2-2}{2} = 0$
  • $E_2 = 2 \times \frac{2-1}{2} = 1$
• 示例2：N=3，k₁=1，k₂=2
  • $E_1 = 1 \times \frac{3-2}{3} = \frac{1}{3}$
  • $E_2 = 2 \times \frac{3-1}{3} = \frac{4}{3}$
    完全匹配示例结果！

精确计算代码实现 #

替换蒙特卡洛模拟，用公式直接计算，效率大幅提升：

def exact_calculation(population_size, samples_sizes):
    N = population_size
    m = len(samples_sizes)
    results = []
    for i in range(m):
        k_i = samples_sizes[i]
        product = 1.0
        for j in range(m):
            if i == j:
                continue
            product *= (N - samples_sizes[j]) / N
        e_i = k_i * product
        results.append(e_i)
    
    # 输出结果
    print(f'population size is {N}')
    for idx in range(m):
        print(
            f'sample {idx + 1}: original_size={samples_sizes[idx]}, new_size={results[idx]}')

# 测试示例
exact_calculation(2, [1, 2])
exact_calculation(3, [1, 2])

# 随机测试（和原蒙特卡洛对比）
from random import randint
population_size = 12
samples_count = randint(2, 4)
samples_sizes = [randint(1, population_size) for _ in range(samples_count)]
print("\n精确计算结果：")
exact_calculation(population_size, samples_sizes)

代码说明 #

• 直接遍历每个样本，计算对应乘积项后得到期望新规模，时间复杂度为O(m²)，远优于蒙特卡洛的O(iterations*m²)。
• 结果是精确值（浮点数或分数，若用分数运算可保留完全精确性），无需迭代模拟。

对比蒙特卡洛模拟 #

蒙特卡洛模拟通过大量重复抽样逼近期望，适合复杂场景，但存在随机误差且效率较低；而精确公式直接计算出理论期望，无误差且计算极快，完全适配当前问题的约束条件（N<100，样本数2-4，样本大小<10）。

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