# 二項分布 Navigation: [[index]] | [[overview]] ## 定義 二項分布(binomial distribution)は、n回の独立なコイン投げにおける表の枚数の分布として計算機科学で頻出する分布([[確率変数]]の一種の値域上の分布)である。コインが公平(表の確率1/2)な場合の**unbiased binomial distribution**は、値域 [0..n] 上の確率密度関数(pdf) f_n(k) := C(n,k)·2^{-n} で与えられる。これは、n回のコイン投げのうち表がちょうどk回になる並び方が C(n,k) 通りあり、各並びの確率が 2^{-n} であることから従う。f_n(k) のグラフは k=n/2 を頂点とする山型で、両裾(tails)は k が0やnに近づくにつれて急速に減衰する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.3.4) コインが確率 p で表になるよう偏っている場合の**general binomial distribution**は f_{n,p}(k) := C(n,k)·p^k·(1-p)^{n-k} で与えられる(k回表、n-k回裏となる並びが C(n,k) 通りあり、各並びの確率が p^k(1-p)^{n-k} であることから従う)。n=20, p=0.75 の場合、山の頂点は k=15付近に移動する。計算機科学における確率解析の多くは、この二項分布の裾に小さな上界を与える問題(サーバやリンクの過負荷、乱択アルゴリズムの異常な長時間実行や誤答などが「稀にしか起きない」ことを示す問題)に帰着する。裾は非常に急速に減衰し、例えば n=100, p=1/2 のとき25回以下しか表が出ない確率は300万分の1未満である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.3.4) n回の独立なコイン投げ(各回表の確率p)における表の枚数 J の**期待値**は、Jを「i回目が表かどうかの指示確率変数 Ji」の和 J=ΣJi として分解し、[[期待値]]の線形性を適用することで Ex[J] = pn と直ちに求まる。この手順により、二項係数を含む和の恒等式 Σ_k k·C(n,k)·p^k(1-p)^{n-k} = pn が、組合せ論的な変形を経ずに証明される。コインが独立でなくても、線形性は独立性を要求しないためこの結果 pn は変わらない。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5.3) ## 横断的知見 - 第18章では二項分布の裾が急速に減衰するという定性的な観察(n=100, p=1/2 のとき25回以下しか表が出ない確率は300万分の1未満)にとどまっていたが、第19章はこれを定量的な上界として回収する。(n,p)-二項分布に従う J は指示確率変数の和 J=ΣIk として、Var[Ik]=p(1-p)([[分散]]、Corollary 19.3.2)の対独立な和であることから Var[J]=np(1-p) が直ちに導かれ(Lemma 19.3.9)、この分散をチェビシェフの不等式に代入することで「裾が急速に減衰する」という第18章の定性的な観察を Pr[|J-np|≥x]≤np(1-p)/x^2 という定量的な上界に変換できる。さらに二項分布は 0≤Ik≤1 を満たす相互独立な指示確率変数の和でもあるため、チェルノフ限界(§19.6.3)を適用すればチェビシェフの多項式減衰より指数的に強い上界(例: 1000回の公平なコイン投げで表が20%以上超過する確率は1万分の1未満)が得られる。第18章で「頻出する分布」として導入された二項分布は、第19章で導入される3種類の集中不等式(マルコフ・チェビシェフ・チェルノフ)すべての標準的な適用対象になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.3.4, [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.3.4-§19.3.9, §19.6.3) - **性能評価の実務書(Jain)は、MCSが理論的に確立した「二項分布の分散は必ず平均を下回る」という事実を、分布選択の実務規則の暗黙の前提として使う**: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 29 Commonly Used Distributions]] §29.3は、二項分布の分散np(1-p)が平均npより常に小さいという性質(MCS第18-19章がpn・np(1-p)としてそれぞれ導出する量そのもの)を根拠に、「観測データの分散が平均より小さければ二項分布、等しければポアソン分布、大きければ負の二項分布を使う」という3分布間の選択規則を与える。MCSは二項分布を組合せ論・確率変数の理論として単独に扱い、この選択規則(他の2分布との比較)には立ち入らない。Jainの規則が成立する理由(なぜ二項分布の分散が必ず平均を下回るか)は、MCSの期待値の線形性・分散の加法性による導出まで遡らないと分からない。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 29 Commonly Used Distributions]] §29.3, [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.5.3, [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] §19.3.4) - **「ベルヌーイ変量の和が二項分布になる」という導出は、MCSの指示確率変数の和による分解とJainの分布関係図で独立に同じ形で示される**: MCS第18章はJ=ΣJi(Jiは各回の成功を表す指示確率変数)という分解を通じて二項分布を定義するが、これは確率変数の理論的な構成法としてのみ提示される。Jain第29章の図29.1(離散分布間の関係)は同じ事実を「ベルヌーイ分布からの矢印に和の記号ςxを添える」という形で、二項分布を含む分布体系全体の中の1つの導出関係として位置づける。両者は同一の数学的操作(ベルヌーイ変量の和)を、前者は単独の証明技法として、後者は分布どうしのネットワークの1辺として扱っており、後者を通じて初めて二項分布が幾何分布・負の二項分布・ポアソン分布と同じ「ベルヌーイ試行から派生する分布の族」の一員であることが見える。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 29 Commonly Used Distributions]] §29.20, [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] §18.3.4) ## 未解決の問い - n→∞ での二項分布の正規分布への収束(中心極限定理)は、本書の離散数学の範囲では扱われていない。Jain第29章§29.20は「二項分布はp→0でポアソン分布に、ポアソン分布はλ>9で正規分布に近づく」という2段階の極限は示すが、二項分布から正規分布への直接の収束条件(n→∞、npが一定という条件など)は示していない。 - チェビシェフの不等式による二項分布の裾評価(多項式減衰)とチェルノフ限界による評価(指数減衰)を同一の具体例(例: n=1000, p=1/2 の20%超過)で数値比較した記述は本章にはない。集中不等式ページの比較表と突き合わせて具体的な数値差を追記する余地がある。 - Jain第29章§29.3が示す「分散<平均なら二項分布」という選択規則を、MCSが確立する分散の加法性(対独立性で十分)の枠組みから、なぜ二項分布の分散が必ず平均を下回るかを明示的に式変形で示す記述は、いずれのソースにもまだ無い(np(1-p)<npは0<1-p<1から自明だが、この自明さを選択規則の正当化として明記した記述は本ページのソースにはない)。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 18 Random Variables]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 19 Deviation from the Mean]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 29 Commonly Used Distributions]] - 概念: [[確率変数]](二項分布は確率変数の分布の一種)、[[期待値]](二項分布の期待値 pn の導出に期待値の線形性を使う)、[[分散]](二項分布の分散 np(1-p) の導出)、[[集中不等式]](二項分布の裾へのチェビシェフの不等式・チェルノフ限界の適用)、[[確率分布の選択と関係]](分散と平均の大小関係による二項・ポアソン・負の二項の選択規則) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 18 §18.3.4, §18.5.3, Chapter 19 §19.3.4-§19.3.9, §19.6.3. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 29, §29.3, §29.20(二項分布の実務的な選択規則と、分布間関係図における位置づけ)。