將 N 個球隨機放入 M 個桶子的數學問題
這篇文章是一個數學題目，是我跟朋友聊天時，他說他的朋友當助教時，教授出的題目。題目如下：將 N 個球隨機放入 M 個桶子，求：所有桶子皆不超過 K 個球的機率為何。
初見
乍看之下，將 N 個球隨機放入 M 個桶子很像是高中時的隔板法 (stars and bars)，例如說用 2 個板子，把 3 個球隔開成 3 個部份有 $C^5_2 = 10$ 種 case：
- ｜｜●●●
- ｜●｜●●
- ｜●●｜●
- ｜●●●｜
- ●｜｜●●
- ●｜●｜●
- ●｜●●｜
- ●●｜｜●
- ●●｜●｜
- ●●●｜｜
雖然是 stars and bars 但是我畫的是 circles and bars。 假設 K=2，那麼除了情況 1, 4, 10 在單一桶子有三個球之外，都是合法的 case，答案應該是 $\frac{7}{10}$。
可惜，這是錯的。
不同情形下機率不同
為什麼呢？考慮更極端的 100 個球的情形下，每個球都丟在同一個桶子的 case，跟分佈較平均的 case 相比，機率應該是低不少的，因此 $\frac{7}{10}$ 是不對的。到底不同 case 的機率分佈怎麼計算呢？
把問題進一步簡化，只有兩個球、兩個桶子的話，有這三種情形：
- ｜●●
- ●｜●
- ●●｜
直覺來說，跟丟兩個硬幣一樣正反各一的機率有 $\frac{1}{2}$，「平均放在兩個桶子」 case 2 的機率應該也是 $\frac{1}{2}$，case 1, 3 是 $\frac{1}{4}$。
好像快要找出某種規律了？再簡化問題成一個球、兩個桶子的話：
- ｜●
- ●｜
這兩個 case 機率各一半，第二個球進來之後，兩者各有一半的機率變成「平均放在兩個桶子」的情形，畫成圖就是：
等等，這個不就是令人熟悉的帕斯卡三角形 (Pascal’s triangle) 嗎：
因此，兩個桶子的解析解是這樣：
$$2^{-N} \sum^{N}_{i=0} \sum^{N}_{j=0} \llbracket(i+j = N) \wedge (i \le K) \wedge (j \le K) \rrbracket \frac{N!}{i!j!}$$
其中 $\llbracket X \rrbracket$ 這個符號表示如果條件 $X$ 成立就是 1，條件不成立就是 0。合理猜測，$M$ 個桶子的解析解是這樣：
$$M^{-N} \sum^{N}_{i_1=0} \cdots \sum^{N}_{i_M=0} \llbracket(\sum^{M}_{j=1} i_j = N) \wedge i_{1..M} \le K \rrbracket \frac{N!}{i_i!\cdots i_M!}$$
註：$M = 2$ 的簡化版是：
$$2^{-N} \sum^{N}_{i=0} \llbracket (i \le K) \wedge (N-i \le K) \rrbracket \frac{N!}{i!(N-i)!}$$
簡單用程式驗算
用這個公式可以算出 $(M,N,K) = (4,2,2)$ 的機率是 $\frac{6}{16}$ ，用 Python 驗算看看：
1import random
2M, N, K = 4, 2, 2
3def try_one():
4 bucket = [0] * N
5 for i in range(M):
6 bucket[random.randint(0, N-1)] += 1
7 return max(bucket)
8
9sum([try_one() <= K for i in range(16000)]) # 6034結語
找出答案之後，就知道這個東西跟 binomial, multinomial 有相當大的關聯，用這個關鍵字在 wiki 上找了一下，隔板法 (stars and bars) 跟多項式定理 (multinomial) 也有很強烈的連結，這樣看來本篇也是重新發明了一次輪子。但是在完全沒有關鍵字的情形下，用大於高中程度離散數學的知識（註：筆者現在的數學程度 XD），重新發明一次輪子，也是個有趣的訓練。