布尔不等式(Boole’s inequality)也叫(union bound),即并集的上界,描述的是至少一个事件发生的概率(P(⋃iAi)" role="presentation">P(⋃iAi)P(⋃iAi))不大于单独事件(事件之间未必独立)发生的概率之和(∑iP(Ai)" role="presentation">∑iP(Ai)∑iP(Ai))。
即:
展开即为:
1. 数学归纳法证明
- 当 n=1" role="presentation">n=1n=1 时,显然 P(A1)≤P(A1)" role="presentation">P(A1)≤P(A1)P(A1)≤P(A1)
-
对于 n" role="presentation">nn,如果有:P(⋃i=1nAi)≤∑i=1nP(Ai)" role="presentation">P(⋃ni=1Ai)≤∑ni=1P(Ai)P(⋃i=1nAi)≤∑i=1nP(Ai),则由 P(A∪B)=P(A)+P(B)−P(A∩B)" role="presentation">P(A∪B)=P(A)+P(B)−P(A∩B)P(A∪B)=P(A)+P(B)−P(A∩B) 可知:
P(⋃i=1n+1Ai)=P({⋃i=1nAi}⋃An+1)=P(⋃i=1nAi)+P(An+1)−P({⋃i=1nAi}⋂An+1)≤P(⋃i=1nAi)+P(An+1)" role="presentation">P(⋃i=1n+1Ai)=P({⋃i=1nAi}⋃An+1)=P(⋃i=1nAi)+P(An+1)−P({⋃i=1nAi}⋂An+1)≤P(⋃i=1nAi)+P(An+1)P(⋃i=1n+1Ai)=P({⋃i=1nAi}⋃An+1)=P(⋃i=1nAi)+P(An+1)−P({⋃i=1nAi}⋂An+1)≤P(⋃i=1nAi)+P(An+1)
2. 将事件转换为独立事件(不相交事件)
假设有A1,A2,A3" role="presentation">A1,A2,A3A1,A2,A3 三个事件,则:
- 令 B1=A1,B2=A2−A1" role="presentation">B1=A1,B2=A2−A1B1=A1,B2=A2−A1,B1" role="presentation">B1B1 与 B2" role="presentation">B2B2 不相交
- 令 B2=A2−A1" role="presentation">B2=A2−A1B2=A2−A1 B3=A3−A2−A1" role="presentation">B3=A3−A2−A1B3=A3−A2−A1,B2" role="presentation">B2B2 与 B3" role="presentation">B3B3 不相交
令 Bi=Ai∖(⋃k=1i−1Ai)" role="presentation">Bi=Ai∖(⋃i−1k=1Ai)Bi=Ai∖(⋃k=1i−1Ai),则有 B1,B2,⋯," role="presentation">B1,B2,⋯,B1,B2,⋯, 互不相交,且 A1∪A2∪⋯=B1∪B2∪⋯" role="presentation">A1∪A2∪⋯=B1∪B2∪⋯A1∪A2∪⋯=B1∪B2∪⋯,自然 Bi⊂Ai" role="presentation">Bi⊂AiBi⊂Ai ==> P(Bi)≤P(Ai)" role="presentation">P(Bi)≤P(Ai)P(Bi)≤P(Ai):