1/nの確率で観測できる事象をn回試行すると1度でも観測できる確率は□以上

確率

トリビアの種風なタイトルにしてみた．タイトルの答えは後半で述べる．

ことの発端は，「17の倍数であるナンバープレートを見つけるためには，車を何台観測しなければないか」というような雑談がきっかけ．こういう日常的な算数ができるとかっこいいなぁと思ったので，ちょっと考えてみた．

現在は希望ナンバーがあるため，ナンバーの分布には偏りがあるものの，ナンバーは一様分布していると仮定する．

すると，17の倍数はおおよそ1/17の確率で見つけることができる．ここで各観測はベルヌーイ試行と捉えることができるため，確率や統計の初歩的な知識でなんとかできそうな気がする．

たとえば，5回目に "初めて" 17の倍数を見つける確率は，4回17の倍数以外 (=16/17) の事象を観測し，5回目に1/17の事象を観測したと考えることができ，
(1 - \frac{1}{17})^4 \frac{1}{17} = 0.046
で求めることができる．

さて，これを一般化すると，確率pで起きる事象をk回目で初めて観測する確率は，
f(k; p) = (1 - p)^{k - 1} p
と表現することができる．実はこれ「幾何分布」と呼ばれる確率分布の確率密度関数になっている．

ここで気になるのは何台観測すれば90%以上の確率で17の倍数を見つけることができるのか，ということに興味がある．そこで，k台目に初めて観測するのではなく，k台目までに観測できる確率を求めるため，確率密度関数ではなく累積分布関数を利用する．

累積分布関数は難しいことを考えずとも求めることができる．k回目までの試行で「一度も観測されない」確率を1から引けばよい．すなわち，
F(k; p) = 1 - (1 - p)^k
で求めることができる．


さてさて道具が揃ったので計算してみる．x軸をkの値，y軸をF(k;p)にした図を描いてみた．

大体40回ということがわかる．
F(38; 1/17) = 1 - (1 - 1/17)^38 = 0.9002
これより，38回観測すれば90%の確率で17の倍数を発見できることがわかる．ちなみに，
F(17; 1/17) = 1 - (1 - 1/17)^17 = 0.6432
なので，1/17の確率で起こる事象を17回観測すると，1度でも観測できる確率は0.5より大きくなる．

それぞれの目が出る確率が1/6であるサイコロの話に変えると，6回振ったときに，1の目が1回でも出る確率は，
F(6; 1/6) = 1 - (1 - 1/6)^6 = 0.6651
となる．この数字についてなんだか直感よりも高い確率のような気がすると先輩にいちゃもんをつけられた．確かになんだか大きい気もする．けれど，なんかいくつ以上になるかということを証明できないものか．．

一般化をすると，
F(n; 1/n) = 1 - (1 - 1/n)^n
の確率が0.5より大きいかということを証明したい．

さて，これを眺めていて，オイラーの定理を思い出した．オイラーの定理とは x>0, a \ne 0に対して(1 + \frac{a}{x})^x < e^aが成り立つというもの．

第二項の(1 - 1/n)^nの部分をオイラーの定理で置き換えることができるではないか! 今回はa = -1と置いてあげると，

(1 + \frac{a}{x})^x < e^a
(1 - \frac{1}{x})^x < e^{-1}

e^{-1}=0.3679より，
(1 - \frac{1}{x})^x < 0.3679
したがって，
F(n; 1/n) = 1 - (1 - 1/n)^n > 1 - 0.3679 = 0.6321 (証明おわり)

これで確率が1/nであるような試行をn回繰り返したときに一度でも観測する確率は，nの値によらず0.6321より大きいことを証明できた．なお，nが小さいときの方がF(n;1/n)の値は大きく，nが大きくなると，0.6321に漸近していく模様 (n=10000のとき，0.632139)．

この数字は日常生活でも使える気がするので，(オイラーの定理の力を借りたけれど) 自分の力で証明できたのは本当にうれしかった．最近は@shuyoさんの影響もあり，自分がつかっている道具の仕組みくらいは理解しておこうと，普段お世話になっている数式 (ただし，簡単に証明できそうなもの) をがんばって自力で証明しようと心がけている．諦めてすぐに他人の証明を眺めるところがゆとりたるゆえん．

今回の件で指導教官に昔言われた言葉を思い出した「理論研究は，正しさを証明するために，道具をいくつ持っているかが重要になる．幅広い分野の道具を持っていないといけない」というもの((なお，理論研究をしていたのは指導教官．僕は理論研究なんぞやったことはありません)．確かに今回の証明はオイラーの定理がなかったら自分では絶対に証明できなかったと思う．ポアンカレ予想を解いたペレリマンは，当時は微分幾何学のアプローチで解けるだろうとされていた難問を，誰もが予想しなかった熱力学の道具を使って解いたという．ペレリマンの天才たるところは，数学のあらゆる分野に精通していたところだとか．

僕が知っている定理といえば，みんな大好きJensenの不等式と，今回出てきたオイラーの定理と，あとはナンダロウ．．．というくらい道具が少ない．最近は機械学習の理論寄りの話も勉強中なので，たくさん道具を増やせるようにしたい．


さて，上記のオイラーの定理について調べてみようとウェブで調べてみるとオイラーの定理と呼ばれる定理はたくさん存在し，上記の定理が一般的になんと呼ばれているのかを知ることができなかった．

なお，上記のオイラーの定理を知ったきっかけは，サポートベクターマシン入門 (p.73) のPAC学習の定理導出に関する訳注の部分．訳者様様です．うーん，しかし，なんて呼ぶんだろう．

(2011-04-08追記)

この定理を自力で証明してみた．部分的にしか証明できなかったけれど．