UA MATH564 概率论 计算至少有一个发生的概率：Waring公式

基于组合学的证明方法基于概率论的证明方法

在推出Poincare公式后，计算$n$个事件中至少有一个事件发生的概率的问题就彻底解决了。但数学家们又开始纠结了，Poincare公式只能够计算至少有一个发生的概率，那有没有能计算恰好有$m$个事件同时发生的概率的方法呢？

假设用$B_m$表示$A_1,\cdots ,A_n$中正好有$m$个发生的事件，则 $$P(B_m)=\sum _{k=m}^n(-1{)}^{k-m}{C}_k^m{S}_k$$

这个公式叫做Waring公式。其中$S_k$就是上一讲定义的记号$$S_m=\sum _{1\le i_1<i_2<\cdots <i_m\le n}P(A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_m})$$

基于组合学的证明方法

Feller的Introduction to Probability and its application中给出了基于组合学的证明方法。用反证法。我们要证明的公式等价于：假设$E$是一个恰好包含在$l$个事件中的子事件，当且仅当$l=m$时，$P(E)$才是$P(B_m)$的一部分。显然这时$P(E)$也是$S_1,S_2,\cdots ,S_l$的一部分，并且$P(E)$只会出现在$S_l$的一项中。如果$l<m$，则$P(E)$不是$P(B_m)$的一部分。如果$l>m$，则$P(E)$会出现在$S_k,k\ge m$的$C_l^k$项中，因此对$S_k,k\ge m$的贡献是$C_l^k{C}_k^m$根据容斥原理，$P(E)$对$P(B_m)$的贡献为 $$\begin{gathered} C_l^m{C}_m^m-C_l^{m+1}{C}_{m+1}^m+C_l^{m+2}{C}_{m+2}^{m+1}-\cdots \\ =C_l^m(C_{l-m}^0-C_{l-m}^1+\cdots )=C_l^m(1-1{)}^{n-m}=0 \end{gathered}$$

这就说明了当且仅当$l=m$时，$P(E)$才是$P(B_m)$的一部分，因此上述公式成立。

基于概率论的证明方法

施利亚耶夫的概率论习题集提到了基于事件的Indicator function与期望的证明方法。我们记恰好发生的$m$个事件为$i_1,i_2,\cdots ,i_m$，记没有发生的事件为$j_1,j_2,\cdots ,j_{n-m}$，记随机变量$X=I_A$，则恰好有$m$个事件发生的随机变量是 $$\sum X_{i_1}{X}_{i_2}\cdots X_{i_m}(1-X_{j_1})\cdots (1-X_{j_{n-m}})$$

上式是对任意可能的$i_1,\cdots ,i_m$的选取的求和。事件的Indicator function的期望等于事件发生的概率，因此 $$P(B_m)=E\sum X_{i_1}{X}_{i_2}\cdots X_{i_m}(1-X_{j_1})\cdots (1-X_{j_{n-m}})$$

注意$(1-X_{j_1})\cdots (1-X_{j_{n-m}})$的展开式中一共有$2^{n-m}$项，其中一项为$1$，因此概率中有一项为 $$E\sum X_{i_1}{X}_{i_2}\cdots X_{i_m}=\sum P(A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_m})$$

其余展开式期望的计算与此类似，事件的Indicator function乘积的期望等于事件的交发生的概率。下面研究$(1-X_{j_1})\cdots (1-X_{j_{n-m}})$的展开式。

引理1 用示性函数表示的容斥原理为：$X_i=I_{A_i}$ $$\begin{gathered} I_{{\bigcup }_{i=1}^n{A}_i}=1-\prod _{i=1}^n(1-X_i)=\sum _{i=1}^n{X}_i-\sum _{1\le i_1<i_2\le n}{X}_{i_1}{X}_{i_2}+\cdots \\ +(-1{)}^{m+1}\sum _{1\le i_1<\cdots <i_m\le n}{X}_{i_1}\cdots X_{i_m}\cdots +(-1{)}^n{X}_1\cdots X_n \end{gathered}$$ 基于这个引理把$(1-X_{j_1})\cdots (1-X_{j_{n-m}})$展开，然后把期望改写成概率就可以得到Waring公式了。