Balls and Bins m balls ○○○○○○ uniformly independently L444↓I n bins birthday problem,coupon collector problem, occupancy problem
Balls and Bins m balls n bins uniformly & independently birthday problem, coupon collector problem, occupancy problem,
Random function balls-into-bins: [m] [n] Prlassignment)..1 nn m nm m random function: Prassigumeut)=m→n 1 1 m 1-1 birthday problem uniformly random function on-to coupon collector pre-images occupancy problem
Random function [m] [n] uniformly random function Pr[assignment] = 1 |[m] [n]| = 1 nm random function: balls-into-bins: Pr[assignment] = 1 n · 1 n ··· 1 n ⇤ ⇥ ⌅ = 1 nm m 1-1 birthday problem on-to coupon collector pre-images occupancy problem
Birthday Paradox Paradox: (i)a statement that leads to a contradiction; (ii)a situation which defies intuition. birthday paradox: Assumption:birthdays are uniformly independently distributed. In a class of m>57 students,with >99%probability, there are two students with the same birthday. m-balls-into-n-bins: &there is no bin with 1 balls
Birthday Paradox Paradox: (i) a statement that leads to a contradiction; (ii) a situation which defies intuition. birthday paradox: In a class of m>57 students, with >99% probability, there are two students with the same birthday. Assumption: birthdays are uniformly & independently distributed. m-balls-into-n-bins: E: there is no bin with > 1 balls. (ii) a situation which defies intuition
Birthday Paradox m-balls-into-n-bins: &there is no bin with >1 balls. uniformly random f [m)[nj, E:f is one-one. m马m_ n·(n-1)…(n-m+1) Im→m 亿m 0 =0
m-balls-into-n-bins: E: there is no bin with > 1 balls. uniformly random f : [m] [n], E: f is one-one. = m ⇤1 k=0 1 k n ⇥ = |[m] 1-1 ⇥ [n]| |[m] ⇥ [n]| Pr[E] Birthday Paradox = n · (n 1)···(n m + 1) nm
Birthday Paradox m-balls-into-n-bins: m-】 E:there is no bin with >1 balls. ecleI(1-) suppose balls are thrown one-by-one: PrE=Prno collision for all m balls] m-1 Prno collision for the (+1)th ball no collision for the first k balls k=0 chain rule
= m ⇤1 k=0 1 k n ⇥ Pr[E] Pr[E] m-balls-into-n-bins: E: there is no bin with > 1 balls. Birthday Paradox = m 1 k=0 Pr[no collision for the (k + 1)th ball | no collision for the first k balls] = Pr[no collision for all m balls] chain rule suppose balls are thrown one-by-one: