生日問題

維基百科,自由的百科全書
(已重新導向自 生日悖論)
前往: 導覽搜尋

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

對此悖論的解釋[編輯]

我們可以把生日悖論理解成一個盲射打靶的問題。對於一個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槍左右任何一發都沒有擊中黑格的機率(投射於房間里的人生日都兩兩不同)是多少呢?想必大家立即會感覺到這個機率十分微小。

因此,理解生日悖論的關鍵,在於考慮上述「依次進入房間」模型中最後幾個進入房間的人「全部都沒碰到相同生日的人」機率有多大這件事情。

機率估計[編輯]

假設有n個人在同一房間內,如果要計算有兩個人在同一日出生的機率,在不考慮特殊因素的前提下,例如閏年雙胞胎,假設一年365日出生機率是平均分佈的(現實生活中,出生機率不是平均分佈的)。

計算機率的方法是,首先找出pn表示n個人中,每個人的生日日期都不同的機率。假如n > 365,根據鴿巢原理其機率為0,假設n ≤ 365,則機率為

\bar p (n) = 1 \cdot \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! \over 365^n (365-n)! }

p(n)表示n個人中至少2人生日相同的機率

 p (n) = 1 - \bar p (n)=1 - { 365! \over 365^n (365-n)! }

n≤365,根據鴿巢原理,n大於365時機率為1。

n=23發生的機率大約是0.507。其他數字的機率用上面的演算法可以近似的得出來:

n pn
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) =和某人生日相同的機率

注意所有人都是隨機選出的:作為對比,qn)表示房間中n個其他人中與特定人(比如你)有相同生日的機率:

 q (n) = 1- \left( \frac{364}{365} \right)^n

n = 22時機率只有大約0.059,約高於十七分之一。如果n個人中有50%機率存在某人跟有相同生日,n至少要達到253。注意這個數字大大高於365/2 = 182.5:究其原因是因為房間內可能有些人生日相同。

數學論證(非數字方法)[編輯]

Paul Halmos的自傳中,他認為生日悖論僅通過數值上的計算來解釋是一種悲哀。為此,Paul Halmos給出了一種概念數學方法的解釋,下面就是這種方法(儘管這個方法包含一定的誤差)。乘積

\prod_{k=1}^{n-1}\left(1-{k \over 365}\right)

等於1-pn),因此我們關注第一個n,欲使乘積小於1/2。由平均數不等式可以得知:

\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)

再利用已知的1到n-1所有整數和等於nn-1)/2,然後利用不等式1-x < e−x,我們可以得到:

\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}
=\left(1-{n \over 730}\right)^{n-1}<\left(e^{-n/730}\right)^{n-1}=e^{-(n^2-n)/730}

如果僅當

n^2-n>730\log_e 2\cong 505.997\dots

最後一個表達式的值會小於0.5。其中"loge"表示自然對數。這個數略微小於506,如果取n2n=506,我們就得到n=23。

在推導中,Halmos寫道:

這個推導是基於一些數學系學生必須掌握的重要工具。生日問題曾經是一個絕妙的例子,用來演示純思維是如何勝過機械計算:一兩分鐘就可以寫出這些不等式,而乘法運算則需要更多時間,並更易出錯,無論使用的工具是一隻鉛筆還是一台老式電腦。計算器不能提供的是理解力,或數學才能,或產生更高級、普適化理論的堅實基礎。[1]

然而Halmos的推導只顯示至少超過23人就能保證平等機會下的生日匹配。因為我們不知道給出的不等式有多強(嚴格、清晰),因此從這個計算過程中無法確定當n=22時是否就能讓機率超過0.5。相反的,當代任何人都可以運用個人電腦程式如Microsoft Excel,幾分鐘就可以把整個機率分布圖形畫出來,對問題答案很快就有個通盤的掌握,一目了然。

泛化和逼近[編輯]

生日悖論可以推廣一下:假設有n個人,每一個人都隨機地從N個特定的數中選擇出來一個數(N可能是365或者其他的大於0的整數)。

pn)表示有兩個人選擇了同樣的數字,這個機率有多大?

下面的逼近公式可以回答這個問題

p (n)\sim 1-1/\exp(n^2/(2N))。,

N=365的結果[編輯]

050329-birthday2.png

泛化[編輯]

下面我們泛化生日問題:給定從符合離散均勻分布的區間[1,d]隨機取出n個整數,至少2個數字相同的機率pn;d)有多大?

類似的結果可以根據上面的推導得出。

p(n;d) = \begin{cases} 1-\prod_{k=1}^{n-1}\left(1-{k \over d}\right) & n\le d \\ 1 & n > d \end{cases}
p(n;d) \approx 1 - e^{-(n(n-1))/2d}             
n(p;d)\approx \sqrt{2d\ln\left({1 \over 1-p}\right)}+{1 \over 2}          
q(n;d) = 1 - \left( \frac{d-1}{d} \right)^n

反算問題[編輯]

反算問題可能是:

對於確定的機率p ...
...找出最大的np)滿足所有的機率pn)都小於給出的p,或者
...找出最小的np)滿足所有的機率pn)都大於給定的p

對這個問題有如下逼近公式:

n (p)\approx \sqrt{2\cdot 365\ln\left({1 \over 1-p}\right)}+{1 \over 2}

舉例[編輯]

逼近   估計N =365
p   n推廣 n<N =365   n pn↓)  n pn↑)
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模擬

1 = 1-PERMUT(365,A1)/POWER(365,A1)
=A1+1 = 1-PERMUT(365,A2)/POWER(365,A2)
=A2+1 = 1-PERMUT(365,A3)/POWER(365,A3)
...      ...

應用[編輯]

生日悖論普遍的應用於檢測哈希函數N-長度的哈希表可能發生碰撞測試次數不是2N次而是只有2N/2次。這一結論被應用到破解密碼學散列函數生日攻擊中。

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

不平衡機率[編輯]

就像上面提到的,真實世界的人口出生日期並不是平均分布的。這種非均衡生日機率問題也已經被解決。[Klamkin 1967]

近似匹配[編輯]

此問題另外一個范化就是求得要在隨機選取多少人中才能找到2個人生日相同,相差1天,2天等的機率大於50% 。這是個更難的問題需要用到容斥原理。結果(假設生日依然按照平均分布)正像在標準生日問題中那樣令人吃驚:

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

只需要隨機抽取6個人,找到兩個人生日相差一周以內的機率就會超過50%。

參考[編輯]

  • 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頁。這一論文證明了當生日按照平均分布,兩個生日相同的機率最小。

相關條目[編輯]

參考文獻[編輯]

  1. ^ 原文: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

外部連結[編輯]