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

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

概率作为一种特殊的测度，满足有限可加性：
$P(⋃i=1nAi)=∑i=1nP(Ai),Ai∩Aj=ϕ,∀i≠jP(\bigcup_{i=1}^{n} A_i) = \sum_{i=1}^{n} P(A_i),A_i \cap A_j = \phi,\forall i \ne j$

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

Boole不等式

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

当且仅当 $A1,A2,⋯,AnA_1,A_2,\cdots,A_n$ 互斥时取等。这个不等式叫做Boole不等式。要证明这个不等式也非常容易，我们构造一个集列 ${B_i\}_{i=1}^n$ ，其中 $B1=A1,B2=A2−A1,⋯,Bn=An−⋃i=1n−1AnB_1 = A_1,B_2 = A_2-A_1,\cdots,B_n = A_n – \bigcup_{i=1}^{n-1}A_n$ ，显然 $Bi∩Bj=ϕ,∀i≠jB_i \cap B_j = \phi, \forall i \ne j$ ，并且
$⋃i=1nBi=⋃i=1nAi\bigcup_{i=1}^n B_i = \bigcup_{i=1}^{n} A_i$

根据概率的可加性和单调性（ $Bi⊂Ai⇒P(Bi)≤P(Ai)B_i \subset A_i \Rightarrow P(B_i) \le P(A_i)$ ）
$P(⋃i=1nAi)=P(⋃i=1nBi)=∑i=1nP(Bi)≤∑i=1nP(Ai)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不等式的另一种形式。
$P(⋂i=1nAi)=1−P(⋂i=1nAiˉ)=1−P(⋃i=1nAˉi)≥1−∑i=1nP(Aˉi)=1−∑i=1n[1−P(Ai)]=∑i=1nP(Ai)−(n−1)P(\bigcap_{i=1}^n A_i) = 1-P(\bar{\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)$

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

Gunias不等式

因为现在没有 $A1,A2,⋯,AnA_1,A_2,\cdots,A_n$ 互斥的假设，所以他们两两之间交集不一定为0，在这 $n$ 个事件中，总有一个事件与其他事件“重合程度”最大，即 $∃k∈{1,2,⋯,n}\exists k \in \{1,2,\cdots,n\}$ ，
$∑i=1,i≠kP(Ai∩Ak)≥∑i=1,i≠jP(Ai∩Aj),∀j∈{1,2,⋯,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$ ：
$B1=Ak,B2=A1−Ak,⋯,Bk=Ak−1−Ak,Bk+1=Ak+1−Ak,⋯,Bn=An−AkC1=Ak,C2=A1−Ak,C3=A2−A1−Ak,⋯,Ck=Ak−1−⋃j=1,j≠k−1kAjCk+1=Ak+1−⋃j=1kAj,⋯,Cn=An−⋃j=1n−1AjB_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}^kA_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$

显然 $Ci⊂BiC_i \subset B_i$ ，因此
$⋃i=1nCi⊂⋃i=1nBi\bigcup_{i=1}^n C_i \subset \bigcup_{i=1}^n B_i$

集列 ${C_i\}_{i=1}^n$ 与Boole不等式证明中构造的集列类似，
$⋃i=1nCi=⋃i=1nAi\bigcup_{i=1}^n C_i = \bigcup_{i=1}^n A_i$

根据概率的单调性，
$P(⋃i=1nAi)=P(⋃i=1nCi)≤P(⋃i=1nBi)P(\bigcup_{i=1}^n A_i) = P(\bigcup_{i=1}^n C_i) \le P(\bigcup_{i=1}^n B_i)$

根据Boole不等式
$P(⋃i=1nBi)≤∑i=1nP(Bi)=P(Ak)+P(A1−Ak)+⋯+P(Ak−1−Ak)+P(Ak+1−Ak)+⋯+P(An−Ak)=P(Ak)+P(A1)−P(A1∩Ak)+⋯+P(Ak−1)−P(Ak−1∩Ak)+P(Ak+1)−P(Ak+1∩Ak)+⋯+P(An)−P(An∩Ak)=∑i=1nP(Ai)−∑j=1,j≠knP(Aj∩Ak)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)$

这个就是Gunias不等式，也可以将其写成：
$P(⋃i=1nAi)≤∑i=1nP(Ai)−sup⁡k∈{1,⋯,n}∑j=1,j≠knP(Aj∩Ak)P(\bigcup_{i=1}^n A_i) \le \sum_{i=1}^n P(A_i) – \sup_{k \in \{1,\cdots,n\}} \sum_{j=1,j \ne k}^{n}P(A_j \cap A_k)$

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

Boole不等式给出的至少有一个事件发生的概率的下界非常粗糙，甚至都不能保证下界是非负的，但钟开莱-艾尔迪希不等式给出的下界一定是非负的：
$P(⋃i=1nAi)≥(∑i=1nP(Ai))2∑i,j=1nP(Ai∩Aj)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$ 时，钟开莱-艾尔迪希不等式为
$P(A1∪A2)≥P(A1)2+P(A2)2+2P(A1)P(A2)P(A1)+P(A2)+2P(A1∩A2)⇐[P(A1)+P(A2)+2P(A1∩A2)]P(A1∪A2)≥P(A1)2+P(A2)2+2P(A1)P(A2)⇐P(A1)[P(A1∪A2)−P(A1)]+P(A2)[P(A1∪A2)−P(A2)]+2[P(A1∩A2)P(A1∪A2)−P(A1)P(A2)]≥0⇐2P(A1)P(A2)−[P(A1)+P(A2)]P(A1∩A2)+2[P(A1∩A2)P(A1∪A2)−P(A1)P(A2)]≥0⇐[2P(A1∪A2)−(P(A1)+P(A2))]P(A1∩A2)≥0P(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$

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

假设 $n = k$ 时，钟开莱-艾尔迪希不等式成立，则 $n = k + 1$ 时，
$P(⋃i=1k+1Ai)=P(Ak+1∪⋃i=1kAi)≥P(Ak+1)2+P(⋃i=1kAi)2+2P(A1)P(⋃i=1kAi)P(Ak+1)+P(⋃i=1kAi)+2P(Ak+1∩⋃i=1kAi)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不等式，
$P(Ak+1)+P(⋃i=1kAi)+2P(Ak+1∩⋃i=1kAi)≤P(Ak+1)+∑i=1kP(Ai)+2∑i=1kP(Ak+1∩Ai)≤∑i,j=1k+1P(Ai∩Aj)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)$

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