泊松二项分布

泊松二项分布（Poisson binomial distribution）是有限个独立伯努利变量之和的分布，各次成功概率可以不同。它的取值仍为成功总数；名称中包含“泊松”，不表示总数具有泊松质量函数，也不要求先对试验次数作泊松抽样。

三个独立装置在一次合成试验中成功的概率分别为0.2、0.5、0.8。总成功数 S 的均值为1.5，但不能把三者都替换为成功率0.5的装置来精确恢复整个分布。下面逐次合并，得到四个概率 $(0.08,0.42,0.42,0.08)$。

定义与生成多项式

设 $X_1,\dots ,X_n$ 相互独立，$X_i\sim \mathrm{Bernoulli}(p_i)$，$0\le p_i\le 1$、$n\in {\mathbb{Z}}_{\ge 0}$。定义 $S=\sum _i{X}_i$。其概率生成多项式为 $$G(z)=𝔼z^S=\prod _{i=1}^n[(1-p_i)+p_{i}z].$$ 独立性使乘积期望分解。展开时，每一项选择一组成功位置 A，故 $$Pr(S=k)=[z^k]G(z)=\sum _{A\subseteq \{1,\dots ,n\},|A|=k}\prod _{i\in A}{p}_i\prod _{j\notin A}(1-p_j).$$ 系数非负，且 $G(1)=1$，证明归一化。若有 a 个概率等于一、b 个严格介于零与一，其正概率支撑是整数区间 $\{a,\dots ,a+b\}$；零概率试验不增加支撑。空和 n=0 时 S 恒为零。

一次只合并一个伯努利变量

记 $f_i(k)=Pr(X_1+\cdots +X_i=k)$，从 $f_0(0)=1$ 开始，范围外视为零。按最后一次失败或成功划分这两个不交事件： $$f_i(k)=(1-p_i)f_{i-1}(k)+p_i{f}_{i-1}(k-1).$$ 第一项保持成功数，第二项把旧成功数增加一。它们覆盖全部情形；独立性保证末次概率可与旧计数概率相乘。这既是递推公式，也是算法每一层存储完整部分和分布的归纳不变量。

主例的中间结果依次是 $(0.8,0.2)$、$(0.4,0.5,0.1)$，最后一层为 $$\begin{array}{cc}{f}_3(0)& =0.2\cdot 0.4=0.08,\\ f_3(1)& =0.2\cdot 0.5+0.8\cdot 0.4=0.42,\\ f_3(2)& =0.2\cdot 0.1+0.8\cdot 0.5=0.42,\\ f_3(3)& =0.8\cdot 0.1=\mathrm{0.08.}\end{array}$$ 因此至少两个成功的概率为 $0.42+0.08=0.5$。

第 i 行是前 i 次试验的完整计数分布；横列 k 是成功数。

Python 3

import math

def poisson_binomial(probabilities):
    p = tuple(probabilities)
    if any(not math.isfinite(x) or not 0 <= x <= 1 for x in p):
        raise ValueError("probabilities must be finite and in [0, 1]")
    mass = [1.0]
    for success in p:
        updated = [0.0] * (len(mass) + 1)
        for k, value in enumerate(mass):
            updated[k] += (1 - success) * value
            updated[k + 1] += success * value
        mass = updated
    return mass

result = poisson_binomial([0.2, 0.5, 0.8])
assert all(abs(a - b) < 1e-12 for a, b in zip(result, [0.08, 0.42, 0.42, 0.08]))
assert poisson_binomial([]) == [1.0]
assert poisson_binomial([0, 1, 0.5]) == [0.0, 0.5, 0.5, 0.0]
print(result)

代码返回按成功数0到n排列的概率列表，不改写输入；概率必须是有限的实数并位于[0,1]。每轮构造一个新列表，避免覆盖仍要使用的旧概率。第 i 轮处理 i 个旧系数，总时间 $O(n^2)$，输入与工作列表的存储均为 $O(n)$。浮点结果有舍入误差；极小尾概率需要更高精度或专门的稳定算法。

相同均值并不保证相同方差

独立性给出 $$𝔼S=\sum _i{p}_i,\mathrm{Var}(S)=\sum _i{p}_i(1-p_i).$$ 令 $\overline{p}=n^{-1}\sum _i{p}_i$（$n>0$），展开平方可得 $$\mathrm{Var}(S)=n\overline{p}(1-\overline{p})-\sum _i(p_i-\overline{p}{)}^2.$$ 所以在固定平均成功率时，不同成功率会降低这一独立模型的总方差。主例为 $0.16+0.25+0.16=0.57$，而 $\mathrm{Binomial}(3,0.5)$ 的方差是0.75。二者恰巧都具有至少二次成功概率0.5，也不能据此认定完整分布相同。

异概率模型均值1.5、方差0.57；固定0.5的二项模型均值1.5、方差0.75。

作为边界变式，取 $(p_1,p_2,p_3)=(0,1,1/2)$，前两次总共恰有一次成功，所以 S 仅取一或二，各以概率二分之一；代码返回 $(0,1/2,1/2,0)$。若三次结果由同一个随机开关控制，虽各自的边际成功率仍可为1/2，它们就不独立，总数可能只取零和三。这样的依赖结构已在生成多项式分解的第一步破坏本模型，不能用调整单个 p_i 修复。