生日问题
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
生日问题是问最少需要多少人,当中两人同一天生日的概率才会过半,答案是23人。这问题有时也称生日悖论,但从引起逻辑矛盾的角度来说生日问题并非悖论,它称作悖论只因这事实与一般直觉相抵触而已。大多数人会认为23人中两人同生日的概率应该远小于一半。计算与此相关的概率称为生日问题,在这个问题之后的数学理论已用于设计著名的密码攻击方法:生日攻击。
解释
[编辑]生日问题可理解成盲射打靶问题。首先计算: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,则概率为
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Birthday_Paradox.svg/290px-Birthday_Paradox.svg.png)
因为第二人不能跟第一人同生日(概率是364/365),第三人不能跟前两人同生日(概率是363/365),依此类推。用阶乘可写成如下形式
p(n)表示n个人中至少两人同生日的概率
n≤365,根据鸽巢原理,n大于365时概率为1。
n是23时概率约0.507。其他人数的概率用上面算法可得出:
n | p(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% |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Birthday_paradox.svg/290px-Birthday_paradox.svg.png)
注意所有人都是随机选出:作为对比,q(n)表示房间中有n+1人,当中与特定人(比如你)同生日的概率:
当n = 22时概率只有大约0.059,约高于十七分之一。如果n人中有50%概率存在某人跟你同生日,n至少要达到253。注意这数字大大高于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。
在推导中,哈莫斯写道:
这推论是基于数学系学生必须掌握的重要工具。生日问题曾是用来演示纯思维如何胜过机械计算的绝妙例子:这些不等式一两分钟就写得出,但乘法运算就要更多时间且更易出错,无论使用的工具是铅笔还是老式电脑。计算器不能提供的是理解力、数学才能、或产生更高级、普适化理论的坚实基础。[1]
然而哈莫斯的推论只显示至少超过23人就能保证平等机会下的生日匹配。因为不知道给出的不等式有多强(严格、清晰),因此无法借此计算过程确定n=22是否能让概率过半;相反,现在任何人都可用Microsoft Excel等个人计算机程序在几分钟内把整幅概率分布图画出来,对问题答案很快就有通盘掌握,一目了然。
泛化和逼近
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Birthday_paradox_approximation.svg/300px-Birthday_paradox_approximation.svg.png)
生日问题可以推广一下:假设有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.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-PERMUT(365,A1)/POWER(365,A1) | |
|
=A1+1 | =1-PERMUT(365,A2)/POWER(365,A2) |
|
=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 = 3650 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页。这一论文证明了当生日按照平均分布,两个生日相同的概率最小。
相关条目
[编辑]参考文献
[编辑]- ^ 原文: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.0 2.1 M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858
- ^ Jesper Juul. Tuesday Changes Everything (a Mathematical Puzzle). The Ludologist. [2022-05-01]. (原始内容存档于2022-01-24).
外部链接
[编辑]- 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 (页面存档备份,存于互联网档案馆)