驗(yàn)證生日悖論

驗(yàn)證生日悖論問題引入：?jiǎn)栴}分析生日悖論：如果一個(gè)房間里有23個(gè)或23個(gè)以上的人，那么至少有兩個(gè)人的生日相同的概率要大于50%。這就意味著在一個(gè)典型的標(biāo)準(zhǔn)小學(xué)班級(jí)(30人)中，存在兩人生日相同的可能性更高。對(duì)于60或者更多的人，這種概率要大于99%。從引起邏輯矛盾的角度來(lái)說生日悖論并不是一種悖論，從這個(gè)數(shù)學(xué)事實(shí)與一般直覺相抵觸的意義上，它才稱得上是一個(gè)悖論。大多數(shù)人會(huì)認(rèn)為，23人中有2人生日相同的概率應(yīng)該遠(yuǎn)遠(yuǎn)小于50%。在《著名的生日悖論》中說道：23個(gè)人里有兩個(gè)生日相同的人的幾率有多大呢？居然有50%。 悖論定義：悖論是指一種導(dǎo)致矛盾的命題。悖論(paradox)來(lái)自希臘語(yǔ)“para+dokein”，意思是“多想一想”。如果承認(rèn)它是真的，經(jīng)過一系列正確的推理，卻又得出它是假的；如果承認(rèn)它是假的，經(jīng)過一系列正確的推理，卻又得出它是真的。生日攻擊：生日攻擊方法沒有利用Hash函數(shù)的結(jié)構(gòu)和任何代數(shù)弱性質(zhì)，它只依賴于消息摘要的長(zhǎng)度，即Hash值的長(zhǎng)度。這種攻擊對(duì)Hash函數(shù)提出了一個(gè)必要的安全條件，即消息摘要必須足夠長(zhǎng)。生日攻擊這個(gè)術(shù)語(yǔ)來(lái)自于所謂的生日問題，在一個(gè)教室中最少應(yīng)有多少學(xué)生才使得至少有兩個(gè)學(xué)生的生日在同一天的概率不小于1/2?這個(gè)問題的答案為23。問題求解不計(jì)特殊的年月，如閏二月。先計(jì)算房間里所有人的生日都不相同的概率，那么第一個(gè)人的生日是365選365第二個(gè)人的生日是365選364第三個(gè)人的生日是365選363第n個(gè)人的生日是365選365-(n-1)所以所有人生日都不相同的概率是：(365/365)X(364/365)X(363/365)X(362/365)X...X【(365-n+1)/365】那么，n個(gè)人中有至少兩個(gè)人生日相同的概率就是： 1-(365/365)X(364/365)X(363/365)X(362/365)X...X【(365-n+1)/365】所以當(dāng)n=23的時(shí)候，概率為0.507，約等于0.51。當(dāng)n=100的時(shí)候，概率為0.9999996，趨近于1。對(duì)于已經(jīng)確定的個(gè)人，生日不同的概率會(huì)發(fā)生變化。下面用隨機(jī)變量計(jì)算：令X[i,j]表示第i個(gè)人和第j個(gè)人生日不同的概率，則易知任意X[i,j]=364/365令事件A表示n個(gè)人的生日都不相同“一1“ 、…nU"知調(diào)'P(A)==■=-解P(A)<1/2，由對(duì)數(shù)可得：n>=23相比之下，隨機(jī)變量也同樣的簡(jiǎn)單易懂，且計(jì)算起來(lái)要方便得多。生日悖論-測(cè)試生日障論可以用計(jì)算機(jī)代碼經(jīng)驗(yàn)性模擬：days:=365;numPeople:=1;prob:=0.0;whileprob<0.5beginnumPeople:=numPeople+1;prob:=1-((1-prob)*(days-(numPeopleT))/days);print"Numberofpeople:〃+numPeople;print"Prob.ofsamebirthday:〃+prob;生日悖論-延伸此問題另外一個(gè)范化就是求得要在隨機(jī)選取多少人中才能找到2個(gè)人生日相同，相差1天，2天等的概率大于50%。這是個(gè)更難的問題需要用到容斥原理。結(jié)果(假設(shè)生日依然按照平均分布)正像在標(biāo)準(zhǔn)生日問題中那樣令人吃驚：2人生日相差k天#需要的人數(shù)TOC\o"1-5"\h\z0 2314119877 6只需要隨機(jī)抽取6個(gè)人，找到兩個(gè)人生日相差一周以內(nèi)的概率就會(huì)超過50%。生日悖論-應(yīng)用生日障論普遍的應(yīng)用于檢測(cè)哈希函數(shù):N-位長(zhǎng)度的哈希表可能發(fā)生碰撞測(cè)試次數(shù)不是2N次而是只有2N/2次。這一結(jié)論被應(yīng)用到破解cryptographichashfunction的生日攻擊中。生日問題所隱含的理論已經(jīng)在［Schnabel1938］名字叫做capture-recapture的統(tǒng)計(jì)試驗(yàn)得到應(yīng)用，來(lái)估計(jì)湖里魚的數(shù)量。結(jié)果分析可見，我們的感覺有時(shí)候往往會(huì)欺騙我們。經(jīng)過客觀的推理運(yùn)算，可以得到在23個(gè)人的一個(gè)團(tuán)體中，至少有兩人生日相同的概率大于50%，而當(dāng)這個(gè)人數(shù)增大到100時(shí)，至少有兩人生日相同的概率竟然接近于1?？偨Y(jié)和心得體會(huì)通過這次的概率論論文寫作，我們?cè)趯?shí)際生活中發(fā)現(xiàn)問題，然后用概率論的知識(shí)去解決他們。一方面，增強(qiáng)了我們發(fā)現(xiàn)問題的能力，另一方面，也增強(qiáng)了我們運(yùn)用平時(shí)所學(xué)的理論知識(shí)去解決實(shí)際問題的能力。如果，我們只是一味的學(xué)習(xí)課本上的知識(shí)，依舊是沒有任何用處的。只有把這些知識(shí)，融會(huì)貫通，才能遇題解題。除此之外，我們?cè)趯W(xué)習(xí)概率論的過程中發(fā)現(xiàn)了很多類似的悖