生日攻擊
我正在閱讀有關Wikipedia 中的生日攻擊的資訊：
我們考慮以下實驗。從一組 $ H $ 我們選擇的價值觀 $ n $ 值均勻隨機，從而允許重複。讓 $ p(n; H) $ 是在這個實驗中至少一個值被多次選擇的機率。這個機率可以近似為$$ p(n:H) \approx 1−e^{-{n(n-1) \over 2H}} $$
我的問題：那在哪裡 $ e^{-{n(n-1) \over 2H}} $ 價值從何而來？
讓我們首先計算每個值都是唯一的機會。
選擇的兩個值是唯一的機會是 $ H - 1 \over H $ 因為在選擇第二個值時，您只有 $ H - 1 $ 剩下唯一的選秀權，其中一個選秀權是非唯一的。選擇第三個號碼有機會 $ H - 2 \over H $ 是唯一的，所以選擇 3 個唯一數字的總機會是 $ {H - 1 \over H} \times {H - 2 \over H} $ . 這可以繼續，以便採摘的機會 $ n $ 唯一值是：
$$ {H - 1 \over H} \times {H - 2 \over H} \times \cdots \times {H - (n - 2) \over H} \times {H - (n - 1) \over H} $$ 這與生日悖論的極限完全相同。
然後需要更多的數學知識。使用近似值。為了 $ x \leq 1 $ 泰勒系列_ $ e $ 給出一個近似值：
$$ e^x \approx 1 + x $$ 然後注意以下幾點：
$$ {H - 1 \over H} = 1 - {1 \over H} \approx e^{-{1 \over H}} $$ 然後我們將計算改寫為：
$$ e^{-{1 \over H}} \times e^{-{2 \over H}} \times \cdots \times e^{-{n - 2 \over H}}\times e^{-{n - 1 \over H}} = $$ $$ e^{-{1 + 2 + \cdots + n-2 + n-1 \over H}} = $$ $$ e^{-{n(n-1)/2 \over H}} = e^{-{n(n-1) \over 2H}} $$ 這就是選擇的每個值都是唯一的機率。如果不是每個值都是唯一的，則必鬚髮生衝突，因此發生衝突的機會為：
$$ p(n:H) \approx 1−e^{-{n(n-1) \over 2H}} $$ 這也是連結的維基百科文章的價值，但它有點模棱兩可 $ / $ 和 $ \cdot $ 優先規則。
這是一種略有不同的方法： 選擇方法的總數 $ n $ 之間的數字 $ H $ 允許重複的值（併計入揀選順序）是 $ A=H^n $ . 不重複選擇的方法數是 $ B=\frac{H!}{(H-n)!}. $
顯然，您要計算的機率是 $ (A-B)/A=1-B/A $ . 現在，確實 $ B/A $ 包含您要查找的指數？使用斯特林公式：
$$ x!\approx \sqrt{2\pi x}(x/e)^x. $$ 我們看到： $$ A/B\approx \sqrt{\frac{H-n}{H}}\left(\frac{H-n}{H}\right)^{H-n}e^n. $$ 取對數，我們發現：
$$ \log(A/B)\approx (H-n+1/2)\log(1-n/H)+n\approx -(H-n+1/2)(n/H+(n/H)^2/2)+n $$ 開發和刪除低階項以獲得 $ \log(A/B)\approx n(n-1)/2H $ .
把所有東西放在一起確實會產生
$$ p(n:H)\approx 1-e^{\frac{n(n-1)}{2H}}. $$ 這種方法的主要優點是它避免了許多近似值的乘積（如夜鶯的答案），這通常需要非常小心。