機率名題二則漫談

　1│2│3　

首頁 | 搜尋

．原載於數學傳播第四卷第四期
．作者當時任教於交大運輸工程與管理學系

‧註釋

機率名題二則漫談

戴久永

生日問題
伯特朗選票問題
解答

機率論是討論各種偶發事件的發生及尋求其所遵循的法則的數學理論。關於機率論早期演進的情形，本刊曾有詳細敘述 ^註1 。近半世紀以來，機率論已由許多散佈孤立的小問題的研究發展成為一門相當具廣涵性和深度的數學分支，不但與其他許多數學分支交互影響，同時在各種應用科學諸如統計，作業研究，生物學，經濟學，和心理學的數學化中扮演重要角色。

第一本對機率論做系統性整理的書可能要算 W. Feller 的《An Introduction To Probability Theory and Its Application》 ^註2 。這是一本經典之作，至今仍有很高的可讀性及參考價值，是學習機率論不可或缺的參考書。在這類機率論導引的入門書中，有許多問題常被各書引用為例題，用來解說機率論上的概念，筆者稱之為「名題」，例如生日問題就是其中之一。但是大多數的情況是點到為止。本文特提出兩個題目，生日問題和伯特朗選票問題，進行稍微深入的討論，一方面希望會增進讀者對這些問題的認識，同時能提高研究機率論的興趣。

生日問題

提到生日有些人馬上就聯想到美味的生日蛋糕和開心的生日舞會。另外一些人卻認為自己的生日是「母難日」，為了自己的誕生，母親可真是受盡生產的苦楚。不過無論你是屬於那一派的人，對於自己的生日必然是牢記不忘的吧。現在我們就以這令人難忘的日子為話題來談一下數學上的生日問題。

最為人所熟知的古典生日問題是「至少要有多少人共聚一堂才會使有二人或二人以上為同日生的機率大於 $\frac{1}{2}$ ？」為了簡化問題，通常我們都是把二月二十九日忽略不計，並且假設其他 365天為相等可能的生日日期。本題的答案 23人也是相當有名。很多人對這答案感到驚訝，因為 23僅為 365的一小部份，而一般人直覺地認為 [183 $\approx\frac{1}{2}$ (365)] 似為較合理的數字。他們之所以感到驚異實在走出於誤解題意的緣故。他們心中所想的是同日生者問題：我至少要問多少人才會使找到與自己同日生者的機率大於 $\frac{1}{2}$ ？

同日生者問題也頗為人所知，只是不如以上所提生日問題著名，答案是 253。答案超過 183 是由於出生日期的抽樣是歸還抽樣而非不歸還抽樣，如果是由 365 個不同的生日的人中抽樣，則 183 為同日生者問題的正確答案。

於比較生日問題和同日生者問題時，我們發現在生日問題中，r 人有 $\frac{r(r-1)}{2}$ 個可能為生日相同的的機會。而在同日生者問題中，在我所問的 n 人中，我僅有 n 個機會可能找到一個或一個以上和我同日生的人。因此倘若要使這兩個問題有相同的成功機率，那麼顯然令 $n\approx\frac{r(r-1)}{2}$ 較為合理，因為如此方可使這兩個問題有相同的成功機率，例如，如果成功的機率為 $\frac{1}{2}$ ，即 r=23， $n=\frac{22(23)}{2}=253$ ，恰為正確的答案。另一方面，這兩問題的成功機率並非完全相等。在生日問題 r=23 時， $P(\mbox{{\fontfamily{cwM1}\fontseries{m}\selectfont \char 65}\hskip 0.0pt plus0... ...nus0.1pt{\fontfamily{cwM0}\fontseries{m}\selectfont \char 138}}) \approx 0.5073$ ，而同生日者問題，n=253， $P(\mbox{{\fontfamily{cwM1}\fontseries{m}\selectfont \char 65}\hskip 0.0pt plus0... ...nus0.1pt{\fontfamily{cwM0}\fontseries{m}\selectfont \char 138}}) \approx 0.5005$ 。

現在我們將上述二問題推廣化，令 N 為相同可能的生日天數，r 為生日問題中的人數，n 為同日生者問題中被詢及生日的人數，則對於生日問題來說，我們很容易求出 r 人生日均不相同的機率，至少有二人同生日的機率為取其餘集。

第一人的生日為 N 日中的任一日，第二人的生日與第一人不同，因此他的生日可能為所剩 N-1 天中的任一天，第三人的生日為 N-2 天中的一天……，第 r 人則為 N-r+1 天中的一天，因此 r 人均不同生日的可能為

$\begin{displaymath} N(N-1)(N-2)\cdots(N-r+1) \end{displaymath}$

(1)

而本題的樣本空間則為 N^r，因為 r 人中每人的生日均可能為 N 天中的任一天。因此

$\begin{displaymath} \begin{eqalign} P_R &= P(\mbox{{\fontfamily{cwM2}\fontseries... ...}) \\ &= 1-N(N-1)(N-2)\cdots\frac{(N-r+1)}{N^r} \end{eqalign}\end{displaymath}$

(2)

在同日生者問題中，我隨機選取的每一被詢問人與我的生日不同的機率為 $\frac{(N-1)}{N}=1-\frac{1}{N}$ 。若 n 人為獨立抽取，則無人與我生日相同的機率為 $(1-\frac{1}{N})^n$ ，即至少有一人與我生日相同的機率 P_S 為

$\begin{displaymath} P_S=1-(1-\frac{1}{N})^n \end{displaymath}$

(3)

我們希望 P_S 與 P_R 大約相等，然後將 n 寫成 r 的函數的形式。若 P_R=P_S 則

$\begin{displaymath} \frac{N(N-1)(N-2)\cdots(N-r+1)}{N^r}=(1-\frac{1}{N})^n \end{displaymath}$

(4)

左式分子的每一項用 N 除，得到

$\begin{displaymath} 1(1-\frac{1}{N})(1-\frac{2}{N})\cdots(1-\frac{r-1}{N})=(1-\frac{1}{N})^n \end{displaymath}$

(5)

將左式相等開來，右式也展開至第二項，得到

$\begin{displaymath} 1-(\frac{1}{N}+\frac{2}{N}+\cdots+\frac{r-1}{N})=1-\frac{n}{N}+\cdots \end{displaymath}$

(6)

比較左右二式，我們得到

$\begin{displaymath} n=1+2+\cdots+(r-1)=\frac{r(r-1)}{2} \end{displaymath}$

(7)

當 n 與 N 相較頗小時，這個結果部份證實我們早先所作對於相等機會數的說法。

關於生日問題，我想在此附帶再多談一點。

(1)表一為不同 r 值所對應至少有二人同生日的機率。

r	5	10	15	20	21	22	23
P_R	0.027	0.117	0.253	0.411	0.444	0.476	0.507
r	24	25	30	40	50	60
P_R	0.538	0.569	0.706	0.891	0.970	0.994

(2)我們學一個巧妙的方法來求無同生日的機率的近似值。因為 $e^{-x}=1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots$ ，當 x 很小峙，e^-x 不會比 1-x 大多少，因此當 x 很小時，我們可以採用 1-x 為 e^-x 了的近似值或以 e^-x 為 1-x 的近似值。

$\begin{eqnarray*} &&\frac{N(N-1)(N-2)\cdots(N-r+1)}{N^r}\\ &=&\frac{N}{N}\frac{... ...e^{-\frac{ 1+2+\cdots+(r-1)}{ N}}\\ &=&e^{-\frac{ r(r-1)}{ 2N}} \end{eqnarray*}$

當 r=23 時， $P(r \mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 65}\hskip 0.0pt plu... ... minus0.1pt{\fontfamily{cwM0}\fontseries{m}\selectfont \char 176}}) \approx 0.5$ 或令 $[\frac{r(r-1)]}{2(365)}]=-\log 0.5\approx 0.699$ ，可求得 r 值。

接下來，我們再來看一下生日問題的另一種推廣化的形式。在有 100 位同學相聚的同學會上，數學高手某甲三句不離本行，提到生日問題，進行一個實驗。在已知會中有二人或二人以上同日生的機率近乎 1 的情形下，他請會中每人由前向後報出自己的生日，倘若會中有人舉手表示與報出的生日相同，立即停止試驗。某甲願意與人打賭這個實驗必會在第 10 個人報出他的生日或之前就會停止，結果沒有人願意和他賭。（事實上甲獲勝的機率是 0.928，當然沒有人願意和他打賭了）。以下我們來討論一下這個生日問題。

設 n 和 k 為正整數，其中 $k\leq n$ ，P(n,k) 代表在 n 人的群體至少有二人生日相同，而其中一人在前 k 人中的機率。 P(n,n) 就是古典的生日問題。我們在前提到 P(100,10)=0.928。

現在我們來看一下如何求得 P(n,k)，在此我們仍然假設不計閏年二月二十九日，並且其他 365 天均為相同可能的生日日期。

樣本空間為 365ⁿ，n 維的數列，n=1,2,…,365。我們感興趣的事件為 n 維的前 k 維中至少有一維是重複的數列的集合。這集合的餘事件倒是相當容易計算。就是 n 維中前 k 維均不同的數列的集合，即如下所示

$\begin{displaymath} 365\cdot 364\cdots(365-k+1)(365-k)^{n-k} \end{displaymath}$

因此，

$\begin{displaymath} P(n,k)=1-\frac{365\cdot 364\cdots(365-k+1)(365-k)^{n-k}}{365^n} \end{displaymath}$

(8)

我們由前知古典生日問題的解答為 $Q_k=1-P(k\mbox{,}k)$ ，而 $P(n,k)=1-Q_k(1-\frac{k}{365})^{n-k}$ 。

在下表中 k(n) 為使 $P(n,k)\geq \frac{1}{2}$ 的最小 k 值。由古典生日問題的解答得知 n 至少要 23 才有 k(n) 存在，同時我們知道 $k(n+1)\leq k(n)$ ，因此表二始於 n=23。

n	23	24	25	26	27	28	29	31	33
k(n)	20	17	15	14	13	12	11	10	9
n	36	40	46	54	66	86	128	254
k(n)	8	7	6	5	4	3	2	1

表二的最後一行表示倘若你想與人打賭在 n 人中有人與你生日相同，則 n 必須至少要 254 人才會使這打賭對你有利。或許有人認為 n 似應為 $1+[\frac{365}{2}] = 183$ ，然而依據古典生日問題的解答，在有 183 人相聚的群體中，通常會有好些重複的生日，而非恰好人人生日不同。換句話說，想要找到 183 個不同生日的最小 n 值為 254 人。細心的讀者必定發現在同生日者問題中的答案 253 人與以上解法所得 254 人略有出入，這是由於牽涉計算上的使用近似值所致。接下來我們來研究一下 254 這個數值是如何得出的。

假設有任意 n 人聚於一室，令隨機變數 X_n 為表示在此 n 人中，不同生日的天數，則期望值 E(X) 應為若干？

解：通常這類求期望值的問題都是先決定 X_n 機率分配而後依據期望值的定義解之，在此，我們擬採用「以小數值試驗，然後看看是否能推測出期望值一般式」的方式試解本題。

首先我們來看一下 n=1,2,3,4 時 X_n 的機率分配情形。X_n 分配如表三所示：

我們僅以 P(X₃=2) 和 P(X₄=3) 來說明如何求得表中數值。

表三

隨機變數＼X值	1	2	3	4
X₁	1
X₂	$\frac{ 1}{ 365}$	$\frac{ 364}{ 365}$
X₃	$\frac{ 1}{ (365)^2}$	$\frac{ 3(364)}{ (365)^2}$	$\frac{ (364)(363)}{ (365)^2}$
X₄	$\frac{ 1}{ (365)^3}$	$\frac{ 7(364)}{ (364)^3}$	$\frac{ 6(364)(363)}{ (365)^3}$	$\frac{ (364)(363)(362)}{ (365)^3}$

當 n=3 時，有三種不同型式可得出二不同生日，即 (xxy,xyx,yxx)。

今以甲乙丙三人，其中甲乙的生日相同，丙的生日與前二人不同為例說明，在一年365天中，甲的生日可能是 365 天中任一天，乙與甲同日生，故只有一種可能（即甲的生日那天），丙的生日為其他 364 天中的任一天，因此

$\begin{displaymath} P(X_3=2)=3=\frac{(365)(1)(364)}{(365)^3}=\frac{3(364)}{(365)^2} \end{displaymath}$

，同理 n=4 有三不同生日有下列六種可能

(xxyz,xyxz,xyzx,yxzx,yxxz,yxzx,yzxx)

每一種發生的可能均為 $\frac{(365)(1)(364)(363)}{(365)^4}$ 即

$\begin{displaymath} P(X_4=3) =\frac{6(365)(1)(364)(363)}{(365)^5} = \frac{6(364)(363)}{(365)^3} \end{displaymath}$

利用上表所列 X_n 的機率分配及期望值的定義，同時將 364 數寫成 (365-1)，363 寫成 (365-2) 等等，可知

$\begin{eqnarray*} E(X_1) &=& 1 \\ E(X_2) &=& 1\times\frac{1}{365}+2\times\frac{(365-1)}{365}=\frac{1}{365}+2(1-\frac{1}{365})=2-\frac{1}{365} \end{eqnarray*}$

同法可得

$\begin{eqnarray*} E(X_3) &=& 3-\frac{3}{365}+\frac{1}{(365)^2} \\ E(X_4) &=& 4-\frac{6}{365}+\frac{4}{(365)^2}-\frac{1}{(365)^3} \end{eqnarray*}$

由以上式子的形式可看出每一式子為正負交錯，而且係數為二項式係數，因此我們推測其一般式的形式為

$\begin{displaymath} E(X_n) = \sum_{k=1}^n (-1)^{k+1}\frac{{n \choose k}}{(365)^{k-1}} , \end{displaymath}$

在上式中加入和減去 k=0 項，然後由每項分母中分解出 (365)^1-n 即得

$\begin{displaymath}\begin{eqalign} E(X_n)&=(365)^{1-n}[(365)^n-\sum_{k=0}^n{n\ch... ... &=365-\frac{(364)^n}{(365)^{n-1}} \quad n=1,2,3 \end{eqalign}\end{displaymath}$

(9)

上式為正確可證明如下：

我們知道每天必為 n 人中某一人的生日或不為其中任一人的生日，若一年中的第 k 日不為 n 人中任一人的生日。令隨機變數 Y_k 的值為 1，否則為 0。則所有非生日的天數和和為 ( $Y_1+Y_2+\cdots+Y_{365}$ )。而對每一 k 值

$\begin{displaymath} E(Y_k)=0\mbox{,}P(Y_k=0)+1\times P(Y_k=1)=(\frac{364}{365})^n \end{displaymath}$

因此，非生日天數的期望值為 $365(\frac{364}{365})^n$ ，故

$\begin{displaymath} E(X_n)=365-365(\frac{364}{365})^n=365-\frac{(364)^n}{(365)^{n-1}} \end{displaymath}$

要求使 $E(X_n)\geq 183$ 的最小 n 值就是相當於找最小的 n 值使 $(\frac{364}{365})^n\leq\frac{1}{2}$ ，查對數表，就得 n=254。

附帶還想說明一點，以上的討論告訴我們，有時候我們不必確知隨機變數的機率分配，照樣可以求出其期望值。

看完以上的討論，或許有人意猶未盡，想要自己一顯身手，以下就是數個好機會。

(1) 依據美國統計結果顯示並非一年 365 天中，每天均為相同可能的生日。假如，夏天出生的人數比冬天要多，試問這事實對表一內機率有什麼影響？（使機率變大還是減小？）

(2) 倘若我們把二月二十九日也列入考慮，則對表一內的各機率又會產生什麼影響？（使機率變大？變小？）

(3) 假設一年內的 12 個月均為相等可能的出生月份，請導出一個頗似表一的機率表，代表一群隨機聚會的 r 人群體中，至少有二人同月生的機率，r=1,2,3,4,5。倘若我們把每月有不同日數的事實列入考慮，對你方才導出的表有什麼影響？

(4) 試證在 r 人相聚的群體中，恰有二人生日相同的機率為

$\begin{displaymath}t_r={r\choose 2}\frac{365\cdot 364\cdots (365-r+2)}{(365)^r}\end{displaymath}$

(5) 在上題中，若以 q_r 表示 r 人中無人同生日的機率，試證

$\begin{displaymath}t_r={r\choose 2}\frac{q_r}{366-r}\end{displaymath}$

(6) 倘若我們把古典生日問題改為要求至少應有多少人相聚，方可使至少有二人生日相同或相鄰（12月31日與 1月 1日相鄰）的機率大於 $\frac{1}{2}$ ？

對外搜尋關鍵字：
．機率論
．隨機變數
．期望值
．Bertrand

　1│2│3　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：黃信元

最後修改日期：4/26/2002