生日问题是指，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级（30人）中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题，在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。

[micxp_threadbk] [micxp_title] 对此悖论的解释 概率估计 数学论证（非数字方法） 泛化和逼近 泛化 反算问题 经验性测试 应用 不平衡概率 近似匹配 参考 相关条目 参考文献 外部链接 [/micxp_title] [#] 我们可以把生日悖论理解成一个盲射打靶的问题。对于一个23人的房间，先考虑问题的补集：23人生日两两不同的概率是多少？为此，我们可以让23个人依次进入，那么每个人生日都与其他人不同的概率依次是1, 364/365, 363/365, 362/365, 361/365,等等。先进入房间的这些人生日两两不同的概率是很大的，比如说前面5个是1×364/365×363/365×362/365×361/365=97.3%。而对于最后进入房间的几个人情况就完全不同。最后几个人进入房间并且找不到同生日者的概率是... 345/365, 344/365, 343/365。我们可以把这种概率看成对一张靶的盲射：靶上有365个小格，其中有17个左右是黑格，其余是白格。假设每枪必中靶并且分布符合几何概型的话，那么连续射12枪左右任何一发都没有击中黑格的概率（投射于房间里的人生日都两两不同）是多少呢？想必大家立即会感觉到这个概率十分微小。 因此，理解生日悖论的关键，在于考虑上述“依次进入房间”模型中最后几个进入房间的人“全部都没碰到相同生日的人”概率有多大这件事情。 [##] 假设有n个人在同一房间内，如果要计算有两个人在同一日出生的概率，在不考虑特殊因素的前提下，例如闰年、双胞胎，假设一年365日出生概率是平均分布的（现实生活中，出生概率不是平均分布的）。 计算概率的方法是，首先找出p（n）表示n个人中，每个人的生日日期都不同的概率。假如n > 365，根据鸽巢原理其概率为1，假设n ≤ 365，则概率为

${\displaystyle \overline{p}(n)=1\cdot (1-\frac{1}{365})\cdot (1-\frac{2}{365})\cdots (1-\frac{n-1}{365})=\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 \frac{365!}{{365}^n(365-n)!}}$

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

${\displaystyle p(n)=1-\overline{p}(n)=1-\frac{365!}{{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个其他人中与特定人（比如你）有相同生日的概率：

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

当n = 22时概率只有大约0.059,约高于十七分之一。如果n个人中有50％概率存在某人跟你有相同生日，n至少要达到253。注意这个数字大大高于365/2 = 182.5:究其原因是因为房间内可能有些人生日相同。 [###] 在Paul Halmos的自传中，他认为生日悖论仅通过数值上的计算来解释是一种悲哀。为此，Paul Halmos给出了一种概念数学方法的解释，下面就是这种方法（尽管这个方法包含一定的误差）。乘积

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

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

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

如果仅当

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

最后一个表达式的值会小于0.5。其中"loge"表示自然对数。这个数略微小于506，如果取n2－n=506，我们就得到n＝23。 在推导中，Halmos写道：

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

然而Halmos的推导只显示至少超过23人就能保证平等机会下的生日匹配。因为我们不知道给出的不等式有多强（严格、清晰），因此从这个计算过程中无法确定当n＝22时是否就能让概率超过0.5。相反的，当代任何人都可以运用个人计算机程序如Microsoft Excel，几分钟就可以把整个概率分布图形画出来，对问题答案很快就有个通盘的掌握，一目了然。 [####] 生日悖论可以推广一下：假设有n个人，每一个人都随机地从N个特定的数中选择出来一个数（N可能是365或者其他的大于0的整数）。 p（n）表示有两个人选择了同样的数字，这个概率有多大? 下面的逼近公式可以回答这个问题

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

[#####] 下面我们泛化生日问题：给定从符合离散均匀分布的区间[1,d]随机取出n个整数，至少2个数字相同的概率p（n;d）有多大? 类似的结果可以根据上面的推导得出。

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

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

${\displaystyle q(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(\frac{1}{1-p}\right)}+\frac{1}{2}}$。

[#######] 生日悖论可以用计算机代码经验性模拟

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)
...      ...

[########] 生日悖论普遍的应用于检测哈希函数：N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解密码学散列函数的生日攻击中。 生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用，来估计湖里鱼的数量。 [#########] 就像上面提到的，真实世界的人口出生日期并不是平均分布的。这种非均衡生日概率问题也已经被解决。[来源请求] [##########] 此问题另外一个泛化就是求得要在随机选取多少人中才能找到2个人生日相同，相差1天，2天等的概率大于50％ 。这是个更难的问题需要用到容斥原理。结果（假设生日依然按照平均分布）正像在标准生日问题中那样令人吃惊：

2人生日相差k天	#需要的人数
0	23
1	14
2	11
3	9
4	8
5	7
7	6

只需要随机抽取6个人，找到两个人生日相差一周以内的概率就会超过50%。 [###########]

• 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

[##############]

• 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

分类：

• 概率论悖论
• 概率与统计
• 生日

隐藏分类：

• 自2015年12月连结格式不正确的条目
• 自2014年1月语调不适于博牛百科的条目
• 拒绝当选首页新条目推荐栏目的条目
• 有未列明来源语句的条目

[/micxp_threadbk]

生日问题是指，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级（30人）中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题，在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。

[micxp_threadbk] [micxp_title] 对此悖论的解释 概率估计 数学论证（非数字方法） 泛化和逼近 泛化 反算问题 经验性测试 应用 不平衡概率 近似匹配 参考 相关条目 参考文献 外部链接 [/micxp_title] [#] 我们可以把生日悖论理解成一个盲射打靶的问题。对于一个23人的房间，先考虑问题的补集：23人生日两两不同的概率是多少？为此，我们可以让23个人依次进入，那么每个人生日都与其他人不同的概率依次是1, 364/365, 363/365, 362/365, 361/365,等等。先进入房间的这些人生日两两不同的概率是很大的，比如说前面5个是1×364/365×363/365×362/365×361/365=97.3%。而对于最后进入房间的几个人情况就完全不同。最后几个人进入房间并且找不到同生日者的概率是... 345/365, 344/365, 343/365。我们可以把这种概率看成对一张靶的盲射：靶上有365个小格，其中有17个左右是黑格，其余是白格。假设每枪必中靶并且分布符合几何概型的话，那么连续射12枪左右任何一发都没有击中黑格的概率（投射于房间里的人生日都两两不同）是多少呢？想必大家立即会感觉到这个概率十分微小。 因此，理解生日悖论的关键，在于考虑上述“依次进入房间”模型中最后几个进入房间的人“全部都没碰到相同生日的人”概率有多大这件事情。 [##] 假设有n个人在同一房间内，如果要计算有两个人在同一日出生的概率，在不考虑特殊因素的前提下，例如闰年、双胞胎，假设一年365日出生概率是平均分布的（现实生活中，出生概率不是平均分布的）。 计算概率的方法是，首先找出p（n）表示n个人中，每个人的生日日期都不同的概率。假如n > 365，根据鸽巢原理其概率为1，假设n ≤ 365，则概率为

${\displaystyle \overline{p}(n)=1\cdot (1-\frac{1}{365})\cdot (1-\frac{2}{365})\cdots (1-\frac{n-1}{365})=\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 \frac{365!}{{365}^n(365-n)!}}$

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

${\displaystyle p(n)=1-\overline{p}(n)=1-\frac{365!}{{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个其他人中与特定人（比如你）有相同生日的概率：

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

当n = 22时概率只有大约0.059,约高于十七分之一。如果n个人中有50％概率存在某人跟你有相同生日，n至少要达到253。注意这个数字大大高于365/2 = 182.5:究其原因是因为房间内可能有些人生日相同。 [###] 在Paul Halmos的自传中，他认为生日悖论仅通过数值上的计算来解释是一种悲哀。为此，Paul Halmos给出了一种概念数学方法的解释，下面就是这种方法（尽管这个方法包含一定的误差）。乘积

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

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

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

如果仅当

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

最后一个表达式的值会小于0.5。其中"loge"表示自然对数。这个数略微小于506，如果取n2－n=506，我们就得到n＝23。 在推导中，Halmos写道：

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

然而Halmos的推导只显示至少超过23人就能保证平等机会下的生日匹配。因为我们不知道给出的不等式有多强（严格、清晰），因此从这个计算过程中无法确定当n＝22时是否就能让概率超过0.5。相反的，当代任何人都可以运用个人计算机程序如Microsoft Excel，几分钟就可以把整个概率分布图形画出来，对问题答案很快就有个通盘的掌握，一目了然。 [####] 生日悖论可以推广一下：假设有n个人，每一个人都随机地从N个特定的数中选择出来一个数（N可能是365或者其他的大于0的整数）。 p（n）表示有两个人选择了同样的数字，这个概率有多大? 下面的逼近公式可以回答这个问题

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

[#####] 下面我们泛化生日问题：给定从符合离散均匀分布的区间[1,d]随机取出n个整数，至少2个数字相同的概率p（n;d）有多大? 类似的结果可以根据上面的推导得出。

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

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

${\displaystyle q(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(\frac{1}{1-p}\right)}+\frac{1}{2}}$。

[#######] 生日悖论可以用计算机代码经验性模拟

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)
...      ...

[########] 生日悖论普遍的应用于检测哈希函数：N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解密码学散列函数的生日攻击中。 生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用，来估计湖里鱼的数量。 [#########] 就像上面提到的，真实世界的人口出生日期并不是平均分布的。这种非均衡生日概率问题也已经被解决。[来源请求] [##########] 此问题另外一个泛化就是求得要在随机选取多少人中才能找到2个人生日相同，相差1天，2天等的概率大于50％ 。这是个更难的问题需要用到容斥原理。结果（假设生日依然按照平均分布）正像在标准生日问题中那样令人吃惊：

2人生日相差k天	#需要的人数
0	23
1	14
2	11
3	9
4	8
5	7
7	6

只需要随机抽取6个人，找到两个人生日相差一周以内的概率就会超过50%。 [###########]

• 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

[##############]

• 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

分类：

• 概率论悖论
• 概率与统计
• 生日

隐藏分类：

• 自2015年12月连结格式不正确的条目
• 自2014年1月语调不适于博牛百科的条目
• 拒绝当选首页新条目推荐栏目的条目
• 有未列明来源语句的条目

[/micxp_threadbk]