■23と253(その4)

[Q]同じ部屋にいる人のうち,少なくとも二人の誕生日が同じになるためには,その部屋には少なくとも何人いればよいか?

  k≧(1+√(1+8nlog2))/2

であるから,一般にk>√nより少し多くの人がいればよいことがわかる.

 k>1.18√n

===================================

 アメリカの数学者ポール・ハルモスによれば,n人が集まっていてそのうちの二人の誕生日が同じになる確率が50%を超えるためには,

  n>1.18×(365)^1/2=22.544

となることが必要であるという.

 ハルモスの概算公式は,cを定数として

  c=(−2log(0.5))^1/2=(log4)^1/2〜1.18

  n>c×(365)^1/2

というものである.

 今回のコラムでは,この概算方法がどのようにして見つけられたものなのか考察してみることにする.

===================================

【Q1】自分の誕生日のパーティーに大勢の人を招待することにする.自分の誕生日がそのうちのひとりと同じのなる確率が50%を超えるには何人招けばよいか?

(A1)ひとりの誕生日が自分の誕生日と同じにならない確率は364/365.n人の客がいて,すべて自分の誕生日と同じにならない確率は(364/365)^n.

 自分の誕生日と同じ人がひとりはいる確率は

  1−(364/365)^n>0.5

より,n>253.この数は365/2よりかなり大きい.

===================================

【Q2】客の中のふたりが同じ誕生日になる確率が50%を超えるには何人招けばよいか?

(A2)このクイズは数多くの本で取り扱われた有名なものである.d=365として,1番目の人と2番目の人が異なる誕生日である確率は1−1/dである.また,3番目の人が1番と2番の人と誕生日が異なる確率は,2番目の人は1番目の人と異なる日に生まれたとして,1−2/dである.

 したがって,n人全員が異なる誕生日である確率pnは,

  pn=(1−1/d)×(1−2/d)×・・・×(1−(n−1)/d)

となる.求めたい確率pは少なくとも2人同じ誕生日の人がいる確率であるから,

  p=1−pn>0.5

よりn=23.

===================================

【3】ハルモスの概算公式

 電卓を使ったとしても,[2]の計算はわずらわしいので,概算方法を示しておく.

 このクイズでは2人が同じ誕生日である確率は1/365と小さいけれども,30人もいれば30人の中から2人を選び出す組合せ数(30,2)は,30×29/2=435通りもあることである.これであれば,同じ誕生日に生まれたペア数の平均値は435/365となるから,一組以上のペアができると期待できるのである.一般に,1年はd日とし,構成員をn人とするとペア数の期待値はn(n−1)/2dになっている.

 このことから

  n(n−1)/2>365 → n>28

としたいところであるが,実際には(A1)で述べたように,

  n(n−1)/2>253 → n>23

でよく,23人の中から2人を選び出す組合せ数は

  23×22/2=253

通りあるのである.

 以上のことから,

  n(n−1)/2>log(0.5)/log(1−1/365)

          〜−365log(0.5)

と近似する.左辺の2次式もn^2/2と近似すると,

  n^2>−2log(0.5)×365

  n>(−2log(0.5))^1/2×(365)^1/2

  n>1.17741×(365)^1/2〜1.18×(365)^1/2

 ところで,

  pn=(1−1/d)×(1−2/d)×・・・×(1−(n−1)/d)

において,nがdに比べて小さければ,テイラー展開より

  1−k/d〜exp(−k/d)

  Π(1−k/d)〜exp(−Σk/d)

Σk=n(n−1)/2であるから,

  p〜1−exp(−n(n−1)/2d)

となる.

 [3]の結果は

  p〜1−exp(−n(n−1)/2d)>0.5

として

  n(n−1)/2d>−log(0.5)

としたものに等しいというわけである.

===================================