生日悖论发表评论(0) 编辑词条

生日悖论（Birthday paradox）

什么是生日悖论编辑本段 回目录

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

生日悖论的理解编辑本段 回目录

　　理解生日悖论的关键在于领会相同生日的搭配可以是相当多的。如在前面所提到的例子，23个人可以产生 $C(23,2)= 23\times \frac{22}{2}=253$ 种不同的搭配，而这每一种搭配都有成功相等的可能。从这样的角度看，在253种搭配中产生一对成功的配对也并不是那样的不可思议。

　　换一个角度，如果你进入了一个有着22个人的房间，房间里的人中会和你有相同生日的概率便不是50：50了，而是变得非常低。原因是这时候只能产生22种不同的搭配。生日问题实际上是在问任何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{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个人中至少2人生日相同的概率:

　　 $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个其他人中与特定人（比如你）有相同生日的概率：

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

　　当n = 22时概率只有大约0.059,约高于十七分之一。如果n个人中有50％概率存在某人跟你有相同生日， n至少要达到253 。注意这个数字大大高于 $\frac{365}{2}=182.5$ .究其原因是因为房间内可能有些人生日相同。==数学论证(非数字方法)==

数学论证(非数字方法)编辑本段 回目录

　　在 Paul Halmos 的自传中，他认为生日悖论仅通过数值上的计算来解释是一种悲哀。为此，Paul Halmos给出了一种概念数学方法的解释，下面就是这种方法（尽管这个方法包含一定的误差）。

　　乘积: $\prod_{k=1}^{n-1}\left(1k \over 365}\right)$

　　等于 1－p(n), 因此我们关注第一个n，使得乘积小于1/2，这样我们得到:

　　 $\sqrt[n-1]{\prod_{k=1}^{n-1}\left(1k \over 365}\right)}<{1 \over n-1}\sum_{k=1}^{n-1}\left(1k \over 365}\right)$

　　由平均数不等式得：

　　 $\prod_{k=1}^{n-1}\left(1k \over 365}\right) <\left({1 \over n-1}\sum_{k=1}^{n-1}\left(1k \over 365}\right)\right)^{n-1}$

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

　　(我们首先利用已知的1到n－1所有整数和等于 n(n－1)/2, 然后利用不等式不等式 1－x < e^−x.)

　　如果仅当:

　　 $n^2-n>730\log_e 2\cong 505.997\dots$

　　最后一个表达式的值会小于0.5。

　　其中"log_e"表示自然对数。这个数略微小于506，运气稍微好一点点就可以达到506，等于n²－n，我们就得到n＝23。

　　在推导中，Halmos写道:

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

　　然而Halmos的推导只显示至少需要23人保证平等机会下的生日匹配；因为我们不知道给出的不等式有多清晰，因此n＝22能够正切的可能也无法确定。

泛化和逼近编辑本段 回目录

生日悖论可以推广一下：假设有n 个,每一个人都随机地从1和特定的N个数中选择出来一个数(N可能是365或者其他的大于0的整数)。

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

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

$p(n)\sim 1-1/\exp(n^2/(2N)).\,$

N＝365的结果

泛化

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

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

$p(n;d) = \begin{cases} 1-\prod_{k=1}^{n-1}\left(1k \over d}\right) & n\le d \\ 1 & n > d \end{cases}$

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

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

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

反算问题编辑本段 回目录

反算问题可能是:

对于确定的概率 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)}.$

举例

逼近			估计N :=365
p	n 推广	n <N :=365	n↓	p(n↓)	n↑	p(n↑)
0.01	0.14178 √N	2.70864	2	0.00274	3	0.00820
0.05	0.32029 √N	6.11916	6	0.04046	7	0.05624
0.1	0.45904 √N	8.77002	8	0.07434	9	0.09462
0.2	0.66805 √N	12.76302	12	0.16702	13	0.19441
0.3	0.84460 √N	16.13607	16	0.28360	17	0.31501
0.5	1.17741 √N	22.49439	22	0.47570	23	0.50730
0.7	1.55176 √N	29.64625	29	0.68097	30	0.70632
0.8	1.79412 √N	34.27666	34	0.79532	35	0.81438
0.9	2.14597 √N	40.99862	40	0.89123	41	0.90315
0.95	2.44775 √N	46.76414	46	0.94825	47	0.95477
0.99	3.03485 √N	57.98081	57	0.99012	58	0.99166

注意:某些值被着色，说明逼近不总是正确。

经验性测试编辑本段 回目录

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

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;

应用编辑本段 回目录

　　生日悖论普遍的应用于检测哈希函数:N-位长度的哈希表可能发生碰撞测试次数不是2^N次而是只有2^N/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%。

参考文献编辑本段 回目录

原文：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.Zoe Emily Schnabel: "The estimation of the total fish population of a lake"（某湖中鱼类总量估计）, 美国数学月刊 45 (1938年), 348-352页

　　3.M. Klamkin，D. Newman: "Extensions of the birthday surprise"（生日惊喜的扩充）, Journal of Combinatorial Theory 3 (1967年),279-282页。

　　4.D. Blom: "a birthday problem"生日问题, 美国数学月刊 80 (1973年),1141-1142页。{这一论文证明了当生日按照平均分布，两个生日相同的概率最小。)

经管百科已经为您找到更多关于“生日悖论”的相关信息，点击查看>>

→如果您认为本词条还有待完善，请编辑词条

词条内容仅供参考，如果您需要解决具体问题
（尤其在法律、医学等领域），建议您咨询相关领域专业人士。本词条对我有帮助1

标签: 生日悖论平均数思维模拟生日攻击统计需要密码学散列函数哈希函数 Mark and recapture 容斥原理

收藏到:

同义词: 暂无同义词

关于本词条的评论 (共0条）发表评论>>

生日悖论 发表评论(0) 编辑词条

什么是生日悖论编辑本段回目录

生日悖论的理解编辑本段回目录

概率估计编辑本段回目录

数学论证(非数字方法)编辑本段回目录

泛化和逼近编辑本段回目录

N＝365的结果

泛化

反算问题 编辑本段回目录

举例

经验性测试 编辑本段回目录

应用 编辑本段回目录

近似匹配 编辑本段回目录

参考文献编辑本段回目录

附件列表

生日悖论发表评论(0) 编辑词条

反算问题编辑本段回目录

经验性测试编辑本段回目录

应用编辑本段回目录

近似匹配编辑本段回目录