博弈论

生日悖论

2018-04-25 22:22:04  浏览:55  来源:投融网
解释

理解生日悖论的关键在于领会相同生日的搭配可以是相当多的。如23个人可以产生C= 23 × 22/2 = 253 种不同的搭配,而这每一种搭配都有成功相等的可能。从这样的角度看,在253种搭配中产生一对成功的配对也并不是那样的不可思议。

换一个角度,如果你进入了一个有着22个人的房间,房间里的人中会和你有相同生日的概率便不是五十五十了,而是变得非常低。原因是这时候只能产生22种不同的搭配。生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少。

计算

不计特殊的年月,如闰二月。先计算房间里所有人的生日都不相同的概率,那么
第一个人的生日是 365选365
第二个人的生日是 365选364
第三个人的生日是 365选363
:
:
:
第n个人的生日是 365选365-
所以所有人生日都不相同的概率是:
× × ×× ... ×
那么,n个人中有至少两个人生日相同的概率就是:
1-× × ×× ... ×
所以当n=23的时候,概率为0.507
当n=100的时候,概率为0.9999996

测试

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

days := 365;
numPeople := 1;
prob := 0.0;
while prob < 0.5 begin
numPeople := numPeople + 1;
prob := 1 - * ) / days);
print "Number of people: " + numPeople;
print "Prob. of same birthday: " + prob;

延伸

此问题另外一个范化就是求得要在随机选取多少人中才能找到2个人生日相同,相差1天,2天等的概率大于50% 。这是个更难的问题需要用到容斥原理。结果正像在标准生日问题中那样令人吃惊:

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

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

应用

生日悖论普遍的应用于检测哈希函数:N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解cryptographic hash function的生日攻击中。生日问题所隐含的理论已经在[Schnabel 1938]名字叫做capture-recapture的统计试验得到应用,来估计湖里鱼的数量。



    投融网(www.ipo.hk),创建于2011年,十年如一日,专注专业:企业投融资、IPO上市咨询辅助、定增、供股、发债、并购、重组、买卖壳资源、财经公关等业务,一站式金融机构及业务对接平台。

    投融资俱乐部,入驻120万+ 机构会员,会员可发布及对接投融资需求、筛选优质项目、企业上市辅导、兼并收购等投行业务信息,在线结识更多人脉,构建投融资与上市服务生态圈。

    欢迎各类机构洽谈合作。

邮箱:service@ipo.hk
电话:0755-33572246



发表评论
0评