生日問題

生日問題是一個機率論中的問題，它的敘述是：「需要多少人聚在一起，才能讓其中至少有兩人同一天生日的機率超過一半？」

答案是只需要23人。這個問題有時被稱為「生日悖論」，不過這其實並不是真正的悖论，只是因為結果違反了一般人的直覺。大多数人会认为23人中兩人同生日的機率應該遠小於50%。它衍生出的數學理論被用於設計一種名為「生日攻击」的密碼破解方法。

 解释 

生日問題可理解成盲射打靶问题。首先計算：23人皆不同生日的概率是多少？可想像一間有23人進入的房間，這23人依次進入，每個進入的人的生日都與房裏其他人的生日不同的概率依次是1、、、、等。先入房的人的生日皆不同的概率很高，前五个是1××××=97.3%；而最后入房的几人就完全不同，他們入房且找不到同生日者的概率是、、。这种概率可看成对靶的盲射：靶有365格，其中17个左右黑格，其余白格。假设每枪必中靶并且分布符合几何概型的话，连射12枪左右任何一发都没有击中黑格的概率（投射于房间里的人生日皆不同）十分微小。

理解生日問題的关键在于考虑上述“依次入房”模型中最后几个入房的人“全都没碰到同生日的人”概率多少。

简言之，大多数人之所以会认为23人中兩人同生日的概率应该远远小于50%，是因为将问题理解为“其他22人与你同生日的概率”，而非问题真諦“23人中两两之间存在生日相同”。如果有考虑这点，直觉上会将原来的概率乘以23（注意：此算法并不正确），则会意识到概率很大。

 概率估计 

假設有n個人在房內，如果要計算兩人同生日的機率，在不考慮特殊因素如閏年、雙胞胎的前提下，假設一年365日出生概率平均分佈（現實的出生機率不是平均分佈）。

計算概率的方法是，首先找出p（n）表示n人中，每人生日都不同的概率。假如n > 365，根據鴿巢原理其概率為0，假设n ≤ 365，则概率为

因为第二人不能跟第一人同生日（概率是364/365），第三人不能跟前两人同生日（概率是363/365），依此类推。用阶乘可写成如下形式

p(n）表示n个人中至少兩人同生日的概率

n≤365，根据鸽巢原理，n大于365时概率为1。

n是23時概率约0.507。其他人數的概率用上面算法可得出：
np（n）10  12%20  41%30  70%50  97%100  99.99996%200  99.9999999999999999999999999998%300  1 −（7×10−73）350  1 −（3×10−131）≥366  100%

注意所有人都是随机选出：作为对比，q(n)表示房间中有n+1人，當中与特定人（比如你）同生日的概率：



当n = 22时概率只有大约0.059，约高于十七分之一。如果n人中有50％概率存在某人跟你同生日，n至少要达到23。注意这数字大大低于365/2 = 182.5；究其原因是因为房间内可能有些人同生日。

 数学论证（非数字方法） 

保羅·哈莫斯在自传中认为生日問題只用计算数值来解释是种悲哀，所以给出了一种概念数学方法的解释（尽管这方法有一定的误差）：乘积

等于1－p（n），因此关注第一个n，欲使乘积小于1/2。由平均数不等式可知：

再用已知的1到n－1所有整数和等于n（n－1）/2，然后用不等式1－x < e−x，可得到：

如果仅当

最后一條表达式的值会小于0.5。其中loge表示自然对数，略小于506，如果取n2－n=506就得到n＝23。

在推导中，哈莫斯写道：

然而哈莫斯的推論只显示至少超過23人就能保证平等机会下的生日匹配。因为不知道给出的不等式有多強（嚴格、清晰），因此無法藉此計算過程確定n＝22是否能讓機率過半；相反，現在任何人都可用Microsoft Excel等個人電腦程式在幾分鐘內把整幅機率分佈圖畫出來，對問題答案很快就有通盤掌握，一目了然。

 泛化和逼近 
生日問題可以推广一下：假设有n人，每人都随机从N个特定的数中选一个数出来（N可能是365或其他正整数）。

p（n）表示有两个人选择了同样的数字，这概率多大?

下面的逼近公式可以回答这个问题

。

 泛化 
下面泛化生日问题：给定从符合离散均匀分布的区间[1,d]随机取出n个整数，至少2个数字相同的概率p（n;d）有多大?

类似的结果可以根据上面的推导得出。




 反算问题 

反算问题可能是：

对于确定的概率p…

…找出最大的n（p）满足所有的概率p（n）都小于给出的p，或者

…找出最小的n（p）满足所有的概率p（n）都大于指定的p。

这问题有如下逼近公式：

。

 举例 

 逼近　　估计N =365 p  　 n推广    n<N =365　 n↓  p（n↓） 　n↑p（n↑） 0.01  　（0.14178 √N）+0.5　   3.208643  0.00820  4  0.01636 0.05  　（0.32029 √N）+0.5　   6.61916 6  0.04046  7  0.05624 0.1  　（0.45904 √N）+0.5　   9.27002 9  0.09462  10  0.11695 0.2  　（0.66805 √N）+0.5　   13.26302 13  0.19441  14  0.22310 0.3  　（0.84460 √N）+0.5　  16.63607 16  0.28360  17  0.31501 0.5  　（1.17741 √N）+0.5　  22.99439 22  0.47570  23  0.50730 0.7 　（1.55176 √N）+0.5 30.14625 30 0.70632 31  0.73045　　　（正確值：n↓=29, n↑=30） 0.8  　（1.79412 √N）+0.5　  34.77666 34  0.79532  35  0.81438 0.9 　（2.14597 √N）+0.5 41.49862 41 0.90315 42  0.91403　　　（正確值：n↓=40, n↑=41） 0.95 　（2.44775 √N）+0.5 47.26414 47 0.95477 48  0.96060　　　（正確值：n↓=46, n↑=47） 0.99 　（3.03485 √N）+0.5 58.48081 58 0.99166 59  0.99299　　　（正確值：n↓=56, n↑=57）

注意：某些值有色，说明逼近不总是正确。

 经验性测试 

生日問題可以用计算机代码经验性模拟

days := 365;
numPeople := 1;
prob := 0.0;
while prob < 0.5 begin
    numPeople := numPeople + 1;
    prob := 1 -((1-prob)*(days-(numPeople-1)) / days);
    print "Number of people: " + numPeople;
    print "Prob. of same birthday: " + prob;
end;

生日問題也可以用Microsoft Excel Spreadsheet模拟
人数
人数对应的生日相同的概率
 1 
   1 
   =1-PERMUT(365,A1)/POWER(365,A1)
  2  
  =A1+1
  =1-PERMUT(365,A2)/POWER(365,A2)
  3  
   =A2+1
   =1-PERMUT(365,A3)/POWER(365,A3)

当行数达到23（即人数），可看到概率结果开始過半。

 应用 

生日問題普遍的应用于检测哈希函数：N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次，这结论用在破解密码学散列函数的生日攻击中。

生日问题隐含的理论已经在[Schnabel 1938]名字叫做捉放法（capture-recapture）的统计试验得到应用，来估计湖的鱼数。

 不平衡概率 

就像上面提到的，現实世界人口的生日并非平均分佈，这种非均衡生日概率问题也已解决。

 近似匹配 

此问题的另外一个泛化是求在人中有两人的生日同在日历天内的概率。假设有个同等可能的生日。M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858

能找到两个人生日相差天或更少的概率高于50%所需要的人数：

{| class="wikitable" style="text-align: center"
!  !! for 
|-
|0 || 23
|-
|1 || 14
|-
|2 || 11
|-
|3 || 9
|-
|4 || 8
|-
|5 || 8
|-
|6 || 7
|-
|7 || 7
|}

只須随机抽取7人，找到两人生日相差一周内的概率就会過半。

其它相關生日錯覺機率問題

星期二男孩問題：一個兩孩家庭有一個男孩，他是星期二出生的，那麼另一個孩子也是男孩的機率是多少？答：13/27

 参考 
 Zoe Emily Schnabel: "The estimation of the total fish population of a lake"（某湖中鱼类总量估计），美国数学月刊45（1938年）, 348-352页
 M. Klamkin，D. Newman: "Extensions of the birthday surprise"（生日惊喜的扩充）, Journal of Combinatorial Theory 3（1967年）,279-282页。
 D. Blom: "a birthday problem"生日问题，美国数学月刊80（1973年）,1141-1142页。这一论文证明了当生日按照平均分布，两个生日相同的概率最小。

 相关条目 
 概率论
 生日
 生日攻击
 哈希函数

 參考文獻 

 外部链接 
 http://www.efgh.com/math/birthday.htm 
 http://www.teamten.com/lawrence/puzzles/birthday_paradox.html 
 http://science.howstuffworks.com/question261.htm 
 http://mathworld.wolfram.com/BirthdayProblem.html 
 http://www.atriumtech.com/pongskorn/birthdayparadox/birthdayparadox.htm 

Category:概率论悖论
Sheng
Category:生日
Category:数学期望