確率を使った一般化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/25 08:26 UTC 版)
次に、確率的な一般化を述べる。n 羽の鳩が m 個のそれぞれの巣へ 1 / m の確率で入れられるとすると、少なくとも1つの巣が2羽以上の鳩に占められる確率は、 1 − m ( m − 1 ) ⋯ ( m − n + 1 ) m n = 1 − m ( n ) m n , {\displaystyle 1-{\frac {m(m-1)\cdots (m-n+1)}{m^{n}}}=1-{\frac {m_{(n)}}{m^{n}}},} ただし、m(n) は下降階乗冪。n = 0, 1（で m > 0）のとき、確率は0である。言い換えれば、鳩が1羽のとき、衝突は起こらない。n > m であれば（鳩が巣より多ければ）、通常の鳩の巣原理を使い、確率は1である。しかし、たとえ鳩が巣より少なかったとしても（n < m でも）、巣への鳩の割当ての無作為性により、衝突が起こる可能性は十分にある。たとえば4個の巣に2羽の鳩ならば、少なくとも1つの巣が2羽以上の鳩に占められる確率は 25%。10個に5羽なら確率は 69.76% であり、20個に10羽なら 93.45% である。この問題は、もっと十分な長さでは、誕生日のパラドックスで扱われている。
※この「確率を使った一般化」の解説は、「鳩の巣原理」の解説の一部です。
「確率を使った一般化」を含む「鳩の巣原理」の記事については、「鳩の巣原理」の概要を参照ください。
ウィキペディア小見出し辞書の「確率を使った一般化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 確率を使った一般化のページへのリンク
