生日悖論機率的推導
我正在嘗試解釋生日碰撞的可能性。
$ P $ （t個人之間沒有碰撞）= $ (1− \frac{1}{365}) · (1-\frac{2}{365}) ··· (1-\frac{t-1}{365}) $
對於一個人來說，沒有碰撞的機率是 1，這是微不足道的，因為單個生日不能與其他人的生日發生碰撞。對於第二個人，沒有碰撞的機率是 364 超過 365，因為只有一天，第一個人的生日，可以碰撞：
$ P $ （2人無碰撞）= $ (1− \frac{1}{365}) $
如果第三個人加入聚會，他或她可以與已經在那裡的兩個人發生碰撞，因此：
$ P $ （2人無碰撞）= $ (1− \frac{1}{365})·(1−\frac{2}{365}) $
雖然很清楚我們如何獲得 2 人的碰撞機率，但對我來說，我們如何獲得 3 人之間的碰撞機率並不直覺。我希望機率是 $ (1−\frac{2}{365}) $ . 例如，當你擲骰子時， $ 6 $ 是 $ \frac{1}{6} $ , 5 或 6 的機率是 $ \frac{2}{6} $ . 它不是 $ \frac{1}{6} $ · $ \frac{2}{6} $ 生日碰撞似乎就是這種情況。
我很欣賞一個直覺解釋的答案。
當一張圖片的機率變得更直覺 $ t $ 人一一進入房間。
在第一個人進入之前，沒有碰撞/出生日期重合，因此沒有碰撞的機率是 $ P_0=1 $ .
當第一個人進入時，不可能有碰撞/生日巧合，沒有碰撞的機率是 $ P_1=1 $ .
當第二個人進入時，有一次機會進入 $ 365 $ 他/她的生日與第一個人的生日相同，因此沒有碰撞的機率是 $ P_2=1-\frac1{365} $ .
當第三人進入時，或者
——前一階段發生碰撞，那麼不發生碰撞的機率為 $ 0 $ ;
- 或者前一階段沒有碰撞，因此有 $ 2 $ 房間裡有不同生日的人，第三個人有一個生日的機率是 $ 2 $ 在 $ 365 $ ，因此沒有碰撞的機率是 $ 1-\frac2{365} $ .
第三個人進入後不發生碰撞的總機率是通過將這兩個機率加權的機率相加得到的。因此我們有 $ P_3=(1-P_2),0+P_2,\bigl(1-\frac2{365}\bigr) $ ， 因此 $ P_3=\bigl(1-\frac1{365}\bigr)\bigl(1-\frac2{365}\bigr) $
同樣的推理給出 $ P_{i+1}=(1-P_i),0+P_i\bigl(1-\frac i{365}\bigr) $ ， 那是 $ P_{i+1}=P_i\bigl(1-\frac i{365}\bigr) $ .
它來自哪裡 $ P_t=\displaystyle\prod_{i=0}^{t-1},\Bigl(1-\frac i{365}\Bigr) $ .
有關在數字很大的加密上下文中使用的公式的推導，請參閱我的加密雜湊的生日問題 101。
筆記： $ P $ , $ t $ ， 和 $ 365 $ 這裡是 $ q $ , $ n $ 和 $ k $ 那裡。