生日問題

數學問題

生日問題是問最少需要多少人,當中兩人同一天生日的機率才會過半,答案是23人。這問題有時也稱生日悖論,但从引起逻辑矛盾的角度来说生日問題并非悖论,它稱作悖論只因这事实与一般直觉相抵触而已。大多数人会认为23人中兩人同生日的概率应该远小于一半。计算与此相关的概率称为生日问题,在这个问题之后的数学理论已用于设计著名的密码攻击方法:生日攻击

解释

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

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

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

概率估计

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

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

 
 
该图片显示特定人数对应的2个人生日一样的概率

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

 

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

 

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

n是23時概率约0.507。其他人數的概率用上面算法可得出:

n pn
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%
 
比较p (n) = 任意两人同生日的概率;q (n) =和某人同生日的概率

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

 

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

数学论证(非数字方法)

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

 

等于1-pn),因此关注第一个n,欲使乘积小于1/2。由平均数不等式可知:

 

再用已知的1到n-1所有整数和等于nn-1)/2,然后用不等式1-x < e−x,可得到:

 
 

如果仅当

 

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

在推导中,哈莫斯写道:

这推論是基于数学系学生必须掌握的重要工具。生日问题曾是用来演示纯思维如何胜过机械计算的绝妙例子:这些不等式一两分钟就写得出,但乘法运算就要更多时间且更易出错,无论使用的工具是铅笔还是老式电脑。计算器不能提供的是理解力、数学才能、或产生更高级、普适化理论的坚实基础。[1]

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

泛化和逼近

 
用公式 (紅綫)與真實概率(黑綫)的比較

生日問題可以推广一下:假设有n人,每人都随机从N个特定的数中选一个数出来(N可能是365或其他正整数)。

pn)表示有两个人选择了同样的数字,这概率多大?

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

 

泛化

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

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

 
              
           
 

反算问题

反算问题可能是:

对于确定的概率p
…找出最大的np)满足所有的概率pn)都小于给出的p,或者
…找出最小的np)满足所有的概率pn)都大于指定的p

这问题有如下逼近公式:

 

举例

逼近   估计N =365
p   n推广 n<N =365   n pn↓)  n pn↑)
0.01  (0.14178 √N)+0.5  3.20864 3 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)的统计试验得到应用,来估计湖的鱼数。

不平衡概率

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

近似匹配

此问题的另外一个泛化是求在n人中有两人的生日同在k日历天内的概率。假设有m个同等可能的生日。[2]

 

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

k n
for m = 365
0 23
1 14
2 11
3 9
4 8
5 8
6 7
7 7

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

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

星期二男孩問題:一個兩孩家庭有一個男孩,他是星期二出生的,那麼另一個孩子也是男孩的機率是多少?答:13/27[3]

参考

  • 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页。这一论文证明了当生日按照平均分布,两个生日相同的概率最小。

相关条目

參考文獻

  1. ^ 原文:The reasoning is based on important tools that all students of mathematics should have ready access to. The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What calculators do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories
  2. ^ 2.0 2.1 M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858
  3. ^ Jesper Juul. Tuesday Changes Everything (a Mathematical Puzzle). The Ludologist. [2022-05-01]. (原始内容存档于2022-01-24). 

外部链接