Poisson近似 - 某理論計算機科学者の研究日誌

Poisson近似という便利なテクニックを今やっている研究でたまたま使ったのでメモ程度に紹介します．

乱択アルゴリズムの解析などで「ビンに一様ランダムにボールを割り振る」というアナロジーを使って確率解析が行われることがよくあります．例えば「ある商品の n 種類のおまけを全部集めたい． m 個商品を買ったときに全部おまけが揃う確率は？」という問題も「 n 本のビンにランダムに m 個のボールを入れたとき，全部のビンにボールが入る確率は？」と置き換えることが出来るわけです．

上の問題のように事象が単純な場合は簡単な解析で確率を評価することができますが，もう少し込み入った事象では割と大変だったりします．こういうときに便利なのが「Poisson近似」と呼ばれる解析テクニックです．

この解析テクニックの肝は「各ビンのボールの個数をPoisson分布に従う確率変数で近似できるよ」ということです．このテクニックの嬉しい点は各ビンに入るボールの個数が互いに独立な確率変数で近似できるところです．近似なしで考えた場合，各ビンに入るボールの数は互いに独立ではないことに注意して下さい．（例えばたまたまあるビンに m 個全部入った場合には他のビンは間違いなく空です．）

もう少し形式的に書いてみます．今 $X_1,...,X_n$ を各ビンに入るボールの数を表す確率変数として $Y_1,...,Y_n$ を平均 $m/n$ のPoisson分布に従う互いに独立な確率変数とします．また ${\cal E}(X_1,...,X_n)$ を確率変数 $X_1,...,X_n$ のみに依存する任意の事象とします．このとき不等式
$\Pr({\cal E}(X_1,...,X_n))\le\sqrt{2\pi em}\Pr({\cal E}(Y_1,...,Y_n))$
が成立します．特に $\Pr({\cal E}(X_1,...,X_n))$ がボールの数 m に対して単調増加あるいは単調減少の場合には更に良い評価
$\Pr({\cal E}(X_1,...,X_n))\le 4\Pr({\cal E}(Y_1,...,Y_n))$
が得られます．証明は確率的計算の教科書

M. Mitzenmacher and E. Upfal
- Probability And Computing: Randomized Algorithms And Probabilistic Analysis

に載ってます．

具体的な使い方は次の機会に．