Birthday Paradox n balls are thrown into m bins: event each bin receives 1 balls (Taylor:1-xe*forx=o(1)) PT61= (-)i。n i0 Formaly::≤i(l-月）setm2 (assuming n <m) whenn=2m in →Pr[8]=(1±o(1)pBirthday Paradox Pr[ℰ] = n−1 ∏ i=0 (1 − i m) ≈ n−1 ∏ i=0 e− i m ≈ e−n2/2m e−(1+o(1))n2/2m ≤ n−1 ∏ i=0 (1 − i m) ≤ e−(1−o(1))n2/2m (Taylor: 1 − x ≈ e for ) −x x = o(1) Formally: (assuming n ≪ m) when n = 2m ln 1 p ⟹ Pr[ℰ] = (1 ± o(1))p n balls are thrown into m bins: event ℰ: each bin receives ≤ 1 balls