Balls-into-Bins Model and Chernof肝Bounds Advanced Algorithms Nanjing University,Fall 2022
Balls-into-Bins Model and Chernoff Bounds Advanced Algorithms Nanjing University, Fall 2022
Balls-into-Bins Model uniformly at random choose h:[m][n] m balls uniformly and independently thrown into n bins Question:probability that each ball lands in its own bin (h is 1-1)? Question:probability that every bin is not empty (h is onto)? Question:maximum number of balls in a bin(maxh()?
Balls-into-Bins Model m balls n bins uniformly and independently thrown into uniformly at random choose h: [m]→[n] Question: probability that each ball lands in its own bin (h is 1-1)? Question: probability that every bin is not empty (h is onto)? Question: maximum number of balls in a bin (max{|h -1 (i)|})?
Birthday Problem Question:probability that each ball lands in its own bin (h is 1-1)? 1-》() m-1 This probability is some constant when m=(Vn) Jan 1st Jan 2nd Jan 3rd Jan 31st Feb 1st Dec 31st
Birthday Problem Question: probability that each ball lands in its own bin (h is 1-1)? Jan 1st Jan 2nd Jan 3rd Jan 31st Feb 1st … … Dec 31st This probability is some constant when
Coupon Collector Question:how many balls we need to throw to leave no empty bins? Let X;be the number of balls thrown until i bins are non-empty, given i-1 bins are already non-empty. X;is a geometric r.v.with parameter(n-i+1)/n. 公刘-X-店m-gn=m+o0m
Coupon Collector Question: probability that every bin is not empty (h is onto)? Question: how many balls we need to throw to leave no empty bins? … Let Xi be the number of balls thrown until i bins are non-empty, given i-1 bins are already non-empty. Xi is a geometric r.v. with parameter (n-i+1)/n
Load Balancing Question:maximum number of balls in a bin (maxh()? Let X;be the number of balls in bin i.That is,X=h(i). Let Y be i.r.v.taking value 1 iff ball j lands in bin i. E(Xi)=E m 1=1 Is maxE()}what we want? For every i,E()is m/n,so max E)is simply m/n. max{E(X,}= m
Load Balancing Question: maximum number of balls in a bin (max{|h -1 (i)|})? Let Xi be the number of balls in bin i. That is, Xi = |h -1 (i)|. Let Yij be i.r.v. taking value 1 iff ball j lands in bin i. Is max{𝔼(Xi )} what we want? For every i, 𝔼(Xi ) is m/n, so max{𝔼(Xi )} is simply m/n