2004年11月02日

たまには計算を

知人のBlog
「23人集まれば、その中に同じ誕生日の人がいる確率が50%を超える。」
なんて事を書いていた。
初トラックバックを兼ねてこいつを検証してみようと思う。

ちなみにblogへの表の挿入の実験もかねてます。

まずn(>1)人以上の人間がいるときに誕生日が全員異なる確率を求める。
それを1から引けば求めたい「n人の人間がいるとき誕生日が同じ人間がいる確率q(n)」が求められるわけである。

いきなりnで考えても簡単なのだが、それだと書くことがなくなってしまうのでとりあえず小さい場合から試して帰納的に解くことにする。

1年の日数をdとし、「n人の人間の誕生日がばらばらである確率」をp(n)とする。

(1)n=2のとき
2人目の誕生日が1人目と異なればいいのだから
    d-1
p(2)=
  d

(2)n=3のとき
3目の誕生日が1人目、2人目と異なればいいのだから
    (d-1)(d-2)
p(3)=
  d2


n=3の時の考え方を一般化する
人が一人増えた時(つまりnが1増えた時)の確率は、それまでの確率に(d-増える前の人数)/dをかければいい
つまり、kを2以上の自然数として
        d-k
p(k+1)=p(k)×
    d


以上より
    (d-1)(d-2)・・・{d-(n-1)}
p(n)=
  dn-1

順列の関数であるnPkを用いてあらわすと
    d-1Pn-1   dPn  
p(n)=
=
・・・(1)
  dn-1 dn 


さてこれで「n人の人間の誕生日がばらばらである確率」が求められたので
本題である「n人の人間がいるとき誕生日が同じ人間がいる確率q(n)」は1-p(n)なので
        dPn  
q(n)=1-
・・・(2)
    dn 

あきらかにp(1)=1,q(1)=0なので(1),(2)式はn=1にも拡張できる
またn>dのときは常にp(0)=0,q(1)=1) (∵鳩の巣定理)
よって(1),(2)式の定義域は1≦n≦d


さて、具体的に計算してみよう
d=365,n=1〜30においてエクセルに計算させてみたのが以下の表である
n123456789101112131415
p(n)10099.799.298.497.396.094.492.690.588.385.983.380.677.774.7
q(n)00.270.821.642.714.055.627.439.4611.714.116.719.422.325.3
n161718192021222324252627282930
p(n)71.668.565.362.158.955.652.449.346.243.140.237.334.631.929.4
q(n)28.431.534.737.941.144.447.650.753.856.959.862.765.468.170.6

ただし確率は百分率に直して少数第二位で四捨五入してある

たしかにn=23の時に50%をこえる。
以上で検証終わり。

久しぶりに確率なんてものを計算してみました。
内容的には高校数学で十分ですね

2004/11/10修正:分数表記の修正、nの上限を言及

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/b_trumpet/8779631
この記事へのトラックバック
「23人集まれば、その中に同じ誕生日の人がいる確率が50%を超える。」 などということを私の旧ブログに書いていたが、それを実際に検証した友達がいた。 詳しくは知人のブログを見ていただきたい。 はっきり言って感心した。よく検証したなぁと。 しかし、実...
バースデーパラドックス検証結果by電脳少年みぞ【ふじこchannel】at 2004年11月24日 21:33
この記事へのコメント
それでもー
わからないー

というわけで初登場でした。
数学なんて中3以来やってないぜ。みたいな。

最近ようやく必要性を感じて高校の教科書をやりはじめましたけど。
Posted by あわ at 2004年11月03日 00:24
あんた、天災や!!
いや、天才や!!

某暗号研究家にこのことを伝えておきます。

しかし、こういう計算て本当に興味がないとやる気にならんね。
あんたくらいになると、こういう計算がどのくらいの時間で解けるんか教えてほしいわ。
そっこーなんやろか。
Posted by ふじこさん at 2004年11月04日 09:59
をぉ、素晴らしい!どっかの大学の入試問題みたいですね。(笑)

プログラマの命は、アルゴリズムとデータ構造。
優秀なプログラマとお見受けします。

厳密に言うと、上記P(n)の式が成り立つのは、n <= (d+1) までかな。
P(366) = 0 は正しくて、必ず同じ誕生日の人がいる状態。

n > 366 では、P(n)は n が奇数の時に負になりますね。
n > (d+1) に関しては、常にP(n) = 0, Q(n) = 1 が正解かな。

まぁ、重箱の隅ですが...

ちなみに、こういうの指摘するのが得意なのが、検証エンジニア。(例外試験、限界値検証)
プログラマがここまで考えると先に進まないんですよね...
Posted by MasaGon at 2004年11月06日 01:05
まとめレスですみません
敬称略します。

>あわ
こんな駄文blogへいらっしゃいませ。
今読み返すとでてくる式の根拠をまったく説明してませんね。
これでは入試だと点をくれないなぁ(笑)
そのうち補足を書こうと思ってますのでお待ちあれ。

>ふじこさん
某暗号研究家って誰でしょ?予測はできるんですが。
これって確率求めるだけなら簡単ですよ。
むしろexcelで計算させてそれをhtmlにするのに数倍の時間がかかりました。
q(n)求めるだけなら5分程度です。
そのうち拡張(同じ誕生日のペアがm組できる確率とか)してみます。

>MasaGon
nの上限は書いたほうがいいかなとは思ったんですけど今回は23の時に50%を超えることの検証だったので不精しました。
とはいえ途中で不必要にn=1に拡張したりしてるので上限も言及すべきでした。
ってことでそのうち修正します。分数が読みにくいのでこの表記もどうにかしようと思ってますし。

あぁ、「そのうち」が多い・・・
Posted by みぞて at 2004年11月06日 13:21
更新お疲れ様です。これからも定期的に頑張ってください。

確率とかは「数学やってて良かった」と思える楽しめの計算であるということを
最近の授業で知りました。ゲーム理論が確率計算ではよく扱われますが、ポーカーの手の
出る確率なんかはなるほどーと思えますよね。

MasaGonさんの指摘は納得です。
というか自分が必要なプログラムを書くレベルだと、そういうイレギュラーな
状態の定義をついつい省いてしまいがちなんですよね。
一般に配布できるようなフリーソフトの開発者の方は本当にすごいと思います。
Posted by うえだ at 2004年11月07日 22:16
修正してみました。
式が見易くなったかと。
Masagonさんご指摘のnの範囲も言及しました。

htmlで数式入力ってめんどくさいですね。
小汚くtableで書いてみたんですがtexで書きたくなりました。

数式onlyのtex→htmlコンバータでも作ろうかな
Posted by みぞて at 2004年11月10日 18:00
おぉ、見やすくなりました!

大体、この手の数式を扱うサイトだと、数式は画像貼り付けちゃってるのが多いかもね。

MS Officeの数式エディタからhtml変換って出来ないんだっけ?
Posted by MasaGon at 2004年11月13日 10:52
個人的に画像貼り付けは嫌いなんです。
htmlもtexも文章の構造を表す言語なんだからこれで表したいなと思います。

ということでhtmlでの数式表現をちょっとしばらく掘り下げてみようと思います。
Posted by みぞて at 2004年11月18日 00:46