生日问题

生日问题是一个有趣的数学现象，它探讨“需要多少人聚在一起，才能让其中至少有两人同一天生日的机率超过一半？”

关于新加坡及亚洲学校数学奥林匹克的题目，请见“谢丽尔的生日”。

答案令人意外，只需要23人。这个问题有时被称为“生日悖论”，不过这其实并不是真正的悖论，只是因为结果违反了一般人的直觉。大多数人会认为23人中两人同生日的机率应该远小于50%。

它衍生出的数学理论被用于设计一种名为“生日攻击”的密码破解方法。

解释

生日问题可理解成盲射打靶问题。首先计算：23人皆不同生日的概率是多少？可想像一间有23人进入的房间，这23人依次进入，每个进入的人的生日都与房里其他人的生日不同的概率依次是1、${\textstyle {\frac {364}{365}}}$、${\textstyle {\frac {363}{365}}}$、${\textstyle {\frac {362}{365}}}$、${\textstyle {\frac {361}{365}}}$等。先入房的人的生日皆不同的概率很高，前五个是1×${\textstyle {\frac {364}{365}}}$×${\textstyle {\frac {363}{365}}}$×${\textstyle {\frac {362}{365}}}$×${\textstyle {\frac {361}{365}}}$=97.3%；而最后入房的几人就完全不同，他们入房且找不到同生日者的概率是${\textstyle {\frac {345}{365}}}$、${\textstyle {\frac {344}{365}}}$、${\textstyle {\frac {343}{365}}}$。这种概率可看成对靶的盲射：靶有365格，其中17个左右黑格，其余白格。假设每枪必中靶并且分布符合几何概型的话，连射12枪左右任何一发都没有击中黑格的概率（投射于房间里的人生日皆不同）十分微小。

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

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

概率估计

假设有n个人在房内，如果要计算两人同生日的机率，在不考虑特殊因素如闰年、双胞胎的前提下，假设一年365日出生概率平均分布（现实的出生机率不是平均分布）。

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

${\displaystyle {\bar {p}}(n)=1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1-{\frac {n-1}{365}}\right)={\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdot {\frac {362}{365}}\cdots {\frac {365-n+1}{365}}}$

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

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

${\displaystyle {365! \over 365^{n}(365-n)!}}$

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

${\displaystyle p(n)=1-{\bar {p}}(n)=1-{365! \over 365^{n}(365-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%

比较p (n) = 任意两人同生日的概率；q (n) =和某人同生日的概率

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

${\displaystyle q(n+1)=1-\left({\frac {364}{365}}\right)^{n}}$

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

数学论证（非数字方法）

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

${\displaystyle \prod _{k=1}^{n-1}\left(1-{k \over 365}\right)}$

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

${\displaystyle {\sqrt[{n-1}]{\prod _{k=1}^{n-1}\left(1-{k \over 365}\right)}}<{1 \over n-1}\sum _{k=1}^{n-1}\left(1-{k \over 365}\right)}$

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

${\displaystyle \prod _{k=1}^{n-1}\left(1-{k \over 365}\right)<\left({1 \over n-1}\sum _{k=1}^{n-1}\left(1-{k \over 365}\right)\right)^{n-1}}$

${\displaystyle =\left(1-{n \over 730}\right)^{n-1}<\left(e^{-n/730}\right)^{n-1}=e^{-(n^{2}-n)/730}}$

如果仅当

${\displaystyle n^{2}-n>730\log _{e}2\cong 505.997\dots }$

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

在推导中，哈莫斯写道：

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

然而哈莫斯的推论只显示至少超过23人就能保证平等机会下的生日匹配。因为不知道给出的不等式有多强（严格、清晰），因此无法借此计算过程确定n＝22是否能让机率过半；相反，现在任何人都可用Microsoft Excel等个人电脑程式在几分钟内把整幅机率分布图画出来，对问题答案很快就有通盘掌握，一目了然。

泛化和逼近

用公式${\displaystyle p(n)\sim 1-1/\exp(n^{2}/(2N))}$（红线）与真实概率（黑线）的比较

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

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

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

${\displaystyle p(n)\sim 1-1/\exp(n^{2}/(2N))}$。

泛化

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

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

${\displaystyle p(n;d)={\begin{cases}1-\prod _{k=1}^{n-1}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}}}$

${\displaystyle p(n;d)\approx 1-e^{-(n(n-1))/2d}}$　　　　　　　　　　　　　

${\displaystyle n(p;d)\approx {\sqrt {2d\ln \left({1 \over 1-p}\right)}}+{1 \over 2}}$　　　　　　　　　　

${\displaystyle p(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}}$

反算问题

反算问题可能是：

对于确定的概率p…

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

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

这问题有如下逼近公式：

${\displaystyle n(p)\approx {\sqrt {2\cdot 365\ln \left({1 \over 1-p}\right)}}+{1 \over 2}}$。

举例

逼近			估计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	=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-位长度的哈希表可能发生碰撞测试次数不是2^N次而是只有2^N/2次，这结论用在破解密码学散列函数的生日攻击中。

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

不平衡概率

就像上面提到的，现实世界人口的生日并非平均分布，这种非均衡生日概率问题也已解决。^{[来源请求]}

近似匹配

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

${\displaystyle {\begin{aligned}p(n,k,m)&=1-{\frac {(m-nk-1)!}{m^{n-1}{\bigl (}m-n(k+1){\bigr )}!}}\end{aligned}}}$

能找到两个人生日相差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. 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）.

外部链接

• 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 （页面存档备份，存于互联网档案馆）