生日悖論

生日悖論

生日悖論,指如果一個房間裡有23個或23個以上的人,那么至少有兩個人的生日相同的機率要大於50%。這就意味著在一個典型的標準國小班級(30人)中,存在兩人生日相同的可能性更高。對於60或者更多的人,這種機率要大於99%。從引起邏輯矛盾的角度來說生日悖論並不是一種悖論,從這個數學事實與一般直覺相牴觸的意義上,它才稱得上是一個悖論。大多數人會認為,23人中有2人生日相同的機率應該遠遠小於50%。計算與此相關的機率被稱為生日問題,在這個問題之後的數學理論已被用於設計著名的密碼攻擊方法:生日攻擊。

悖論內容

著名的生日悖論

23個人里有兩個生日相同的人的幾率有多大呢?

居然有50%

問題是這樣的: 如果一個房間裡有23個或23個以上的人,那么至少有兩個人的生日相同的機率要大於50%。這就意味著在一個典型的標準國小班級(30人)中,存在兩人生日相同的可能性更高。對於60或者更多的人,這種機率要大於99%。

不計特殊的年月,如閏二月。

先計算房間裡所有人的生日都不相同的機率,那么

第一個人的生日是 365選365

第二個人的生日是 365選364

第三個人的生日是 365選363

:

:

:

第n個人的生日是 365選365-(n-1)

所以所有人生日都不相同的機率是:

生日悖論 生日悖論

那么,n個人中有至少兩個人生日相同的機率就是:

生日悖論 生日悖論

所以當n=23的時候,機率為0.507

當n=100的時候,機率為0.999999692751072

對於已經確定的個人,生日不同的機率會發生變化。下面用 隨機變數計算:

令X[i,j]表示第i個人和第j個人生日不同的機率,則易知任意X[i,j]=364/365

令事件A表示n個人的生日都不相同

生日悖論 生日悖論

P(A)=

解P(A)<1/2,由對數可得:n>=23

相比之下,隨機變數也同樣的簡單易懂

,且計算起來要方便得多

理解悖論

理解生日悖論的關鍵在於領會相同生日的搭配可以是相當多的。如在前面所提到的例子,23個人可以產生23 × 22/2 = 253種不同的搭配,而這每一種搭配都有成功相等的可能。從這樣的角度看,在253種搭配中產生一對成功的配對也並不是那樣的不可思議。

換一個角度,如果你進入了一個有著22個人的房間,房間裡的人中會和你有相同生日的機率便不是50%了,而是變得非常低。原因是這時候只能產生22種不同的搭配。生日問題實際上是在問任何23個人中會有兩人生日相同的機率是多少。

悖論套用

生日悖論普遍的套用於檢測哈希函式:N-位長度的哈希表可能發生碰撞測試次數不是2^N次而是只有2^(N/2)次。這一結論被套用到破解cryptographic hash function的生日攻擊中。

生日問題所隱含的理論已經在[Schnabel 1938]名字叫做capture-recapture的統計試驗得到套用,來估計湖裡魚的數量。

悖論定義

悖論是指一種導致矛盾的命題。悖論(paradox)來自希臘語“para+dokein”,意思是“多想一想”。 如果承認它是真的,經過一系列正確的推理,卻又得出它是假的;如果承認它是假的,經過一系列正確的推理,卻又得出它是真的。

把集合分成兩類,凡是不以自身作為元素的集合稱為正常集,(例如,自然數集N本身不是一個自然數,因此N是正常集。)凡是以自身作為元素的集合稱為異常集。(例如,所有的非生物的集合F也是非生物,因此F是異常集。)

這樣,許多日常中常見的悖論(說謊者悖論,理髮師悖論,上帝悖論等)都可以歸入異常集之中了。

另外一種悖論是關於無限的,雖然我們基本上都能接受極限的理論,但是要把這個理論向那些不懂的人解釋還是十分困難的。

經典故事

(古希臘數學家芝諾(Zeno of Elea)的阿基里斯悖論)阿基里斯在賽跑中不可能追上起步稍微領先於他的烏龜,因為當他要到達烏龜出發的那一點,烏龜又向前爬動了。阿基里斯和烏龜的距離可以無限地縮小,但永遠追不上烏龜。

(古希臘數學家芝諾(Zeno of Elea)的二分法悖論)當一個物體行進一段距離到達D,它必須首先到達距離D的二分之一,然後是四分之一、八分之一、十六分之一、以至可以無窮地劃分下去。因此,這個物體永遠也到達不了D。

“1厘米線段內的點與太平洋面上的點一樣多”

康托爾(1845-1918)成功地證明了:一條直線上的點能夠和一個平面上的點一一對應,也能和空間中的點一一對應。由於無限,1厘米長的線段內的點,與太平洋面上的點,以及整個地球內部的點都“一樣多”。

盤點各博弈論

博弈論(Game Theory),有時也稱為對策論,或者賽局理論,是研究具有鬥爭或競爭性質現象的理論和方法,它是套用數學的一個分支,既是現代數學的一個新分支,也是運籌學的一個重要學科。

相關搜尋

熱門詞條

聯絡我們