誕生日パラドックス
CSについて勉強しているのだが、MIT pressの Introduction to Algorithms (third edition) を130ページまで読み進めた。asymptotic notation のくだりが終わり、(asymptotic notationとは、すごく雑に言うと fn = Θ(gn) となっていれば fnはだいたいgnと等価（c1gn < gn < c2gnでc1, c2は固定値）、fn = O(gn) となっていれば（パフォーマンスで考えると）fnはO（遅くて）gn, また、fn= Ω(gn)となっていれば fnは（早くて）gn という感じである。これは nがとっても巨大な数であることが前提であり（n > n0）また、大文字以外に小文字もある(o(n), ω(n))。小文字と大文字の違いは大文字の場合はいくつかのnに対して法則が成立していればそれでいいが、小文字は全部に対して成立する必要がある）
話はずれたが、誕生日パラドックスのくだりがでてきて、「あ！」となった。これは昔ブロックチェーンの会社で働いてた時に Paar.Pelzl の Understanding Cryptographyを読んでた時にそっくりそのままおんなじくだりが Pigeon hole の関連ででてきた！！！！というかんじである。
誕生日パラドックスというのは、ようは確率論的に（１）複数人いたときに彼らのうち A さんと Bさんの誕生日が偶然一致する確率は？（２）複数人（n人）のうち、1組でも誕生日が一致する確率は？というものである。
難しい数式は、そもそもユニコードじゃ表現できないしめんどいんで、すっごく雑にいうと、
まず、その複数人を i = 1, 2, ....k とする。
そして、一年の日の数を n (=365)とすると、
そして、（１）AさんとBさんが特定の誕生日10/15で偶然一致する確率は、
1/n × 1/n = 1/n^2 である。
さらに、彼らが任意の誕生日で偶然一致するのは、
1/n^2 × n = 1/n となる。
また、Aさん、Bさん、とかじゃなくてとにかく誰でもいいから任意の2人が偶然誕生日が一致してしまう確率は、
１- 全員の誕生日が全部ユニークな確率(X)
である。
このXは、まず一番目の人は
1 （一番乗りだから誰ともぶつかるわけない）
二番目は
(n - 1)/n (一番目の人にごっつんこしなきゃいい）
3番目は
(n - 3 + 1)/n = (n - 2)/n (1,2番目の人にごっつんこしなきゃいい）
k番目は
(n - k + 1)/n
つまり
1 × (n - 1)/n × (n - 2)/n × ... (n - k + 1)/n
言い換えると
1 × (n - 1)/n × (n - 2)/n × ... (1 - (k - 1)/n)
さらに
1 × (1 - 1/n) × (1 - 2/n) × ... (1 - (k - 1)/n)
ちなみに、1 + x < e^x という法則 があるので、それで置き換えると
1 × e^(-1/n) × e^(-2/n) ... × e^(-(k-1)/n)
で、（ユニコードで書くのがしんどいので割愛するけど、塁上の部分がΣ式を使って単純な和にできるので、
＝e ^ -k(k-1)/2n
-k(k-1)/2n ≦ ln(1/2) と仮定すると、
e ^ -k(k-1)/2n ≦ e ^ ln1/2 = 1/2^lne(e) = 1/2 (対数の性質で、 a^loge(x) = x^loge(a) に置換できる）
つまり全部ユニークになるのは大体 1/2だよねって話になり、
１つでも誕生日が重複するのは おおよそ1 - 1/2=1/2 という結論になります。
超雑なまとめかたですが、一応これが誕生日パラドックスというやつになります。
で、このCS（計算機科学）のアルゴリズムがどういうところで登場するかと言うと、先ほど紹介したように暗号化理論のところで登場したりします。
CSについて勉強する意義は、僕も全体像はまだ見えてないんですが、基本的にこれが基礎的な前提知識としていろんなものができているということです。
暗号化のところでも、ちょっと記憶がうろ覚えですが Hashを破る時に Collisionについて考えるくだりがあり、（Collisionがあるとそこから搾取される原因になる）その流れでこのCSのアルゴリズムが登場したり、それから、GCCのソースコードとか読んでいくとグラフ理論ががっつり使われていたり、
「CSを知っている頭のいい人が作ってボランティアで提供してくれているものにフリーライド」して多くの僕たちエンジニアは何かを作っているわけで、
それを「民主化」というのは少し違うと言うか、言い方を変えれば、人の善意に甘えている、ともなる。
であれば、やはり高度なことをするためには（また、新しいものを作るとかするためには）どうしたってCSは必要になるんじゃないか、というのが今の感想です。（まだ把握しきっていないのであれですが）
No comments:
Post a Comment