ブールの不等式

確率論において、ブールの不等式（ブールのふとうしき、英: Boole's inequality）またはユニオンバウンド（union bound）は、事象の有限あるいは可算集合について、少くとも1つの事象が起こる確率は個別の事象の確率の和よりも大きくない、ことを示す。 ブールの不等式の名称はジョージ・ブールにちなむ。 形式的に、事象A1, A2, A3, ...の可算集合について、 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}).} ブールの不等式は事象の有限和の確率の上界と下界を見つけるために一般化することができる。これらの境界はカルロ・エミリオ・ボンフェローニにちなみボンフェローニの不等式と呼ばれる（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 の時は等号が成立し、得られる恒等式は包除原理である。