2015/09/27

ブールの不等式の証明と応用例

分野: データの分析,確率  レベル: マニアック

事象 $A_1,A_2,\cdots,A_n$ に対して
$P(A_1\cup A_2\cup\cdots\cup A_n)\leq \displaystyle\sum_{i=1}^nP(A_i)$

ブールの不等式について

事象 $A_1,A_2,\cdots,A_n$ のうちどれか一つでも起きる確率 $P(A_1\cup A_2\cup\cdots\cup A_n)$ を上からおさえる不等式です。ユニオンバウンドとも言います。

$n=2$ の場合:$P(A\cup B)\leq P(A)+P(B)$
$n=3$ の場合:$P(A\cup B\cup C)\leq P(A)+P(B)+P(C)$

「どれか一つでも起きる確率はそれぞれが起きる確率の和よりも小さい」という当たり前の不等式です。

各事象が互いに排反なら等号が成立します。

ブールの不等式の証明

感覚的には当たり前の不等式ですが,一応証明しておきます。 $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ を使います。

証明

帰納法で証明する。 $n=1$ のときは自明。

$n=k$ のとき正しいと仮定する。先述の公式を $A=A_1\cup\cdots \cup A_k,B=A_{k+1}$ として使うと,
$P(A_1\cup\cdots\cup A_{k+1})=P(A_1\cup\cdots\cup A_k)+P(A_{k+1})\\
-P((A_1\cup\cdots\cup A_k)\cap A_{k+1})$

ここで,帰納法の仮定より右辺第一項は $\displaystyle\sum_{t=1}^kP(A_t)$ 以下であることと,$P((A_1\cup\cdots\cup A_k)\cap A_{k+1})$ が非負であることから $n=k+1$ のときもブールの不等式は正しい。

ブールの不等式の応用例

マルコフの不等式やチェビシェフの不等式から得られるバウンドよりも強い結果です!

$n$ 種類のコンプガチャ(景品は全て等確率)を $2n\log n$ 回引いてもコンプリートできない確率は $\dfrac{1}{n}$ 以下。

ちなみにコンプリートするまでの回数の期待値はだいたい $n\log n$ です。→コンプガチャに必要な回数の期待値の計算

証明

$2n\log n$ 回引いても $k$ 番目の種類のガチャが一回も当たらない確率を $A_k$ とおく。
コンプリートできない確率は $P(A_1\cup \cdots\cup A_n)$ であるが,これはブールの不等式より $\displaystyle\sum_{k=1}^nP(A_k)=nP(A_1)$ 以下である。

ここで,
$P(A_1)=\left(\dfrac{n-1}{n}\right)^{2n\log n}\\
=\left\{\dfrac{1}{(1-\frac{1}{n})^{-n}}\right\}^{\log n^2}\\
\leq \dfrac{1}{e^{\log n^2}}\\
=\dfrac{1}{n^2}$
より主張は示された。

注:途中の不等号では $\left(1-\dfrac{1}{n}\right)^{-n}\geq e$ を使っています。
これは $\left(1-\dfrac{1}{x}\right)^{-x}$ が $x > 1$ 単調減少であること(微分すると分かる)と $x\to\infty$ で $e$ となることから分かります。

期待値の二倍くらい頑張ってもコンプできない人は相当運が悪いということです。
分野: データの分析,確率  レベル: マニアック