Probability Theory Practices (Easy)

　確率論の問題を解いた。確率論のtutorial+レベル別問題まとめみたいなのがあったのでやってみた。

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities

level 1:はbrute force系の問題が多かった。

特に難しい問題はなかったが、面白そうな話題があったので紹介。

BirthdayOdds - SRM 174

　1年がN日から成り立つ世界がある。何人の人を集めれば、同じ誕生日の人が少なくとも2人出てくる確率がP(%)以上になるか？

というような問題。

　問題文にあるように、「クラスに23人いれば、同じ誕生日の人がいる確率は50%を超える。」というのは有名な話。counter-intuitiveな確率の話として、覚えておいて損はないかも。

BenfordsLaw - SRM 155

　この法則は知らなかった。

日常生活にでてくる数字の多くは、以下の確率に従う。

最大桁の数値がdである確率は、log10(1 + 1/d)。

　これは面白い。数字の最大桁の値は一様分布に従うと思いきや、違うらしい。この法則によると、最大桁が1である確率は、30%を超える。50%の確率で、数字の最大桁の値は、1または2となるらしい。

　この問題では、この法則を用いて、金融機関のtransactionの監査を行う。金融機関で取引された金額リストを取得して、すべての数字の最大桁の値dをサンプリングする。適当な閾値を設定しBenford's Lawに従わない値dが存在すれば、それらの取引には何らかの不正があると考え厳重に監視する。

　プロコンの問題という観点では単純な実装ゲーだったが、この法則と問題の内容が面白かった。

　余談になるが、この問題では予めlog10(1+ 1/d), d=1,2,...,9を計算してstaticなテーブルに入れておくとよい。今回は、求める数値が9つなので起動時に計算しても問題ないが、求める個数が大きくなった場合はメタプログラミングの対象になるのかなと思った。とか何とか考えながら、いろいろ調べてたらこんな変態postを発見。なんだこれは（笑）面白そうじゃなイカ。