包除原理とBonferroni inequalities

包除原理 (inclusion-exclusion principle) は、集合の要素数・確率・面積などにおいて成立するべきとされる原理であり、現代の整備された集合論・確率論・測度論において証明することができる。Bonferroni inequalities は包除原理によく似た不等式であり、これも証明することができる。この記事では主に確率論に重きを置いて、この2つを証明する。

はじめに

この記事では確率論における包除原理と Bonferroni inequalities (ボンフェローニの不等式) を証明する。適宜用語を置き換えることで測度論における不等式の証明にもなる (ただし測度が∞になる可測集合を用いない場合に限る)。

以下の証明では、与えられた正の整数 $n$ に対して、1 以上 $n$ 以下の自然数からなる集合を $[n]$ と表現しているので\[[n]=\{1,\dots,n\}\]である。

ここで考える確率空間は $\Pr$ を確率関数としてもつとする。

また、以下の命題はいずれも確率論 (測度論) や集合論に関する初等的な命題であるので、すでに証明が済んでいるものとして話を進める。

命題$A_1,\dots,A_n$ を事象列とすると\[\Pr\left(\bigcup^n_{i=1} A_i\right) \leq \sum^n_{i=1}\Pr\left(A_i\right).\]

命題$A_1,\dots,A_n$, $B$ を集合列とすると\[\left(\bigcup^n_{i=1} A_i\right)\cap B = \bigcup^n_{i=1} (A_i\cap B).\]

包除原理と証明

まず包除原理全体の証明に先だって、事象の個数が 2 である場合に限定した包除原理を先に証明しておく。

命題$A$, $B$ を事象とすると\[\Pr(A\cup B) = \Pr(A)+\Pr(B)-\Pr(A\cap B)\]

(証明) $A\setminus B$ と $B$ は互いに素だから、確率関数の完全加法性より\begin{eqnarray}\Pr(A\setminus B)+\Pr(B) &=& \Pr((A\setminus B) \cup B)\\ &=& \Pr(A\cup B)\end{eqnarray}であり、$A\setminus B$ と $A\cap B$ は互いに素だから、確率関数の完全加法性より\begin{eqnarray}\Pr(A\setminus B)+\Pr(A\cap B) &=& \Pr((A\setminus B) \cup (A\cap B))\\ &=& \Pr(A)\end{eqnarray}である。この2つの等式より\[\Pr(A\cup B) = \Pr(A)+\Pr(B)-\Pr(A\cap B)\]が得られる。

これを用いて、以下の包除原理を証明することができる。

定理$n$ を正の整数とする。$n$ 個の事象 $A_1,\dots,A_n$ に対して \[\Pr\left(\bigcup^n_{i=1} A_i\right) = \sum^n_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]}\Pr\left(\bigcap_{i\in I} A_i\right)\right) \]である。

(証明) $n$ についての数学的帰納法を用いる。

まず、$n=1$ のとき明らかに成立する。次に、$n$ 個に満たない事象列について定理が成立すると仮定して、事象の個数が $n$ 個でも成立することを示す。このとき、2つの事象に対する包除原理と交叉の加算合併への分配則より\begin{eqnarray}\Pr\left(\bigcup^n_{i=1} A_i\right) &=& \Pr\left(\bigcup^{n-1}_{i=1} A_i\right) + \Pr(A_n) - \Pr\left(\left(\bigcup^{n-1}_{i=1} A_i\right)\cap A_n\right)\\ &=& \Pr\left(\bigcup^{n-1}_{i=1} A_i\right) + \Pr(A_n) - \Pr\left(\bigcup^{n-1}_{i=1} (A_i\cap A_n)\right)\end{eqnarray}であるので、数学的帰納法の仮定より\begin{eqnarray}\Pr\left(\bigcup^n_{i=1} A_i\right) &=& \sum^{n-1}_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n-1]}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &&+\Pr(A_n)\\&& -\sum^{n-1}_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n-1]}\Pr\left(\bigcap_{i\in I} (A_i\cap A_n)\right)\right) \\ &=& \sum^n_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]\\ n\not\in I}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &&+\sum^1_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]\\ n\in I}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &&+\sum^n_{j=2}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]\\ n\in I}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &=& \sum^n_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\end{eqnarray}

右辺が少しわかりづらいので具体的な例を出すと、$n$ の値によって次のような等式になる。\begin{eqnarray}\Pr(A_1\cup A_2) &=& \Pr(A_1)+\Pr(A_2)-\Pr(A_1\cap A_2)\\\Pr(A_1\cup A_2\cup A_3) &=& \left(\Pr(A_1)+\Pr(A_2)+\Pr(A_3)\right)\\&&-(\Pr(A_1\cap A_2) + \Pr(A_2\cap A_3)+\Pr(A_3\cap A_1))\\&& +\Pr(A_1\cap A_2\cap A_3)\end{eqnarray}

Bonferroni inequalities と証明

Bonferroni inequalities の証明は包除原理の証明とまったく同じ手順でできる。

定理$n$ を正の整数とする。$n$ 個の事象 $A_1,\dots,A_n$ に対して $k$ が $n$ 以下の奇数なら\[\Pr\left(\bigcup^n_{i=1} A_i\right) \leq \sum^k_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]}\Pr\left(\bigcap_{i\in I} A_i\right)\right) \]であり、$k$ が $n$ 以下の偶数なら\[\Pr\left(\bigcup^n_{i=1} A_i\right) \geq \sum^k_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\]である。

(証明) $k=1$ のときと $k=n$ のときはそれぞれ確率関数の劣加法性と包除原理より明らかだから、$k= 2,\dots,n-1$ とする。$n$ についての数学的帰納法を用いる。

まず、$n=1$ のとき明らかに成立する。次に、$n$ 個に満たない事象列について定理が成立すると仮定して、事象の個数が $n$ 個でも成立することを示す。このとき、$k$ が奇数であれば、2つの事象に対する包除原理と交叉の加算合併への分配則より\begin{eqnarray}\Pr\left(\bigcup^n_{i=1} A_i\right) &=& \Pr\left(\bigcup^{n-1}_{i=1} A_i\right) + \Pr(A_n) - \Pr\left(\left(\bigcup^{n-1}_{i=1} A_i\right)\cap A_n\right)\\ &=& \Pr\left(\bigcup^{n-1}_{i=1} A_i\right) + \Pr(A_n) - \Pr\left(\bigcup^{n-1}_{i=1} (A_i\cap A_n)\right)\end{eqnarray}であるので、数学的帰納法の仮定より\begin{eqnarray}\Pr\left(\bigcup^n_{i=1} A_i\right) &\leq& \sum^k_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n-1]}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &&+\Pr(A_n)\\&& -\sum^{k-1}_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n-1]}\Pr\left(\bigcap_{i\in I} (A_i\cap A_n)\right)\right) \\ &=& \sum^k_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]\\ n\not\in I}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &&+\sum^1_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]\\ n\in I}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &&+\sum^k_{j=2}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]\\ n\in I}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\\ &=& \sum^k_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\end{eqnarray}$k$ が偶数であれば同様に\[\Pr\left(\bigcup^n_{i=1} A_i\right) \geq \sum^k_{j=1}(-1)^{j-1}\left(\sum_{|I|=j \\ I\subset[n]}\Pr\left(\bigcap_{i\in I} A_i\right)\right)\]

右辺が少しわかりづらいので具体的な例を出すと、$n$ や $k$ の値によって次のような不等式となる。\begin{eqnarray}\Pr(A_1\cup A_2) &\leq& \Pr(A_1)+\Pr(A_2)\\\Pr(A_1\cup A_2\cup A_3) &\leq& \Pr(A_1)+\Pr(A_2)+\Pr(A_3)\\ \Pr(A_1\cup A_2\cup A_3) &\geq& \left(\Pr(A_1)+\Pr(A_2)+\Pr(A_3)\right)\\&&-(\Pr(A_1\cap A_2) + \Pr(A_2\cap A_3)+\Pr(A_3\cap A_1))\end{eqnarray}

2つの定理の使い分け

包除原理は $\Pr(\bigcup_i A_i)$ が得られるが足さなくてはならない項が多い。Bonferroni inequalities は $\Pr(\bigcup_i A_i)$ の上限と下限しか得られないが足す項の数は少なくすることができる。これらの点で、$\Pr(\bigcup_i A_i)$ について議論するときにこの2つを使い分けることができる。

数学  2018/06/23  k.izumi