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

$n$ 個のビン、 $m$ 個のボールがある。各ボールを一様ランダムに選んだビンにいれる。

これはハッシュという有名な応用例がある。そこで、上手いこと衝突は避けたいよね。

誕生日のパラドックスで、 $\Theta(\sqrt{m})$ の時に衝突する。これは、予想よりも小さい数で衝突するぞ！ということがいえる。

つまり、ハッシュで言うと衝突する確率。

$E_i$ を「 $i$ 番目のボールがこれまですべて入れてきたビンと違うビンに入っている」という事象だとする。

以下のように、事象としては積集合である。積集合のprodは独立非独立問わず、以下のように条件付き確率で計算できる。

Pr[\bigcap _{i=1}^n E_i] = \prod _{i=1}^n Pr[E_i | \bigcap _{j=1}^{i-1} E_j] \\ = \frac{n}{n} \cdot \frac{n-1}{n} \cdots \frac{m+1}{n} = \prod_{i=1}^m (1 - \frac{i-1}{n})

ここで、 $1 - x \leq e^{-x}$ を利用して挟めば以下のようにできる。指数関数はまとめて計算できるという利点がある。

\prod_{i=1}^m (1 - \frac{i-1}{n}) \leq \prod_{i=1}^m \exp(-(i-1)/n) = \exp(-(m-1)m/n)

これについて、 $m \geq \sqrt{2n \log 2} + 1$ で $1/2$ を切ることになる。さらに、 $k\sqrt{n}+1$ と入れ替えれば、上界は $\exp(-k\sqrt{n}(k\sqrt{n}+1)/n) \leq \exp(-k^2/n)$ で抑えられる。

よって、 $\Theta(\sqrt{m})$ というわけである。

$n$ 個の景品が等確率で現れるガチャで、景品コンプするために引くべき回数の期待値を計算してみる。期待値の線形性や調和級数の評価をすることで、 $\Theta(n \log n)$ 回引く必要があるとわかる。

証明として、丁寧に確率変数を設定して解くのもできる。

ハッシュを考えると、すべての項に $\Theta(1)$ 個の値が割り当てられるのが望ましい。

$X_i$ を $i$ 番目のビンのサイズ=入っている要素数だとする。

$m = cn$ とする。 $c>1$ で、チェルノフ上界により、( $R=(1+\delta)$ として)

Pr[X_i \geq (1 + \delta) c] \leq (\frac{e^\delta}{(1 + \delta)^{1 + \delta}})^c \leq (\frac{e ^ {1 + \delta}}{(1 + \delta)^{1 + \delta}})^c \\ \leq (\frac{1 + \delta}{e})^{-(1 + \delta)c} \leq (\frac{R}{ce})^{-R}

この確率は中心からばらける確率。これが、 $1/n^2$ になるように選ぶとき、こんなふうにUnion Boundを使えるらしい。

Pr[\max X_i \geq R] \leq Pr[\bigcup _{i=1}^n X_i \geq R] \leq \sum_{i=1}^n Pr[X_i \geq R] \leq \frac{1}{n}

もし、 $(R/(ce))^{-R} < 1/n^2$ ならば、以下のようになる。

(\frac{R}{ce})^R > n^2 \Rightarrow R \log R \pm \theta(R) \geq 2 \log n \\ \Rightarrow R=\Omega(\frac{\log n}{\log \log n})

最大負荷はそれになる確率はたかだか $1/n$ で抑えている。

Pr[X=k] = \frac{\mu^k}{k!}e^{-\mu} \\ \mathbb{E}[X] = \mu

二項分布について、 $\lim _{n \to \infty} Bi(\mu n, 1/n)$ でポアソン分布に収束する。

ポアソン分布の和は同様にポアソン分布であり、パラメタはすべてそのまま足し合わせればよい。