Sen(Qian)’s Memo

第2回は集中不等式。どれだけの確率でアルゴリズムが成功するのかの判定。

$X$を非負の確率変数とする。

なぜなら、$1/k$を超える確率で$k \mathbb{E}[X]$を最低でも取るなら期待値はかならず$\mathbb{E}[X]$を上回るので矛盾する。

実はかなりガバガバな評価式。

クイックソートは最悪$O(N^2)$、期待値は$O(N \log N)$である。

計算時間が$2c n\log n$を超えたらソートを止めてやり直す。それ以外ならソートしなおす。最大このようなソートのやり直しはたかだか$d$回やるとする。$c$は定数。

これをマルコフの不等式で評価する。

このように指数的に収束するとわかる。

分散$\mathbb{V}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2$と標準偏差$\sigma[X] = \sqrt{\mathbb{V}(X)}$を定義できる。次の式がチェビシェフの不等式。

標準偏差の$k$倍を外れる確率は、たかだか$1/k^2$である。

非負であるという条件はないし、両側の確率を抑えている。マルコフだと、$k \sigma[X]$のかわりに$k^2 \mathbb{E}[X]$となることから、抑える精度のオーダが1つ上がったと言える。

まだ直感だが、$X = X_1 + \cdots$のように、有限個とすら限らない確率変数の和だとする。このとき、個数を無限まで増やすと$X$はガウス分布に収束する=中心極限定理があるので、以下のように更に指数関数的に集中しそうじゃない？

全人口の中である属性を持った人の数を知りたい。

全部で$n$人ある中で$b$人がその属性を持っている。上手くサンプリングして$b$を推定したい。

サンプルは独立で重複ありで選ぶことで作る。数がいっぱいあるので重複あったところで問題はない。サンプルの中で属性を持つのが$b_s$とすると、簡単に$b \approx b_s / s \times n$となるが、それが十分に正しいと示すのに使える。

$\delta$は信頼度、$\alpha n$は誤差だと言える。誤差を下げるのは大変(誤差を半分にするとサンプル数が4倍必要)だが、信頼度を上げるのは簡単(誤差を下げるとき、サンプル数は$\frac{\log 2}{\alpha^2}$増やせばいい)。

$X_i$は$i$番目のサンプルが属性を持っていると1、持たないときは0とする。

$\frac{\alpha ^2 }{s} = \log(2 / \delta)$となるので、これを代入して計算すると、見事に上の式が得られる。

ベルヌーイ分布$p^X(1-p)^{1-X}$に従うコイン投げの結果を重ねると、二項分布$B(s, p)$となる。これは、$s$回コインを振って表が出た回数。

ここで、$p=0.5$という前提で、$s$回コイン投げて表の回数が$s/2 + \alpha s$となる確率を正確に計算できる。二項係数をスターリングの近似を用いることで計算すると、$\sqrt{\frac{2}{\pi s}} e^{-\alpha^2 s}$になるとわかる。これはHoeffding Inequalityでの評価と一致するものであるので、不等式の評価は非常に正確であるということ。

しかし、性質上推定値には$\sqrt{1/s}$の誤差が出るのは仕方ない。