m balls are thrown into n bins. m E[X;]= X;:number of balls in the i-th bin n Chernoff Bound:For 6>0, Pr[X,≥(1+δ)4≤ ·When m=n:u=l ≥法 elnn for L= n2 In Inn 。union bound: n婴x≥sn民≥小s分 1<i≤n Max load is o logn loglogn w.h.p.m balls are thrown into n bins. X number of balls in the i-th bin i : μ = 피[Xi ] = m n • When : • union bound: m = n μ = 1 Pr[Xi ≥ L] ≤ eL eLL ≤ 1 n2 for L = e ln n ln ln n Pr [ max 1≤i≤n Xi ≥ L ] ≤ n Pr[Xi ≥ L] ≤ 1 n Max load is O w.h.p. ( log n log log n ) Chernoff Bound: For δ > 0, Pr[Xi ≥ (1 + δ)μ] ≤ ( eδ (1 + δ)(1+δ) ) μ