生日問題

维基百科,自由的百科全书
跳转至: 导航搜索

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

对此悖论的解释[编辑]

我们可以把生日悖论理解成一个盲射打靶的问题。对于一个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,根據鴿巢原理其概率為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}
该图片显示特定人数对应的2个人生日一样的概率

因为第二个人不能跟第一个人有相同的生日(概率是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−73)
350 1 − (3 × 10−131)
≥366 100%
比较 p(n) = 任意两个人生日相同概率 q(n) =和某人生日相同的概率

注意所有人都是随机选出的:作为对比,q(n)表示房间中 n个其他人中与特定人(比如你)有相同生日的概率:

 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给出了一种概念数学方法的解释,下面就是这种方法(尽管这个方法包含一定的误差)。 乘积

\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。 其中"loge"表示自然对数。这个数略微小于506,如果取n2n=506,我们就得到n=23。


在推导中,Halmos写道:

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

然而Halmos的推导只显示至少超過23人就能保证平等机会下的生日匹配。因为我们不知道给出的不等式有多強(嚴格、清晰),因此從這個計算過程中無法確定當n=22時是否就能讓機率超過0.5。相反的,當代任何人都可以運用個人電腦程式如 Microsoft Excel,幾分鐘就可以把整個機率分布圖形畫出來,對問題答案很快就有個通盤的掌握,一目了然。

泛化和逼近[编辑]

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

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

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

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

N=365的结果[编辑]

050329-birthday2.png

泛化[编辑]

下面我们泛化生日问题: 给定从符合离散均匀分布的区间[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\le 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}          
q(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.11694
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)
...      ...

应用[编辑]

生日悖论普遍的应用于检测哈希函数:N-长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解密码学散列函数生日攻击中。

生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用,来估计湖里鱼的数量。

不平衡概率[编辑]

就像上面提到的,真实世界的人口出生日期并不是平均分布的。这种非均衡生日概率问题也已经被解决。[Klamkin 1967]

近似匹配[编辑]

此问题另外一个范化就是求得要在随机选取多少人中才能找到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

外部链接[编辑]