论文记录-Closed-Form Expression for the Poisson-Binomial Probability Density Function

2021-02-12

论文

字数统计: 1.3k | 阅读时长≈ 4 分钟

Closed-Form Expression for the Poisson-Binomial Probability Density Function

Introduction

二项分布概率密度函数描述了当单个成功概率在试验中保持不变时 N 次独立试验中的成功数。而当这个成功概率会改变时，概率密度函数就转变为泊松-二项分布。

例子：

可靠性理论/容错：当N个子进程中有至少M个失败时，我们认为该进程失败。第n个子进程的失败概率为$p_n$，计算整个进程的失败概率。
目标追踪：当传感器在N次连续独立查找中至少检测到M次时，目标追踪会被启动。给定可能会改变的每次查找检测概率$p_n$，确定追踪启动的概率。
模式识别/决策理论：如果第n个专家在诊断某特殊情况是否发生时，有$p_n$的概率得到正确的判断，那么为了实现超过某一百分数的正确率，需要多少位独立专家的重合判定。
教育考试设计：标准化考试中有N个等权重问题，给定至少正确解答其中n个问题的学生百分数，据此推算每个问题正确回答学生的百分数，从而确定问题是否表现出所需的难度扩散。（这是一个逆向泊松二项分布的问题）
多传感器融合：给定一个由N个传感器组成的网络，其检测/无检测输出将通过投票结果进行组合，为了实现指定的M-out-N”融合”误报概率，每个传感器的误报率应该是多少。
项目管理/资源分配：有K个工作站，每个工作站分配到$r_k$个资源，每个工作站达到其各自生产配额的概率为$p_k=f(r_k)$。给定L个附加工作站的可用性，并假设函数$f()$可逆，应向新工作站分配多少资源，以便K+L个工作站中至少 M 个工作站能达到其生产配额的概率为P。

本文组织结构：

单独每次事件成功率与泊松-二项分布概率密度函数之间的关系
数值技术（多项式插值和离散傅里叶变换）
通过获取二项系数、二项式 cdf 和泊松-二项性时刻（Poisson-binomial moments，这个翻译不知道是否正确）的新表示来演示这些表达式的使用
解决前面的第6个例子作为应用展示
使用多项式技术和矩阵理论技术解决逆向泊松-二项分布的问题
总结

GROUNDWORK

在N次独立实验中，第k次的成功率为$p_k$，失败率为$1-p_k$。成功的次数Y可以被写作$Y=X_1+X_2+…+X_N$，这N个相互独立的随机变量$X_k$，分布向量为$[Pr\{X_k=0\}\ \ Pr\{X_k=1\}]=[1-p_k\ \ p_k]$，其中$Pr\{u\}$表示$u$的概率。而这些随机变量的和式Y的分布就是泊松二项概率密度函数，其表达式通过线性卷积可以得到：

$[Pr\{Y=0\}\ \ Pr\{Y=1\}...Pr\{Y=N\}]\\ = [1-p_1\ \ p_1]*[1-p_2\ \ p_2]*...*[1-p_N\ \ p_N] \tag{1}$

对公式1两边使用Z变换，可得泊松二项概率密度函数的两种生成函数：

$P_0+P_1z+P_2z^2+...+P_Nz^N\\ =(1-p_1+p_1z)(1-p_2+p2_z)...(1-p_N+p_Nz) \tag{2}$

其中$P_n$表示$Pr\{Y=n\}$

公式(2)的右边稍微改动一下可得：

$P_0+P_1z+P_2z^2+...+P_Nz^N\\ =\alpha(z-s_1)(z-s_2)...(z-s_N) \tag{3a}$

其中

$\alpha = \prod_{k=1}^N P_k \tag{3b}$ $s_k = -(1-p_k)/p_k \tag{3c}$

上述过程用matlab可以写成：

function [P,Q]=ProbMofN(p)
% 给定N个元素的向量p，它表示N个独立重复实验的成功概率，该函数的返回值包括：
% P：N+1个元素，表示0次成功、1次成功、2次成功...N次成功（泊松-二项式的pdf）
% Q：N+1个元素，表示至少0次成功、至少1次成功、...、至少N次成功的概率（泊松-二项式的cdf）
p(p==0)=[];    % 消除等于0的元素
n=length(p);
alpha=prob(p);
s=-(1-p)./p;
S=poly(s); % S就是根为向量s的多项式的N+1个系数的向量，也就是说，S(1)*x^N+...+S(N)*x+S(N+1)

temp_P=alpha*S;
temp_Q=cumsum(temp_P);

P=temp_P[N+1:-1:1];
Q=temp_Q[N+1:-1:1];
%================================
function p=invProbMofN(P)
% 给定N个元素的向量P，它表示N次实验后，0次成功、1次成功、...、N次成功的概率，该函数的返回值为：
% p：N个元素的向量，表示每次实验的成功率
N1=length(P); % N1=N+1
S=P[N1:-1:1]; 
s=roots(S); % s是N个元素的向量，表示生成函数的根
p=1./(1-s); % p是N个元素的向量，表示每次事件的成功率

这样的计算过程虽然很好用，但是在对泊松-二项式pdf进行进一步分析或推导新结论时不太方便。于是本文提出了近似表达式。