UA MATH564 概率论 计算至少有一个发生的概率：Boole不等式

Boole不等式Gunias不等式钟开莱-艾尔迪希（Chung-Erdos）不等式

概率作为一种特殊的测度，满足有限可加性： $$P(\bigcup _{i=1}^n{A}_i)=\sum _{i=1}^{n}P(A_i),A_i\cap A_j=\varphi ,\forall i\ne j$$

$A_i,A_j$作为样本空间$\sigma$-代数中的元素，$A_i\cap A_j=\varphi$的概率解释是$A_i,A_j$这两个事件互斥。上式左边的含义是互斥事件$A_1,A_2,\cdots ,A_n$中至少有一个发生的概率，右边的含义是互斥事件$A_1,A_2,\cdots ,A_n$的概率之和。但在具体应用中，事件互斥的假设实在是太强了，我们希望在没有互斥这个条件下，也能有一个计算$P({\bigcup }_{i=1}^n{A}_i)$的方法。

Boole不等式

尝试估计某个量的值之前，我们往往会尝试找到一些上界和下界，然后试图找到更小的上界和更大的下界，逐步逼近准确值。要寻找$P({\bigcup }_{i=1}^n{A}_i)$的上界和下界，最容易想到的是外测度的有限次可加性： $$P(\bigcup _{i=1}^n{A}_i)\le \sum _{i=1}^{n}P(A_i)$$

当且仅当$A_1,A_2,\cdots ,A_n$互斥时取等。这个不等式叫做Boole不等式。要证明这个不等式也非常容易，我们构造一个集列$\{B_i{\}}_{i=1}^n$，其中$B_1=A_1,B_2=A_2-A_1,\cdots ,B_n=A_n-{\bigcup }_{i=1}^{n-1}{A}_n$，显然$B_i\cap B_j=\varphi ,\forall i\ne j$，并且 $$\bigcup _{i=1}^n{B}_i=\bigcup _{i=1}^n{A}_i$$

根据概率的可加性和单调性（$B_i\subset A_i\Rightarrow P(B_i)\le P(A_i)$） $$P(\bigcup _{i=1}^n{A}_i)=P(\bigcup _{i=1}^n{B}_i)=\sum _{i=1}^{n}P(B_i)\le \sum _{i=1}^{n}P(A_i)$$

基于de Morgan律很容易就能得到Boole不等式的另一种形式。 $$\begin{gathered} P(\bigcap _{i=1}^n{A}_i)=1-P(\overline{\bigcap _{i=1}^n{A}_i})=1-P(\bigcup _{i=1}^n{\bar{A}}_i)\ge 1-\sum _{i=1}^{n}P({\bar{A}}_i) \\ =1-\sum _{i=1}^n[1-P(A_i)]=\sum _{i=1}^{n}P(A_i)-(n-1) \end{gathered}$$

Boole不等式给出了非常粗糙的上界和下界，后续的任务就是试图推导出更精确的上界和下界。Gunias不等式和钟开莱-艾尔迪希（Chung-Erdos）不等式分别提供了至少有一个事件发生概率的更精确的上界和下界。

Gunias不等式

因为现在没有$A_1,A_2,\cdots ,A_n$互斥的假设，所以他们两两之间交集不一定为0，在这$n$个事件中，总有一个事件与其他事件“重合程度”最大，即$\exists k\in \{1,2,\cdots ,n\}$， $$\sum _{i=1,i\ne k}P(A_i\cap A_k)\ge \sum _{i=1,i\ne j}P(A_i\cap A_j),\forall j\in \{1,2,\cdots ,n\}$$

下面我们构造两个集列$\{B_i{\}}_{i=1}^n$与$\{C_i{\}}_{i=1}^n$： $$\begin{gathered} B_1=A_k,B_2=A_1-A_k,\cdots ,B_k=A_{k-1}-A_k,B_{k+1}=A_{k+1}-A_k,\cdots ,B_n=A_n-A_k \\ {C}_1=A_k,C_2=A_1-A_k,C_3=A_2-A_1-A_k,\cdots ,C_k=A_{k-1}-\bigcup _{j=1,j\ne k-1}^k{A}_j \\ {C}_{k+1}=A_{k+1}-\bigcup _{j=1}^k{A}_j,\cdots ,C_n=A_n-\bigcup _{j=1}^{n-1}{A}_j \end{gathered}$$

显然$C_i\subset B_i$，因此 $$\bigcup _{i=1}^n{C}_i\subset \bigcup _{i=1}^n{B}_i$$

集列$\{C_i{\}}_{i=1}^n$与Boole不等式证明中构造的集列类似， $$\bigcup _{i=1}^n{C}_i=\bigcup _{i=1}^n{A}_i$$

根据概率的单调性， $$P(\bigcup _{i=1}^n{A}_i)=P(\bigcup _{i=1}^n{C}_i)\le P(\bigcup _{i=1}^n{B}_i)$$

根据Boole不等式 $$\begin{gathered} P(\bigcup _{i=1}^n{B}_i)\le \sum _{i=1}^{n}P(B_i)=P(A_k)+P(A_1-A_k)+\cdots \\ +P(A_{k-1}-A_k)+P(A_{k+1}-A_k)+\cdots +P(A_n-A_k) \\ =P(A_k)+P(A_1)-P(A_1\cap A_k)+\cdots +P(A_{k-1})-P(A_{k-1}\cap A_k) \\ +P(A_{k+1})-P(A_{k+1}\cap A_k)+\cdots +P(A_n)-P(A_n\cap A_k) \\ =\sum _{i=1}^{n}P(A_i)-\sum _{j=1,j\ne k}^{n}P(A_j\cap A_k) \end{gathered}$$

这个就是Gunias不等式，也可以将其写成： $$P(\bigcup _{i=1}^n{A}_i)\le \sum _{i=1}^{n}P(A_i)-\underset{k\in \{1,\cdots ,n\}}{\sup }\sum _{j=1,j\ne k}^{n}P(A_j\cap A_k)$$

钟开莱-艾尔迪希（Chung-Erdos）不等式

Boole不等式给出的至少有一个事件发生的概率的下界非常粗糙，甚至都不能保证下界是非负的，但钟开莱-艾尔迪希不等式给出的下界一定是非负的： $$P(\bigcup _{i=1}^n{A}_i)\ge \frac{{\left({\sum }_{i=1}^{n}P(A_i)\right)}^2}{{\sum }_{i,j=1}^{n}P(A_i\cap A_j)}$$

证明 当$n=2$时，钟开莱-艾尔迪希不等式为 $$\begin{gathered} P(A_1\cup A_2)\ge \frac{P(A_1{)}^2+P(A_2{)}^2+2P(A_1)P(A_2)}{P(A_1)+P(A_2)+2P(A_1\cap A_2)} \\ \Leftarrow [P(A_1)+P(A_2)+2P(A_1\cap A_2)]P(A_1\cup A_2)\ge P(A_1{)}^2+P(A_2{)}^2+2P(A_1)P(A_2) \\ \Leftarrow P(A_1)[P(A_1\cup A_2)-P(A_1)]+P(A_2)[P(A_1\cup A_2)-P(A_2)] \\ +2[P(A_1\cap A_2)P(A_1\cup A_2)-P(A_1)P(A_2)]\ge 0 \\ \Leftarrow 2P(A_1)P(A_2)-[P(A_1)+P(A_2)]P(A_1\cap A_2) \\ +2[P(A_1\cap A_2)P(A_1\cup A_2)-P(A_1)P(A_2)]\ge 0 \\ \Leftarrow [2P(A_1\cup A_2)-(P(A_1)+P(A_2))]P(A_1\cap A_2)\ge 0 \end{gathered}$$

显然$2P(A_1\cup A_2)-(P(A_1)+P(A_2))\ge 0$，因此当$n=2$时，钟开莱-艾尔迪希不等式成立。

假设$n=k$时，钟开莱-艾尔迪希不等式成立，则$n=k+1$时， $$P(\bigcup _{i=1}^{k+1}{A}_i)=P(A_{k+1}\cup \bigcup _{i=1}^k{A}_i)\ge \frac{P(A_{k+1}{)}^2+P({\bigcup }_{i=1}^k{A}_i{)}^2+2P(A_1)P({\bigcup }_{i=1}^k{A}_i)}{P(A_{k+1})+P({\bigcup }_{i=1}^k{A}_i)+2P(A_{k+1}\cap {\bigcup }_{i=1}^k{A}_i)}$$

根据Boole不等式， $$\begin{gathered} P(A_{k+1})+P(\bigcup _{i=1}^k{A}_i)+2P(A_{k+1}\cap \bigcup _{i=1}^k{A}_i) \\ \le P(A_{k+1})+\sum _{i=1}^{k}P(A_i)+2\sum _{i=1}^{k}P(A_{k+1}\cap A_i)\le \sum _{i,j=1}^{k+1}P(A_i\cap A_j) \end{gathered}$$

对$P({\bigcup }_{i=1}^k{A}_i)$使用钟开莱-艾尔迪希不等式，说明分子大于${\left({\sum }_{i=1}^{k+1}P(A_i)\right)}^2$，这一步留给读者自己计算。综上，钟开莱-艾尔迪希不等式对所有的自然数都成立。