Birthday Paradox m-balls-into-n-bins: m- E:there is no bin with >1 balls. 胸=i〔-》 Taylor's expansion:e-k/1-/n (-) m-l m-1 e k=1 ( k=1 =e-m(m-1)/2n ≈e-m2/2n
Taylor's expansion: ek/n ⇥ 1 k/n ⇥ m ⌅1 k=1 e k n = exp m ⇤1 k=1 k n ⇥ = em(m1)/2n em2/2n m ⇤1 k=1 1 k n ⇥ = m ⇤1 k=0 1 k n ⇥ Pr[E] m-balls-into-n-bins: E: there is no bin with > 1 balls. Birthday Paradox
Birthday Paradox m-balls-into-n-bins: E:there is no bin with >1 balls. PHe]-(1-) (-）≈6rea m-1 exact 08 ---approx k=三1 0.6 n=365 1 0.4 for m= 02 10 20 30 40 50 60 0.02 Pr[E]≈e 0 0.02 20 30 40 50 60 m=f(√m)for constant e m
em2/2n m ⇤1 k=1 1 k n ⇥ Pr[E] for m = 2n ln 1 , m = ⇥( n) for constant = m ⇤1 k=0 1 k n ⇥ Pr[E] m-balls-into-n-bins: E: there is no bin with > 1 balls. Birthday Paradox
Perfect Hashing S={a,b,c,d,e,f uniform random h [N→[M Pr[perfect]1/2 M =O(n2) Table T: ca birthday！ UHA:Uniform Hash Assumption search(x):retrieve h; check whether T[h(x)]=x;
Perfect Hashing e b d f c a h Table T: M S = { a, b, c, d, e, f } search(x): retrieve h; check whether T[h(x)] = x; [N] [M] UHA: Uniform Hash Assumption uniform random Pr[perfect] > 1/2 birthday! = O(n2)
Coupon Collector (cover time) coupons in cookie box number of boxes bought to collect all n coupons number of balls thrown to cover all n bins each box comes with a uniformly random coupon
Coupon Collector number of boxes bought to collect all n coupons each box comes with a uniformly random coupon number of balls thrown to cover all n bins coupons in cookie box (cover time)