基于容斥原理求解至少x位宾客到场概率的错误排查与疑问

问题背景 #

邀请n位宾客参加生日派对，给定整数x和包含n个元素的列表（列表第i个元素为宾客i的到场概率），需计算至少x位宾客到场的概率。

尝试用容斥原理求解的步骤：

• 生成宾客概率列表中所有元素数量≥x的子集；
• 计算每个子集内宾客都到场的概率（子集元素概率相乘）；
• 对大小为x+2k（k为非负整数）的子集概率求和，对大小为x+1+2k的子集概率做减法。

遇到的问题：最终结果超出[-1,1]范围，需明确：

1. 该思路存在什么错误？
2. 容斥原理是否仅能从元素数≥1的基础子集开始应用？

附修正后的Java代码 #

public class PartyProbability {
    public static void main(String[] args) {
        int x = 5;

        double[] guests = new double[] {0.34, 0.24, 0.72, 0.28, 0.55, 0.88, 0.91, 0.99, 0.01, 0.46};
        
        ArrayList<Double> subset = new ArrayList<>();
        ArrayList<ArrayList<Double>> subsets = new ArrayList<>();
        getSubsets(subset, subsets, 0, guests, x);
        
        double probx = 0;
        
        for (ArrayList<Double> s : subsets) {
            double prob = 1;
            for (double p : s) {
                prob *= p;
            }
         
            if ((s.size() % x) % 2 == 0) {
                probx += prob;
            } else {
                probx -= prob;
            }
        }
        
        System.out.println(probx);
    }

    public static void getSubsets(ArrayList<Double> tmp, ArrayList<ArrayList<Double>> subsets, int i, double[] guests, int minSize) {
        if (i == guests.length) {
            if (tmp.size() >= minSize) {
                subsets.add(new ArrayList<>(tmp)); // 修正：添加副本，避免引用共享
            }
            return;
        }
        ArrayList<Double> newSet = new ArrayList<>(tmp);
        newSet.add(guests[i]);

        getSubsets(newSet, subsets, i + 1, guests, minSize);
        getSubsets(tmp, subsets, i + 1, guests, minSize);
    }
}

错误分析与解答 #

1. 思路核心错误 #

（1）容斥的符号与计数逻辑完全错误

当前的符号判断条件(s.size() % x) % 2 == 0完全不符合容斥原理的要求。计算至少x人到场的概率时，容斥的符号应该基于子集大小与x的差值的奇偶性：

• 大小为x的子集：加
• 大小为x+1的子集：减
• 大小为x+2的子集：加
• 以此类推，即符号为(-1)^(k - x)，其中k是子集大小。

更关键的是，容斥计算至少x人到场时，每个k元子集的概率不能直接加减——因为每个k元子集对应的「k人到场」事件，会被包含在多个更大的子集中，需要用组合数C(k-1, x-1)修正权重，正确的公式为：

P(至少x人到场) = Σ（k从x到n）[ (-1)^(k-x) * C(k-1, x-1) * S_k ]

其中S_k是所有k元子集的到场概率乘积之和。忽略权重修正会导致重复计算的部分无法抵消，结果溢出概率范围。

（2）概率计算遗漏了子集外宾客的状态

仅计算子集内宾客到场的概率，会导致每个包含该子集的更大集合的事件重复计算这个概率，结果被无限放大，必然超出[0,1]范围。容斥中需要明确每个项对应的事件边界，避免重复统计。

（3）代码实现的细节错误

原getSubsets方法直接将tmp添加到subsets，但递归过程中tmp是共享的列表引用，会导致所有子集最终指向同一个列表，数据混乱。修正方法是添加tmp的副本new ArrayList<>(tmp)。

2. 容斥原理的应用范围 #

容斥原理并非只能从元素数≥1的子集开始应用，它的应用取决于你要计算的事件定义。比如计算至少x人到场，可以从「选x人必须到场，其余任意」的事件出发，通过容斥修正重复计算的部分；也可以先计算补集（最多x-1人到场）再用1减去，补集的计算同样可以用容斥，从0人到场、1人到场的事件开始累加修正。

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