この記事にはや(外部リンク )の一覧が含まれていますが、(脚注 )による参照が不十分であるため、情報源が依然不明確です 。適切な位置に脚注を追加して、記事の(信頼性向上 )にご協力ください。(2012年2月 )
確率論 において、ブールの不等式 (ブールのふとうしき、英 : Boole's inequality )またはユニオンバウンド (union bound)は、事象 の有限 あるいは可算集合 について、少くとも1つの事象が起こる確率は個別の事象の確率の和よりも大きくない、ことを示す。
ブールの不等式の名称はジョージ・ブール にちなむ[1] 。
形式的に、事象A 1 , A 2 , A 3 , ...の可算集合について、
P ( ⋃ i A i ) ≤ ∑ i P ( A i ) {\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)\leq \sum _{i}{\mathbb {P} }(A_{i})} が成り立つ。
測度論 の用語では、ブールの不等式は測度(および任意の確率測度 )がσ -劣加法的 である事実から得られる。
有限和の場合 有限個の事象に関するブールの不等式は、帰納法 を使って証明することができる。
n = 1 {\displaystyle n=1} の場合について当然
P ( A 1 ) ≤ P ( A 1 ) {\displaystyle \mathbb {P} (A_{1})\leq \mathbb {P} (A_{1})} ということになる。
n {\displaystyle n} の場合に
P ( ⋃ i = 1 n A i ) ≤ ∑ i = 1 n P ( A i ) {\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\right)\leq \sum _{i=1}^{n}{\mathbb {P} }(A_{i})} であると仮定する。
P ( A ∪ B ) = P ( A ) + P ( B ) − P ( A ∩ B ) {\displaystyle \mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B)} であり、和集合演算は結合則 を満たすため、
P ( ⋃ i = 1 n + 1 A i ) = P ( ⋃ i = 1 n A i ) + P ( A n + 1 ) − P ( ⋃ i = 1 n A i ∩ A n + 1 ) {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)+\mathbb {P} (A_{n+1})-\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\cap A_{n+1}\right)} を得る。
そして、(確率の第一公理 )によって、
P ( ⋃ i = 1 n A i ∩ A n + 1 ) ≥ 0 {\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\cap A_{n+1}\right)\geq 0} であるため、
P ( ⋃ i = 1 n + 1 A i ) ≤ P ( ⋃ i = 1 n A i ) + P ( A n + 1 ) {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)\leq \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)+\mathbb {P} (A_{n+1})} を得て、したがって
P ( ⋃ i = 1 n + 1 A i ) ≤ ∑ i = 1 n P ( A i ) + P ( A n + 1 ) = ∑ i = 1 n + 1 P ( A i ) {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)\leq \sum _{i=1}^{n}\mathbb {P} (A_{i})+\mathbb {P} (A_{n+1})=\sum _{i=1}^{n+1}\mathbb {P} (A_{i})} を得る。
一般の場合 確率空間 における A 1 , A 2 , A 3 , … {\displaystyle A_{1},A_{2},A_{3},\dots } 中のいかなる事象に対しても、
P ( ⋃ i A i ) ≤ ∑ i P ( A i ) {\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)\leq \sum _{i}\mathbb {P} (A_{i})} となる、ことを示す。
確率空間の公理の1つは、 B 1 , B 2 , B 3 , … {\displaystyle B_{1},B_{2},B_{3},\dots } が確率空間の「交わりを持たない」部分集合であるならば
P ( ⋃ i B i ) = ∑ i P ( B i ) {\displaystyle \mathbb {P} \left(\bigcup _{i}B_{i}\right)=\sum _{i}\mathbb {P} (B_{i})} となるというものである。これは「可算加法性」と呼ばれる。
一方、 B ⊂ A {\displaystyle B\subset A} ならば、 P ( B ) ≤ P ( A ) {\displaystyle \mathbb {P} (B)\leq \mathbb {P} (A)} であるから、確率分布の公理より、
P ( A ) = P ( B ) + P ( A − B ) {\displaystyle \mathbb {P} (A)=\mathbb {P} (B)+\mathbb {P} (A-B)} である。(ここで留意すべきは、右辺のどちらの項も非負である、という点である。)
さて、集合 A i {\displaystyle A_{i}} を、交わりを持たないよう変形する。
B i = A i − ⋃ j = 1 i − 1 A j . {\displaystyle B_{i}=A_{i}-\bigcup _{j=1}^{i-1}A_{j}.} とすると、 { B i } {\displaystyle \{B_{i}\}} は互いに素 であり、また B i ⊂ A i {\displaystyle B_{i}\subset A_{i}} であり、かつ
⋃ i = 1 ∞ B i = ⋃ i = 1 ∞ A i {\displaystyle \bigcup _{i=1}^{\infty }B_{i}=\bigcup _{i=1}^{\infty }A_{i}} となる。
したがって、以下の式を演繹することができる。
P ( ⋃ i A i ) = P ( ⋃ i B i ) = ∑ i P ( B i ) ≤ ∑ i P ( A i ) . {\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)=\mathbb {P} \left(\bigcup _{i}B_{i}\right)=\sum _{i}\mathbb {P} (B_{i})\leq \sum _{i}\mathbb {P} (A_{i}).} ブールの不等式は事象の有限和の確率の(上界 )と(下界 )を見つけるために一般化することができる[2] 。これらの境界はカルロ・エミリオ・ボンフェローニ にちなみボンフェローニの不等式 と呼ばれる(Bonferroni (1936) )。
以下を定義する。
S 1 := ∑ i = 1 n P ( A i ) {\displaystyle S_{1}:=\sum _{i=1}^{n}{\mathbb {P} }(A_{i})} S 2 := ∑ 1 ≤ i < j ≤ n P ( A i ∩ A j ) {\displaystyle S_{2}:=\sum _{1\leq i<j\leq n}{\mathbb {P} }(A_{i}\cap A_{j})} {3, ..., n } 中の全ての整数k について
S k := ∑ 1 ≤ i 1 < ⋯ < i k ≤ n P ( A i 1 ∩ ⋯ ∩ A i k ) {\displaystyle S_{k}:=\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}{\mathbb {P} }(A_{i_{1}}\cap \cdots \cap A_{i_{k}})} すると、 {1, ..., n } 中の奇数k について
P ( ⋃ i = 1 n A i ) ≤ ∑ j = 1 k ( − 1 ) j − 1 S j {\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\right)\leq \sum _{j=1}^{k}(-1)^{j-1}S_{j}} {2, ..., n } 中の偶数k について
P ( ⋃ i = 1 n A i ) ≥ ∑ j = 1 k ( − 1 ) j − 1 S j {\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\right)\geq \sum _{j=1}^{k}(-1)^{j-1}S_{j}} となる。
ブールの不等式はk = 1の場合である。k = n の時は等号が成立し、得られる恒等式は包除原理 である。