這種碰撞機率近似的誤差是多少？
**定理：**選擇 $ Q $ 集合中的隨機自然數 $ {1,2, \dots, M}. $ 發生至少一次碰撞的機率是
$$ P_C(Q) = 1 - \frac{M - (Q - 1)}{M} P_{\neg C}(Q-1). $$
符號： 由 $ P_C $ ，我的意思是發生碰撞的機率。經過 $ P_{\neg C} $ 我的意思是不發生碰撞的機率。
**備註：**這是生日問題。
**備註：**所以 $ P_C(Q) $ 只是通過使用它的補碼來計算的。我以這種方式表達這個定理的原因是因為它的歸納證明與它以這種方式被闡明直接相關。
定理： $$ P_C(Q) \approx 1 - e^{-\tfrac{(Q-1)Q}{2M}}. $$
**證明：**我們知道 $$ e^{-x} = 1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - \ldots $$
如果我們取這個展開式的兩項，我們得到 $ e^{-x} \approx 1 - x $ . 然後
$$ \begin{align} P_{\neg C}(Q)&= \prod_{i=1}^{Q-1} \left(1 - \dfrac{i}{M}\right)\ &\approx \prod_{i=1}^{Q-1} e^{-i/M} \ &= e^{-1/M} e^{-2/M} \dotsc\ e^{-(Q - 1)/M} \ &= e^{-\sum_{i=1}^{Q-1} i/M} \ &= e^{-\dfrac{1}{M} (Q-1)Q/2}\ &= e^{-\dfrac{(Q-1)Q}{2M}}, \end{align} $$
所以 $ P_C(Q) \approx 1 - P_{\neg C}(Q), $ 如預期的。
問題： 如果我使用這個估計來計算在具體情況下發生碰撞的機率，我如何（至少）對我的正確數字有一些概念？
顯然，對於 $ x\in (0,1) $ 這是我們的情況， $$ e^{-x}-(1-x)< x^2/2, $$ 因此估計和實際答案之間的相對乘法誤差滿足 $$ \frac{\widehat{P}{\neg C}(Q)}{P{\neg C}(Q)}<\prod_{i=1}^{Q} \frac{(i/M)^2}{2(1-(i/M))}\leq 2^{-Q} M^{-2Q} \frac{Q(Q+1)(2Q+1)}{6}\frac{1}{(M+1-(Q+1)/2))}, $$ 通過使用第一個的總和 $ Q $ 分子上的平方和分母上的算術幾何平均不等式。所以 $$ \frac{Q^3/3}{ 2^Q M^{2Q}(M-Q/2)} $$ 是誤差的一個很好的近似值。
kodlu 提供了誤差項 的近似值，但您可能還對碰撞機率的固定界限感興趣，您無需深入了解泰勒展開的高階項即可獲得 $ e^{-x} $ . 如何？
- 你保證_ $ 1 - x \leq e^{-x} $ ， 對所有人 $ x $ .
證明。讓 $ f(x) = e^{-x} + x - 1 $ ; 聲稱是 $ f(x) $ 處處是非負的。 $ f’(x) = 1 - e^{-x} $ 僅在零處 $ x = 0 $ ，所以唯一可能的極值點是 $ x = 0 $ 在哪裡 $ f $ 為零；在，例如， $ x = 1 $ 和 $ x = -1 $ , $ f(x) $ 為正，所以 $ f $ 兩邊都是正的 $ x = 0 $ 並且到處都是非負的。
因此，您可以設置 $ 1 - i/M \leq e^{-i/M} $ 因此 $ P_{\lnot C}(Q) \leq e^{-Q (Q - 1)/(2M)} $ .
- 您還可以保證 $ e^{-2x} \leq 1 - x $ ， 只要 $ 0 \leq x \leq 1/2 $ .
證明。讓 $ g(x) = 1 - x - e^{-2x} $ ; 聲稱是 $ g(x) $ 對所有人都是非負的 $ x \in [0, 1/2] $ . $ g’(x) = 2 e^{-2x} - 1 $ 僅在零處 $ x = \frac 1 2 \log 2 \in [0, 1/2] $ ， 所以 $ g $ 只能有一個極值點，它是正的，因為 $ g(\frac 1 2 \log 2) = 1 - \frac 1 2 \log 2 - 1/2 > 0 $ ; 在端點， $ g(0) = 0 $ 和 $ g(1/2) = 1/2 - 1/e $ , $ g $ 是非負的，所以它在整個區間上都是非負的。
因此，如果 $ Q < M/2 $ , 你可以設置 $ 1 - i/M \geq e^{-2i/M} $ 因此 $ P_{\lnot C}(Q) \geq e^{-Q(Q - 1)/M} $ .
將不等式放在一起，如果 $ Q (Q - 1) < M/8 $ ， 我們有$$ 1 - \frac{Q (Q - 1)}{M} \leq e^{-Q(Q - 1)/M} \leq P_{\lnot C}(Q) \leq e^{-Q(Q - 1)/(2M)} \leq 1 - \frac{Q (Q - 1)}{4M}, $$或等效地$$ \frac{Q (Q - 1)}{4M} \leq P_C(Q) \leq \frac{Q (Q - 1)}{M}. $$