布尔不等式

布尔不等式（），由乔治·布尔提出，指对于全部事件的概率不大于单个事件的概率总和。

对于事件A1、A2、A3、......：
:P(\bigcup_{i} A_i) \le \sum_i P(A_i)

在测度论上，布尔不等式满足σ次可加性。

证明
布尔不等式可以用数学归纳法证明。

对于1个事件：
:P(A_1) \le P(A_1)

对于n个事件：
:P(\bigcup_{i=_1}^{n} A_i) \le \sum_{i=_1}^{n} P(A_i)
:P(A \cup B) = P(A) + P(B) - P(A \cap B)
:P(\bigcup_{i=_1}^{n+1} A_i) = P(\bigcup_{i=_1}^n A_i) + P(A_{n+1}) - P(\bigcup_{i=_1}^n A_i \cap A_{n+1})
:P(\bigcup_{i=_1}^n A_i \cap A_{n+1}) \ge 0,
:P(\bigcup_{i=_1}^{n+1} A_i) \le P(\bigcup_{i=_1}^n A_i) + P(A_{n+1})
:P(\bigcup_{i=_1}^{n+1} A_i) \le \sum_{i=_1}^{n} P(A_i) + P(A_{n+1}) = \sum_{i=_1}^{n+1} P(A_i).
使用马尔可夫不等式的证明
令A_1,A_2,\cdots,A_n是任意概率事件。X是各种事件A_i的发生次数的随机变量。显然有：
:E(X)=P(A_1)+P(A_2)+\cdots+P(A_n)=\sum_{i=1}^{n}P(A_i)
因为X是非负随机变量，应用馬爾可夫不等式，取a=1，有：
:P(X\geqslant 1)\leqslant E(X)=\sum_{i=1}^{n}P(A_i)
注意到P(X\geqslant 1)=P(\bigcup_{i=_1}^{n} A_i)

邦费罗尼不等式
布尔不等式可以推导出事件并集的上界和下界，其关系称为邦费罗尼不等式 。

定义：
:S_1 = \sum_{i=1}^n P(A_i),
:S_2 = \sum_{1\le i
:S_k = \sum_{1\le i_1

对于奇数k：
:P( \bigcup_{i=1}^n A_i ) \le \sum_{j=1}^k (-1)^{j-1} S_j

对于偶数k：
:P( \bigcup_{i=1}^n A_i) \ge \sum_{j=1}^k (-1)^{j-1} S_j

参见
*容斥原理

参考资料
*
*
*
*