验证生日悖论.doc

《验证生日悖论.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、验证生日悖论问题引入：一．问题分析生日悖论：如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。在《著名的生日悖论 》中说道： 23个人里有两个生日相同的人的几率有多大呢？居然有50%。     悖论定义：悖论是指一种导致矛盾的命题。悖论(paradox)来自希腊

2、语“para+dokein”，意思是“多想一想”。 如果承认它是真的，经过一系列正确的推理，却又得出它是假的；如果承认它是假的，经过一系列正确的推理，却又得出它是真的。 生日攻击：生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。这种攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够长。生日攻击这个术语来自于所谓的生日问题，在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于1/2？这个问题的答案为23。二．问题求解不计特殊的年月，如闰二月。 先计算房间里所有人的生日都不相同的概率，那么 第一个人的生日

3、是 365选365 第二个人的生日是 365选364 第三个人的生日是 365选363 : : : 第n个人的生日是 365选365-(n-1) 所以所有人生日都不相同的概率是： (365/365)× (364/365) ×(363/365) ×(362/365)× ... ×【(365-n+1）/365】那么，n个人中有至少两个人生日相同的概率就是： 1-(365/365)× (364/365) ×(363/365) ×(362/365)× ... ×【(365-n+1）/365】 所以当n=23的时候，概率为0.507，约等于0.51。 当n=100的时候，概率为0.9999996，

4、趋近于1。对于已经确定的个人，生日不同的概率会发生变化。下面用随机变量计算：令X[i,j]表示第i个人和第j个人生日不同的概率，则易知任意X[i,j]=364/365令事件A表示n个人的生日都不相同P(A)=解P(A)<1/2，由对数可得：n>=23相比之下，随机变量也同样的简单易懂，且计算起来要方便得多。生日悖论-测试 生日悖论可以用计算机代码经验性模拟：days:=365; numPeople:=1; prob:=0.0; whileprob<0.5begin numPeople:=numPeople+1; prob:=1-((1-prob)*(days-(numPeople-1))

5、/days); print"Numberofpeople:"+numPeople; print"Prob.ofsamebirthday:"+prob;生日悖论-延伸 此问题另外一个范化就是求得要在随机选取多少人中才能找到2个人生日相同，相差1天，2天等的概率大于50％。这是个更难的问题需要用到容斥原理。结果(假设生日依然按照平均分布)正像在标准生日问题中那样令人吃惊：2人生日相差k天#需要的人数0                       23 1                       14 2                       11 3                

6、       9 4                       8 5                       7 7                       6 只需要随机抽取6个人，找到两个人生日相差一周以内的概率就会超过50%。生日悖论-应用 生日悖论普遍的应用于检测哈希函数:N-位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。这一结论被应用到破解cryptographichashfunction的生日攻击中。生日问题所隐含的理论已经在[Schnabel1938]名字叫做capture-recapture的统计试验得到应用，来估计湖里鱼的数量。三．结果分析

7、可见，我们的感觉有时候往往会欺骗我们。经过客观的推理运算，可以得到在23个人的一个团体中，至少有两人生日相同的概率大于50%，而当这个人数增大到100时，至少有两人生日相同的概率竟然接近于1。四．总结和心得体会通过这次的概率论论文写作，我们在实际生活中发现问题，然后用概率论的知识去解决他们。一方面，增强了我们发现问题的能力，另一方面，也增强了我们运用平时所学的理论知识去解决实际问题的能力。如果，我们只是一味的学习课本上的知识，依旧是