包除の定理 - 而して

〔参考文献：Williram Feller（河田龍夫ら訳）『確率論とその応用Ⅰ（上巻）』紀伊国屋書店, 2001.〕

（離散）標本集合を $\Omega$ とし、その部分集合である $n$ 個の事象 $A _ 1,\ A _ 2,\ \cdots,\ A _ n$ を考える。「ちょうど $m$ 個の事象のみが起こる」という事象 $A$ の起こる確率は、

$\displaystyle S _ k = \sum _ {\sigma \in \{ \sigma \in \mathfrak{S} _ k\ |\ \sigma(1) \lt \cdots \lt \sigma(k) \} } {\mbox{Pr}(A _ {\sigma(1)} \cap \cdots \cap A _ {\sigma(k)})}$

とおくとき（ $\mathfrak{S} _ n$ は $n$ 次の置換全体の集合）、

$P _ {[m]} = S _ m - \binom{m+1}{m} S _ {m+1} + \binom{m+2}{m} S _ {m+2} - \cdots \pm \binom{n}{m} S _ {n}$

で求めることができる。長い式で少し嫌になる（特にΣで和をとる範囲が面倒そうに思える）のだが、実用の幅が広い定理で（冒頭に示した参考文献で、色々の応用を扱っている）、とても重要だと思ったので、メモする。

証明. 次の式で、指示関数（indicator） という関数：

$\boldsymbol{1} _ {A} (x) = 1 \ (x \in A),\ 0 \ (x \notin A)$

を定める（ $\boldsymbol{1} _ A$ は $\chi _ A$ などとも書かれる）。つまり $\boldsymbol{1} _ A$ は、 $x$ を入力とし、 $x \in A$ ならば $1$ を, $x \notin A$ ならば $0$ を返すような関数である。この指示関数を用いると、

$\displaystyle P _ {[m]} = \sum _ {x \in A} {\mbox{Pr}(\{x\})} = \sum _ {x \in \Omega} {\mbox{Pr}(\{x\})} \boldsymbol{1} _ {A}(x),$

$\displaystyle S _ k = \sum _ {\sigma \in \{ \sigma \in \mathfrak{S} _ k\ |\ \sigma(1) \lt \cdots \lt \sigma(k) \} } { \sum _ {x \in \Omega} \mbox{Pr}(\{x\}) \boldsymbol{1} _ {A _ {\sigma(1)} \cap \cdots \cap A _ {\sigma(k)}}(x)}$ $\displaystyle = \sum _ {x \in \Omega} \mbox{Pr}(\{x\}) \sum _ {\sigma \in \{ \sigma \in \mathfrak{S} _ k\ |\ \sigma(1) \lt \cdots \lt \sigma(k) \} } \boldsymbol{1} _ {A _ {\sigma(1)} \cap \cdots \cap A _ {\sigma(k)}}(x)$

と表すことができる。記号の便宜で、

$\displaystyle s _ k(x) = \sum _ {\sigma \in \{ \sigma \in \mathfrak{S} _ k\ |\ \sigma(1) \lt \cdots \lt \sigma(k) \} } \boldsymbol{1} _ {A _ {\sigma(1)} \cap \cdots \cap A _ {\sigma(k)}}(x)$

とおくことにしよう。よって $S _ k = \sum _ {x \in \Omega} \mbox{Pr}(\{x\}) s _ k(x)$ となる。以上のことから、示したい式は

$\sum _ {x \in \Omega} {\mbox{Pr}(\{x\})} \boldsymbol{1} _ {A}(x)$

$= \sum _ {x \in \Omega} \mbox{Pr}(\{x\}) (s _ m(x) - \binom{m+1}{m} s _ {m+1}(x)$ $\hspace{1in} + \binom{m+2}{m} s _ {m+2}(x) - \cdots \pm \binom{n}{m} s _ {n}(x))$

と書くことができるので、任意の $x \in \Omega$ について、

$\boldsymbol{1} _ A(x)$ $= s _ m(x) - \binom{m+1}{m} s _ {m+1}(x) + \binom{m+2}{m} s _ {m+2}(x) - \cdots \pm \binom{n}{m} s _ {n}(x)$

を示すことができれば証明が終わる（もはやこれは確率論というよりも集合論であることに注意されたい。この定理の本質はこの式に他ならない。 なお、例えば $\Omega$ を有限集合と仮定して、 $T \subseteqq \Omega$ について $\mbox{n}(T)$ で $T$ に含まれる元の個数を表すことにすれば、 $\mbox{Pr}()$ を $\mbox{n}()$ で置き換えるだけで上の議論をそのまま使って $\mbox{n}()$ に関する同様の定理が証明できる）。

$x \in A$ の場合。このとき、 $x$ はちょうど $m$ 個の事象 $A _ {i _ 1},\ \cdots,\ A _ {i _ m}$ のみに含まれるのだったから、 $s _ {m+1}(x) = \cdots = s _ {n}(x) = 0$ となるので、 $s _ {m}(x) = 1$ を示せばよい。 $i _ 1,\ \cdots,\ i _ m$ を昇順（小さい順）に並び替えて $j _ 1 \lt \cdots \lt j _ m$ が一意に定まるので、 $s _ {m}(x)$ のΣのうちで、 $\sigma(1) = j _ 1 ,\ \cdots,\ \sigma(m) = j _ m$ なるただひとつの $\sigma$ についての項のみが残り、この項の値は $1$ である。ゆえに $s _ m(x) = 1$ となる。

$x \notin A$ の場合。 $x$ は $A _ 1,\ \cdots,\ A _ n$ のうちで、ちょうど $r$ 個 $(r \neq m)$ の事象に含まれるとする。 $r \lt m$ ならば $s _ m(x) = \cdots = s _ {n}(x) = 0$ となるから成立するので、以下 $r \gt m$ とする。なお、やはり $s _ {r + 1}(x) = \cdots = s _ {n}(x) = 0$ は成立つので、示すべくは、

$0 = s _ {m}(x) - \binom{m+1}{m} s _ {m+1}(x) + \cdots \pm \binom{r}{m} s _ {r}(x)$

である。

$x$ は $r\ ( \gt m)$ 個の事象に属するから、 $m \leqq c \leqq r$ について、 $s _ {c}(x)$ のΣのうちで、残る項は $\binom{r}{c}$ 個だけあり（これがポイントである。 $\sigma(1) \lt \cdots \lt \sigma(c)$ という条件が附されているので、 $r$ 個から $c$ 個を選ぶ組合せの総数と同じだけ項が残る）、その値はすべて $1$ であるから、 $s _ {c}(x) = \binom{r}{c}$ が成立つ。したがって、示す式は、

$0 = \binom{r}{m} - \binom{m+1}{m}\binom{r}{m+1} + \cdots \pm \binom{r}{m}\binom{r}{r}$

とかける。ここで $\binom{m+y}{m} \binom{r}{m+y} = \binom{r}{m} \binom{r-m}{y}$ が成立するので、

$0 = \binom{r}{m} \left\{\binom{r-m}{0} - \binom{r-m}{1} + \cdots \pm \binom{r-m}{r-m}\right\}$

と変形できるが、この右辺の $\{\}$ の中は $(1+(-1)) ^ {r-m}$ の二項展開だから（右辺） $=0$ が得られる。これで証明が終わった。終

この定理の効力を見るために、参考文献から一例を借用しよう。

$1, 2, \cdots, n$ と番号の書かれたカードが二組あって、一方を番号が昇順になるように、横一列に机に並べる。そのすぐ下に、他方をシャッフルして横一列に並べる。結果として机には二列の $n$ 枚のカードが並び、上は整列されていて、下は勝手に並んでいる、という状況になる。 $n= 5$ ならば、例えば

$1\ \ 2\ \ 3\ \ 4\ \ 5$

$3\ \ 2\ \ 1\ \ 5\ \ 4$

という風に並んでいるのである。このとき、この二列を縦にみて、上下で数字が一致しているか否かを考えよう。この例では、 $2$ のみが一致している。

さて、下列の並び方は全部で $n !$ 通りある。そこで、どの並び方も同じ確率 $1 / n !$ で起こると仮定するとき、ちょうど $m$ 個の数字が一致する確率はどれくらいだろうか？

下列の並び方を、数字をカンマ区切りで横に並べて括弧でまとめることで表現しよう。先の例なら $(3,2,1,5,4)$ と表すことができる。逆に、 $n$ 個の数字によるこの表記から、ある一つの下列の並べ方が対応するので、下列の並び方のすべてをこのような表記で統一的に表すことができる。従って、直積を用いて標本空間 $\Omega$ は $\Omega = \{1, 2, \cdots, n\} ^ {n}$ とかける。

事象 $A _ k$ を「番号 $k$ が一致する」ことによって定める $(1 \leqq k \leqq n)$ 。厳密に言えば $A _ k = \{(i _ 1, i _ 2, \cdots, i _ {k-1}, k, i _ {k+1}, \cdots, i _ {n})\ |\ 1 \leqq i _ 1, i _ 2, \cdots, i _ n \leqq n\}$ とかくことができる。含まれる元の個数は $(n-1) !$ である。求めたい確率は、事象 $A$ を「 $A _ 1, \cdots, A _ n$ のうちでちょうど $m$ 個のみの事象が起こる」ことと定義して $P _ {[m]} = \mbox{Pr}(A)$ とかけるので、定理の記号で、

$\displaystyle S _ k = \binom{n}{k} \dfrac{(n-k) !}{n !} = \dfrac{1}{k !}$

であるから、

$P _ {[m]} = S _ m - \binom{m+1}{m} S _ {m+1} + \binom{m+2}{m} S _ {m+2} - \cdots \pm \binom{n}{m} S _ {n}$

$= \dfrac{1}{m !} - \dfrac{(m+1) !}{m! 1 !} \dfrac{1}{(m+1) !} + \dfrac{(m+2) !}{m! 2 !} \dfrac{1}{(m+2)!} - \cdots \pm \dfrac{n !}{m!(n-m)!}\dfrac{1}{n!}$