Probability and Computing

輪講で読んでいるのがこれ。

確率と計算 ―乱択アルゴリズムと確率的解析―

確率と計算 ―乱択アルゴリズムと確率的解析―


もとは英語です。
ちなみに僕はこの第五章すべてが担当になっていて、今は五節までやりました。

これコンピュータとは何にも関係無い確率論の話題が延々と半分くらい続き、説明に図はほとんど無くすべて数式で説明していく。…ように見えるのだが、意外とそうでもない。しかし、後半(数式が頻出する件)は間違いではないw

どうせブログをまんまと始めたことだし、これについて書いてみようと思う。そもそもこの本は、アルゴリズムの解析に確率論を導入すると便利ですよ、という内容の本。





余談ですが、普段コードを書くときに何を気にしているだろうか。探索空間の削減や、計算量の解析、オーダーの上界・下界・発散、そんなこと考えているのだろうか。

恐らく、実際にコードを書いているときにおいては、そんな抽象的なことは考えていないと思う。なぜかというと、そんなことを考えるよりは makefile のマニアックな書き方を Google で調べたりする方が楽しいから。世に数多ある妙ちくりんなライブラリを調べてみたり、成功した Web サービス社長のブログを読んだり、 .emacs を糞長くしてみたり、そんなことをしている方がよほど楽しいのである。

まぁいいや。余談なので、これ以上ここでは言わない。別エントリにしよう。
結論の問題空間を言えば、「emacsハックとコンサルもどきに精通している人間」と「Chernoff上界で乱択アルゴリズムの偽陰性確率上界を知ってからコード書く人間」と「趣味グラムをほとんどせず休日は本ばっかし読んでる出不精インドア教養のあるギーク」と、企業はどんなのが欲しいの?ということ。





さて余談はこのぐらいにして、本の続き。

「誕生日の逆理」というのがありまして、30人学級において誕生日が一致する生徒が少なくとも2人いる確率は70%を超えます。50%にするにはクラス人数が23人いればOKです。へー。

この「誕生日の逆理」は「ボールと瓶」という数学モデルの特殊な場合です。「ボールと瓶」というのは、瓶がずらずら並んでいるところに一様ランダムにボールを投げ入れる確率モデルのこと。瓶を誕生日、ボールを生徒に置き換えたイメージです。瓶の中のボールの数の分布や、最大内容量の下界・上界などが議論となります。

ちなみに、この「ボールと瓶」はハッシュの構造とよく似ています。つまり、このモデルを使うとハッシュを用いたアルゴリズムの計算量解析を定数倍(e\sqrt{m})誤差で厳密に行うことができます。

瓶の数がすっごく多く、ボールの数が相対的に0に近づくと、ボールの分布はポアソン分布になります。「相対的に」というのはnp\rightarrow \lambda(n\rightarrow \infty)という意味です。

ここでようやくアルゴリズムの話!
Poisson 近似において小さな確率で起こる任意の事象は、ボールが瓶に投げられるシナリオにおいてもまた小さな確率で起こります。前述したように、定数倍(e\sqrt{m})誤差です。これはすなわち、あるアルゴリズム内において、ある事象が小さい確率で起こることを示したいとき、確率変数の独立・非独立を厳密に解析するような趣味人なことをしなくても、その評価をPoisson確率変数とすれば、誤差内で厳密な評価を得られるということです。

で、Poisson分布には重要な性質があります。有り体に言えば、「Poisson分布の和はPoisson分布」ということです。「ごくたまぁーに起こるのを何回繰り返しても、結果的にはごくたまぁーにしか起きていない」ということです。

そ い つ ぁ す げ ぇ や !!

確率的データ構造においてごくたまに起きる偽陰性は、データ構造が巨大になってもごくたまにしか起きない、ということです。データ量とその関数であるハッシュの場合は、データ量の方が圧倒的に早く発散する(ように普通は設計する)ことを考えれば、これは強力な理論的背景を持っていることになります。

す げ ぇ や あ ん ち ゃ ん !!

何か疲れてきたので、一度閉じよう。。。