生日問題

它在說什麼

23 個人的房間裡，有兩人同一天生日的機率是 0.507。算法從反面走：第二個人避開第一個人生日的機率是 $364/365$，第三個人再避開前兩人是 $363/365$，一路乘到第 23 個人，全部避開的機率是

$$\prod_{i=1}^{22} \frac{365-i}{365} \approx 0.493,$$

有人同一天生日的機率因此是 $1 - 0.493 = 0.507$。人數到 50，這個機率是 97%。

23 個人兩兩之間有 $\binom{23}{2} = 253$ 對，每一對都是一次落在同一天的機會；機會的數量按人數的平方長，人數因此不必多。直覺按人頭數，數不出這件事。

它跟洗牌的關係

逆向洗牌做 $k$ 次，每張牌帶一串 $k$ 位元的標籤，牌堆要洗勻，一個充分條件是 52 張牌的標籤全不重複，即 52 個「人」從 $2^k$ 個「生日」裡抽、全不同天的生日問題。該書用這個計算證出鴿尾式洗牌的上界 $t_{\mathrm{mix}} \le 2\log_2(4n/3)$。散列表的碰撞、亂數種子的重複，用的也都是同一個計算。

資料來源

1. 1.David A. Levin & Yuval Peres（2017）。Markov Chains and Mixing Times，2nd ed. Providence: American Mathematical Society。第 8.3 節「Riffle Shuffles」pp.107-110：鴿尾式洗牌的三種等價描述（其中第三種是逆洗牌的位元標籤法）、命題 8.11 的強停止時間，以及命題 8.12 的上界 $t_{\mathrm{mix}} \le 2\log_2(4n/3)$。第 4.1 節 p.47 定義全變異距離，第 18 章 p.261 處理 cutoff 現象。原文