Balls into Bins m balls are thrown into n bins. X;:number of balls in the i-th bin [1 withprob,,为 whnereX 17 1 j=1 with prob.1 n m Xi~Bin(m,1/n) =E[X]= n Chernoff Bound:For 6>0, PrX,≥(1+4≤ ed a+Balls into Bins m balls are thrown into n bins. X number of balls in the i-th bin i : X where i = m ∑ j=1 Xij Xij = 1 with prob. 1 n 0 with prob. 1 − 1 n Chernoff Bound: For δ > 0, Pr[Xi ≥ (1 + δ)μ] ≤ ( eδ (1 + δ)(1+δ) ) μ μ = 피[Xi ] = m n Xi ∼ Bin(m,1/n)