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:
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)
Coupon Collector X: number of balls thrown to make all the n bins nonempty 2=1 Xi is geometric! X:=4 with p:=1-i-1 m bins E[X;]= 1 m i-1 n-i+1
Coupon Collector bins i-1 Xi = 4 X = n i=1 Xi Xi is geometric! pi = 1 i 1 n with E[Xi] = 1 pi = n n i + 1 X : Xi : number of balls thrown to make all the n bins nonempty number of balls thrown while there are exactly (i-1) nonempty bins