近似计算二项随机变量线性组合小于指定值的概率的方法咨询

数据老陈

2026-4-17

嗨，太懂你这种头疼的处境了——每次微调几个$n_i$之后，都要枚举所有满足$\sum c_i x_i < c$的$n$元组来求和PMF，计算量直接上天，尤其是当$n$或者$n_i$有点规模的时候，完全是吃力不讨好的活儿。下面给你几个实用的替代方案，从近似到精确优化都有，你可以根据自己的场景挑：

1. 正态近似法（中心极限定理）

适用场景：当每个$X_i$的$n_i$都不算太小的时候，这个方法的效果会很靠谱，毕竟二项分布本身在$n$较大时就会趋近正态分布。
具体操作：先算线性组合$Y = \sum c_i X_i$的期望和方差：
- 期望：$E[Y] = \sum c_i n_i p_i$
- 方差：$Var(Y) = \sum c_i^2 n_i p_i (1-p_i)$（因为变量独立，方差直接相加）
  然后把$Y$近似成正态分布$N(E[Y], Var(Y))$，用正态分布的累积分布函数（CDF）来计算$P(Y < c)$。如果要更精准，因为$Y$是离散变量，正态是连续的，可以加个连续性修正：比如计算$P(Y < c)$时，近似成$\Phi\left(\frac{c - 0.5 - E[Y]}{\sqrt{Var(Y)}}\right)$，这里$\Phi$是标准正态分布的CDF。
优势：计算速度快到离谱，每次$n_i$微调后，只需要重新算期望和方差就行，几乎没额外开销。

适用场景：比正态近似精度高得多，尤其是在计算尾部概率（比如$c$远小于$Y$的均值）或者$n_i$不算特别大的时候，鞍点近似是目前离散分布近似里的“优等生”。
具体操作：
- 先求$Y$的矩生成函数（MGF）：$M_Y(t) = \prod_{i=1}^n (1 - p_i + p_i e^{c_i t})^{n_i}$，因为每个二项分布$X_i$的MGF是$(1-p + pe^t)n$，线性组合的MGF就是各变量MGF在$c_i t$处的乘积。
- 找到鞍点$t_0$：满足$\frac{M_Y'(t_0)}{M_Y(t_0)} = c$（对应$Y$的均值等于$c$的情况，针对$P(Y < c)$需要微调这个条件），然后用鞍点近似的公式计算CDF。
优势：精度碾压正态近似，尤其是极端情况，而且计算量也不大——每次$n_i$微调后，只需要重新计算MGF的导数和解方程找$t_0$，比枚举$n$元组快N倍。

适用场景：如果$n$不算太大，而且每次$n_i$的微调幅度很小（比如只改几个$n_i$，或者每个$n_i$只±1），这个方法可以复用之前的计算结果，大幅减少重复劳动。
具体操作：
- 把问题拆成逐步累加的过程：先算第一个变量$c_1X_1$所有可能取值的概率分布，然后和第二个变量$c_2X_2$的分布做卷积，得到前两个变量线性组合的分布，以此类推，直到得到$Y$的完整概率分布。
- 当$n_i$微调时，比如某个$n_i$从$k$变成$k+1$，只需要更新这个变量对应的分布部分，再做一次局部卷积就行，不用从头开始计算所有步骤。
优势：能得到精确的概率分布，而且在$n_i$微调幅度小时，复用之前的结果后效率比枚举高太多；当然如果$n$或者$n_i$太大，内存和计算量还是会上来，但肯定比枚举$n$元组强。

适用场景：当其他方法都不好操作（比如$c_i$有正有负，或者$n$很大但$n_i$很小），蒙特卡洛是万能的兜底方案。
具体操作：
- 生成大量独立样本：每个样本里，对每个$X_i$，用当前的$n_i$和固定的$p_i$生成一个二项分布的样本值$x_i$，然后计算$\sum c_i x_i$，统计其中小于$c$的样本占比，这个占比就是$P(Y < c)$的近似值。
- 样本量越大精度越高，比如生成10^5到106个样本，一般就能满足大部分工程需求。
优势：实现超级简单，不管$c_i$正负、$n$多大都能做；每次$n_i$微调后，只需要重新生成对应变量的样本，代码改动极小。
注意点：如果是极端尾部概率（比如$P(Y < c)$只有1e-6），蒙特卡洛需要的样本量会大到离谱，这时候不如用鞍点近似。

备注：内容来源于stack exchange，提问作者Rohit Pandey