Mixing
生日問題
 | 本条目需要編修，以確保文法、用詞、语气、格式、標點等使用恰当。（2018年4月） |
關於新加坡及亞洲學校數學奧林匹克的題目，請見“謝麗爾的生日”。生日問題是指，如果在一个房间要多少人，則两个人的生日相同的概率要大于50%? 答案是23人。
这就意味着在一个典型的标准小学班级（30人）中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题，在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。
目录
1 对此悖论的解释
2 概率估计
3 数学论证（非数字方法）
4 泛化和逼近
4.1 泛化
5 反算问题
5.1 举例
6 经验性测试
7 应用
8 不平衡概率
9 近似匹配
10 参考
11 相关条目
12 參考文獻
13 外部链接
对此悖论的解释
可以把生日悖论理解成一个盲射打靶的问题。对于一个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枪左右任何一发都没有击中黑格的概率（投射于房间里的人生日都两两不同）是多少呢？想必大家立即会感觉到这个概率十分微小。
理解生日悖论的关键，在于考虑上述“依次进入房间”模型中最后几个进入房间的人“全部都没碰到相同生日的人”概率有多大这件事情。
简而言之，大多数人之所以会认为23人中有2人生日相同的概率应该远远小于50%，是因为将问题理解为“其他22人与你的生日相同的概率”，而非问题本意“23人之中两两之间存在生日相同”。如果考虑到这一点，直觉上会将原来的概率乘以23（注意：此算法并不正确），则会意识到概率很大了。
概率估计
假設有n個人在同一房間內，如果要計算有兩個人在同一日出生的機率，在不考慮特殊因素的前提下，例如閏年、雙胞胎，假設一年365日出生概率是平均分佈的（現實生活中，出生機率不是平均分佈的）。
計算概率的方法是，首先找出p（n）表示n個人中，每個人的生日日期都不同的概率。假如n > 365，根據鴿巢原理其概率為0，假设n ≤ 365，则概率为
- p¯(n)=1⋅(1−1365)⋅(1−2365)⋯(1−n−1365)=365365⋅364365⋅363365⋅362365⋯365−n+1365{displaystyle {bar {p}}(n)=1cdot 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!365n(365−n)!{displaystyle {365! over 365^{n}(365-n)!}}
p(n）表示n个人中至少2人生日相同的概率
- p(n)=1−p¯(n)=1−365!365n(365−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个人，當中与特定人（比如你）有相同生日的概率：
- q(n+1)=1−(364365)n{displaystyle q(n+1)=1-left({frac {364}{365}}right)^{n}}
当n = 22时概率只有大约0.059，约高于十七分之一。如果n个人中有50％概率存在某人跟你有相同生日，n至少要达到253。注意这个数字大大高于365/2 = 182.5；究其原因是因为房间内可能有些人生日相同。
数学论证（非数字方法）
在保羅·哈爾莫斯的自传中，他认为生日悖论仅通过数值上的计算来解释是一种悲哀。为此，哈爾莫斯给出了一种概念数学方法的解释，下面就是这种方法（尽管这个方法包含一定的误差）。乘积
- ∏k=1n−1(1−k365){displaystyle prod _{k=1}^{n-1}left(1-{k over 365}right)}
等于1－p（n），因此关注第一个n，欲使乘积小于1/2。由平均数不等式可以得知：
- ∏k=1n−1(1−k365)n−1<1n−1∑k=1n−1(1−k365){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)}
![sqrt[n-1]{prod_{k=1}^{n-1}left(1-{k over 365}right)}<br />
<{1 over n-1}sum_{k=1}^{n-1}left(1-{k over 365}right)](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4444729a7dc76c1b0240a69bea185b4f965fb68)
再利用已知的1到n－1所有整数和等于n（n－1）/2,然后利用不等式1－x < e−x，可以得到：
- ∏k=1n−1(1−k365)<(1n−1∑k=1n−1(1−k365))n−1{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}}
- =(1−n730)n−1<(e−n/730)n−1=e−(n2−n)/730{displaystyle =left(1-{n over 730}right)^{n-1}<left(e^{-n/730}right)^{n-1}=e^{-(n^{2}-n)/730}}
如果仅当
- n2−n>730loge2≅505.997…{displaystyle n^{2}-n>730log _{e}2cong 505.997dots }
最后一个表达式的值会小于0.5。其中"loge"表示自然对数。这个数略微小于506，如果取n2－n=506，就得到n＝23。
在推导中，哈爾莫斯写道：
.mw-parser-output .templatequote{margin-top:0;overflow:hidden}.mw-parser-output .templatequote .templatequotecite{line-height:1em;text-align:left;padding-left:2em;margin-top:0}.mw-parser-output .templatequote .templatequotecite cite{font-size:small}
这个推导是基于一些数学系学生必须掌握的重要工具。生日问题曾经是一个绝妙的例子，用来演示纯思维是如何胜过机械计算：一两分钟就可以写出这些不等式，而乘法运算则需要更多时间，并更易出错，无论使用的工具是一只铅笔还是一台老式电脑。计算器不能提供的是理解力，或数学才能，或产生更高级、普适化理论的坚实基础。[1]
然而哈爾莫斯的推导只显示至少超過23人就能保证平等机会下的生日匹配。因为不知道给出的不等式有多強（嚴格、清晰），因此從這個計算過程中無法確定當n＝22時是否就能讓機率超過0.5。相反的，當代任何人都可以運用個人電腦程式如Microsoft Excel，幾分鐘就可以把整個機率分布圖形畫出來，對問題答案很快就有個通盤的掌握，一目了然。
泛化和逼近
使用公式p(n)∼1−1/exp(n2/(2N)){displaystyle p(n)sim 1-1/exp(n^{2}/(2N))}
（紅綫）與真實概率（黑綫）的比較生日悖论可以推广一下：假设有n个人，每一个人都随机地从N个特定的数中选择出来一个数（N可能是365或者其他的大于0的整数）。
p（n）表示有两个人选择了同样的数字，这个概率有多大?
下面的逼近公式可以回答这个问题
p(n)∼1−1/exp(n2/(2N)){displaystyle p(n)sim 1-1/exp(n^{2}/(2N))}
泛化
下面泛化生日问题：给定从符合离散均匀分布的区间[1,d]随机取出n个整数，至少2个数字相同的概率p（n;d）有多大?
类似的结果可以根据上面的推导得出。
- p(n;d)={1−∏k=1n−1(1−kd)n≤d1n>d{displaystyle p(n;d)={begin{cases}1-prod _{k=1}^{n-1}left(1-{k over d}right)&nleq d\1&n>dend{cases}}}
p(n;d)≈1−e−(n(n−1))/2d{displaystyle p(n;d)approx 1-e^{-(n(n-1))/2d}}
n(p;d)≈2dln(11−p)+12{displaystyle n(p;d)approx {sqrt {2dln left({1 over 1-p}right)}}+{1 over 2}}- q(n;d)=1−(d−1d)n{displaystyle q(n;d)=1-left({frac {d-1}{d}}right)^{n}}
反算问题
反算问题可能是：
- 对于确定的概率p ...
- ...找出最大的n（p）满足所有的概率p（n）都小于给出的p，或者
- ...找出最小的n（p）满足所有的概率p（n）都大于给定的p。
对这个问题有如下逼近公式：
n(p)≈2⋅365ln(11−p)+12{displaystyle n(p)approx {sqrt {2cdot 365ln 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模拟, 其中A列表示人数,B列表示人数对应的生日相同的概率.
| A | B | |
|---|---|---|
| 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(即人数)时，你可以看到概率结果开始大于50%.
应用
生日悖论普遍的应用于检测哈希函数：N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解密码学散列函数的生日攻击中。
生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用，来估计湖里鱼的数量。
不平衡概率
就像上面提到的，真实世界的人口出生日期并不是平均分布的。这种非均衡生日概率问题也已经被解决。[來源請求]
近似匹配
此问题的另外一个泛化是求在n个人中有两个人的生日同在k日历天内的概率。假设有m个同等可能的出生日。[2]
- p(n,k,m)=1−(m−nk−1)!mn−1(m−n(k+1))!{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个人，找到两个人生日相差一周以内的概率就会超过50%。[2]
参考
- 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.02.1 M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858
外部链接
- 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
Comments
Post a Comment