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

5.4.2  Balls and bins
假設現在有 b 個 bins $\{1, 2, \ldots, b\}$，然後我們開始隨機的投擲球到這些 bins 裡面，當然每次一定會丟擲到某個 bin 裡面，而且每個 bin 被球投擲進去的機率都是一模一樣的。這個 ball-tossing process 其實就是 Bernoulli trial，這個 model 在未來對我們分析 hashing 是非常有用的。


接下來我們來思考幾個問題：
(1) 如果我們丟 n 個球，對一個給定的 bin，會有幾顆球在裡面？
因為每個 bin 被球投進去的機率都是 $1/b$，所以期望值是 $n/b$。


(2) 對於某個給定的 bin，平均我們要丟到幾個球，這個 bin 才會有球被丟進去呢？
顯然答案當然是 b 個球。

(3) 平均我們要丟幾個球，才會讓每個 bin 裡面都至少會有一顆球？
對這個問題，我們把他切成 b 個 stage 來看，每個 stage  代表有一個球被投擲到某個空的 bin 裡面去，所以我們要分析的就是從第 (i-1) 個 stage 到第 i 個 stage 我們平均要丟幾個球？當現在是第 i 個 stage 的時候，會有 (b - i + 1) 個 empty bins，令 $n_i$ 為我們在第 i 個 stage 裡所投出的球數，而在第 i 個 stage 時丟到不是空的 bin 的機率是 $(b - i + 1)/b$，所以我們可以得知 $E[n_i] = \frac{b}{b - i + 1}$
令 $n = \sum_{i = 1}^b n_i$，則
 $$E[n] = \sum_{i = 1}^b E[n_i] = \sum_{i = 1}^b \frac{b}{b - i + 1} = b\sum_{i = 1}^b \frac{1}{i} = b(\ln b + O(1))$$

所以我們可以得知大概需要 $b \ln b$ 次投擲，才能讓每個 bin 都至少有一顆球在裡面。這個問題也被稱為 coupon collector's problem，有一個人要蒐集 b 種不同的 coupons，那平均下來他要拿到 $b \ln b$ 張 coupons，才能夠全部種類都蒐集到一張。