生日问题

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

答案令人意外，只需要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，则概率为

{\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}}

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

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

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

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⁻⁷³）
350	1 −（3×10⁻¹³¹）
≥366	100%

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

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

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

数学论证（非数字方法）

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

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

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

{\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，可得到：

\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}

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

如果仅当

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等个人计算机程序在几分钟内把整幅概率分布图画出来，对问题答案很快就有通盘掌握，一目了然。

泛化和逼近

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

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

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

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

。

泛化

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

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

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}}

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

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

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

反算问题

反算问题可能是：

对于确定的概率p…

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

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

这问题有如下逼近公式：

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]

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

参考文献

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

[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

[abramson-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）.

[1]

[2]

[3]

解释