[Algo] 5.4 Probabilistic analysis and further uses of indicator random variables (1)

5.4.1 The birthday paradox
How many people must there be in a room before there is a 50% chance that two of them were born on the same day of the year?

我們先定義幾個符號：
$k$ 為總人數
一年有 $n = 365$ 天（假設沒有閏年的影響）
$b_i$ 為第i個人的生日，$1 \leq b_i \leq n$

假設生日都是 uniformly distribute 的，所以我們可以得到 $\mbox{Pr}\{b_i = r\} = \frac{1}{n}$，其中 $i = 1, 2, \ldots k$，$r = 1, 2, \ldots n$，而且我們再假設彼此的生日都是獨立的，那麼我們可以推斷第i個人和第j個人他們的生日都是 $r$ 的機率是：
$\mbox{Pr}\{b_i = r$ and $b_j = r\} = \mbox{Pr}\{b_i = r\}\mbox{Pr}\{b_j = r\} = \frac{1}{n^2}$
所以， 第i個人和第j個人他們的生日是同一天的機率就是：
$\mbox{Pr}\{b_i = b_j\} = \sum_{r = 1}^n \mbox{Pr}\{b_i = r$ and $b_j = r\} = \sum_{r = 1}^n \frac{1}{n^2} = \frac{1}{n}$

接下來我們從反面來算，先算每個人的生日都不一樣的機率 $p$：
$p = \frac{P^n_k}{n^k} = \frac{n(n-1)(n-2) \cdots (n - k + 1)}{n^k}$
$ = 1 \cdot (\frac{n-1}{n}) \cdot (\frac{n-2}{n}) \cdots (\frac{n - k + 1}{n})$
$ = 1 \cdot (1 - \frac{1}{n})(1 - \frac{2}{n}) \cdots (1 - \frac{k - 1}{n})$
由不等式$1 + x \leq e^x$，我們可以整理如下：
$p \leq e^{-1/n}e^{-2/n} \cdots e^{-(k-1)/n} = e^{-k(k-1)/2n}$

所以回到問題來，我們希望 $1 - p \geq 1/2$， 顯然 $-k(k-1)/2n \leq \ln(1/2)$，解完這個二次不等式，我們可以得到 $k \geq (1 + \sqrt{1 + (8\ln 2)n})/2$，以 $n = 365$ 來說，$k \geq 23$
                                                                                                                                                                    
接下來，課本利用 indicator random variable 來幫助我們分析要有多少人在房間裡，才會恰好兩個人的生日是在同一天？
一樣假設有 $k$ 個人在房間裡面，我們定義 indicator random variable $X_{ij}$ 如下：
$X_{ij} =  \mbox{I}\{$ person i and person j have the same birthday $\}$
所以我們知道：$E[X_{ij}] = \mbox{Pr}\{$ person i and person j have the same birthday $\} = 1/n$
定義 random variable $X$ 為有多少人的生日為同一天，則 $X = \sum_{i = 1}^k \sum_{j = i+1}^k X_{ij}$
$E[X] = \sum_{i = 1}^k \sum_{j = i+1}^k E[X_{ij}] = C_{2}^{k} \frac{1}{n} = \frac{k(k-1)}{2n}$
當 $k(k-1) \geq 2n$ 時，生日在同一天的人數的期望值才至少會大於 1，以 $n = 365$ 來說，至少 $k = 28$ 人，我們才期望可以找到至少兩個人的生日是同一天。