(講義ノート)乱択アルゴリズム第9回

こうすると、二項分布の3つ以上の選択肢があるようになると考えられ、これは多項分布である。

多項分布に従う時、以下のようなことになる。

Pr[X_i = k] = {}_m C_k p_i^k (1 - p_i)^{m-k} \approx \frac{m^k}{k!} p^k e^{-p_i(m-k)} \\ = \frac{(p_i m)^k}{k} e^{-p_i m} = \frac{\mu^k e^{-mu}}{k!}

ここでは、 $k$ が $m$ よりずっと小さく、その時は $(1-p_i)^{m-k} \approx e^{-p_i (m-k)}$ と置き換えている。

するとこれによってポアソン分布を導けた。

二項分布に従い毎回確率 $p$ で起きる事象について、 $n$ 回の試行について考える。この時、 $np=const$ と固定して、極限で $n\to\infty$ とすれば、同様にポアソン分布が得られる。このような場面での計算にポアソン分布を使うと言い、という感じ。

Pr[y=k] = \frac{\mu^k e^{-\mu}}{k!}

ポアソン分布の性質は以下の通り。

\mathbb{E}[y]=\mu, V[y]=\mu

例えば、 $Pr[y=\mu]$ を計算してみる。二項分布では、試行回数を増やすと、真ん中に集中するけどぴったり $\mu$ となる確率は $1/\sqrt{n}$ のオーダーで減少していた。これはポアソン分布でも同様に成り立つ。スターリングの近似を使う。

k! = \sqrt{2 \pi k} (k / e)^k \\ Pr[y=\mu] \approx \frac{\mu^k e^{-\mu}}{\sqrt{2\pi \mu} \mu^{k} e^{-\mu}} = \frac{1}{\sqrt{2 \pi \mu}}

翻って、 $Pr[y=\mu + \Delta], -\mu \leq \Delta \leq \mu$ の間に収まる(つまり $y \in [0, 2 \Delta]$ に収まる確率を計算してみる。

Pr[y=\mu + \Delta] = \frac{\mu^{\mu + \Delta} e^{-\mu}}{(\mu + \Delta)!} = \frac{\mu^{\mu + \Delta} e^{-\mu}}{\sqrt{2 \pi (\mu + \Delta)}(\mu + \Delta)^{\mu + \Delta} e^{-(\mu + \Delta)}} \\ = \frac{1}{\sqrt{2 \pi \mu} \sqrt{1 + (\Delta / \mu)}} \frac{e ^ \Delta}{(1 + (\Delta / \mu))^{\mu + \Delta}} = \frac{1}{\sqrt{2 \pi \mu} \sqrt{1 + (\Delta / \mu)}}

ここでは、最後に $e^\Delta$ の項の分母で極限をとってるわけではないが、 $e$ を作り出すと考えると、そこが1になって、ちょうど打ち消し合う。わりと $y = \mu$ の場合とも整合性取れてそう。

y_i \sim Poi(\mu_i) \Rightarrow \sum _i y_i \sim Poi(\sum_i \mu_i)

つまり、ポアソン分布のパラメタの和を取ったものに従う変数は、別々のポアソン分布だと考えた時の変数の和と同じ。

証明は以下の通り。

Pr[y_1 + y_2 = k] = \sum_{0 \leq k_1 \leq k} Pr[y_1 = k] Pr[y = k - k_1] = \sum_{0 \leq k_1 \leq k} \frac{e^{-\mu} \mu_1^{k_1}}{k!} \frac{e^{-\mu_2} \mu_2^{k-k_1}}{(k-k_1)!} \\ = \frac{e^{-(\mu + \mu_2)}}{k!} \sum_k \mu_1^{k_1} \mu_2^{k-k_1} \frac{k!}{k_1!(k-k_1)!} = \frac{e^{-(\mu_1 + \mu_2)}(\mu_1 + \mu_2)^k}{k!}

$p_1, \cdots$ が固定されているとする。 $X_i$ を $m$ 回ボールを投げた時の $i$ 番目のビンのボールの数とする。

$y_i^{(m)}\sim Poi(m p_2)$ だとする。

次に、以下のようにベクトルを定める。

これについて、条件付等価性が成り立つ。成り立つならば、相関している難しい分析を独立している簡単な分析ですり替えられる。

$\sum_{i} y_i^{(m)} = k$ が成り立つとき、 $\mathbf{x}^k$ と $\mathbf{y}^m$ の分布が一致するという特徴がある。

つまり、ポアソン分布に従う変数の和が $k$ で固定されるなら、ボールビンの $\mathbf{x}^k$ と等しくなる。

まず、両辺をそれぞれ展開する。

Pr[\mathbf{x}^k = (k_1, \cdots, k_n)] \:\: \mathrm{for \: this \; condition} \: \: (\sum_i k_i = k) \\ = k! \prod _{i=1}^n p_i^{k_2} \frac{p_i^{k_i}}{k_i !}

次に、 $\mathbf{y}^m$ を展開する。これは前提があるので、条件付確率である。以下のように導ける。

Pr[\mathbf{y}^m = (k_1, \cdots, k_n) | \sum_i k_i = k] = \frac{\prod_{i=1}^n e^{-mp_i} (mp_i)^{k_i} / k_i!}{e^{-m} m^k / k!} \\ \frac{\prod_{i=1}^n e^{-m p_i}}{e^m} \frac{\prod_{i=1}^n m^{k_i}}{m^k} k! \prod_{i=1}^n (\frac{p_i ^ {k_i}}{k_i!}) \\ = 1 \cdot 1 \cdot e^{--\Delta^2 / \mu} \times \Theta(\frac{1}{\sqrt{\mu}}) \\ \sum_{0 \leq k_1 \leq k} \frac{e^{-\mu_1} \mu_1 ^ {k_1}}{k_1!} \frac{e^{-\mu_2} \mu_2 ^{k - k_1}}{(k-k_1)!}

以下のように取りうる範囲が抑えられる。

非負の $f : \mathbb{R}^n \to \mathbb{R}_+$ があり、 $\mathbb{E}[f(\mathbf{x}^m)]$ は $m$ に対して広義単調増加か、広義単調減少が成り立つとする。この時以下のように成り立つ。

\mathbb{E}[f(\mathbf{x}^m)] \leq 2 \mathbb{E}[f(\mathbf{y}^m)]

\mathbb{E}[f(\mathbf{y}^m)] = \sum_{k=0} ^ \infty \mathbb{E}[f(\mathbf{y}^m) | \sum_i y_i^{(m)} = k] Pr[\sum_i y_i^{(m)} = k] \\ = \sum_{k=0} ^ \infty \mathbb{E}[f(\mathbf{x}^k)] Pr[\sum_i y_i^{(m)} = k]

まず、先ほど示した条件付等価性で置き換えられる。

\geq \sum_{k=m} ^ \infty \mathbb{E}[f(\mathbf{x}^k)] Pr[\sum_i y_i^{(m)} = k] \geq \sum_{k=m} ^ \infty \mathbb{E}[f(\mathbf{x}^k)] Pr[\sum_i y_i^{(m)} \geq m] \\ \Rightarrow \mathbb{E}[f(\mathbf{x}^m)] \leq 2 \times \mathbb{E}[f(\mathbf{y}^{(m)})]

最初の不等号では、 $f$ は非ゼロなので成り立ち、2つ目の不等号は $\mathbb{E}[f]$ は広義単調増加なので成り立つ。もし、広義単調減少であると考えたいときは、 $Pr[\sum_i y_i^{(m)} \leq m]$ で置き換えればよい。

そして、最後に $\sum_i y_i^{(m)}$ はポアソン分布 $Poi(m)$ に従う(ポアソン変数の和もまたポアソン変数である)ことから、これが $m$ を超える確率ということに。これは $1/2$ よりは大きい値になるので、最後の結果が成り立つということ。

この時、代わりにポアソン分布の変数 $\mathbf{y}^m$ をみればいい。

コイントスを $m$ 回繰り返す。表が $p$ の確率で出るとき、表の回数 $Bi(m,p)$ であり、裏の回数は $Bi(m, 1-p)$ である。

ここで、 $k \sim Poi(m)$ とおして、 $k$ 個コイントスをする。この時、表の回数と裏の回数は独立である。