【证明】【一题多解】布尔不等式(union bound)的证明

布尔不等式(Boole’s inequality)也叫(union bound),即并集的上界,描述的是至少一个事件发生的概率(P(⋃iAi)" role="presentation">P(⋃iAi)P(⋃iAi))不大于单独事件(事件之间未必独立)发生的概率之和(∑iP(Ai)" role="presentation">∑iP(Ai)∑iP(Ai))。

即:

P(⋃iAi)≤∑iP(Ai)" role="presentation">P(⋃iAi)≤∑iP(Ai)P(⋃iAi)≤∑iP(Ai)

展开即为:

P(A1⋃A2⋃⋯)≤P(A1)+P(A2)+⋯" role="presentation">P(A1⋃A2⋃⋯)≤P(A1)+P(A2)+⋯P(A1⋃A2⋃⋯)≤P(A1)+P(A2)+⋯

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):

P(A1∪A2∪⋯)=P(B1∪B2∪⋯)=P(B1)+P(B2)+⋯≤P(A1)+P(A2)+⋯" role="presentation">P(A1∪A2∪⋯)=P(B1∪B2∪⋯)=P(B1)+P(B2)+⋯≤P(A1)+P(A2)+⋯P(A1∪A2∪⋯)=P(B1∪B2∪⋯)=P(B1)+P(B2)+⋯≤P(A1)+P(A2)+⋯
上一篇:mysql安装后服务启动不了


下一篇:MySQL外键之级联