m balls are thrown into n bins. m =E[X]= X;:number of balls in the i-th bin n Chernoff Bound:For L>2eu, PrX≥L≤2b ·When m≥nlnn:u≥lnn k≥-mk≥s2w≤2" 1 n2 ·union bound: Pr 1≤i≤n 二 Max load is w.h.p.m balls are thrown into n bins. X number of balls in the i-th bin i : μ = 피[Xi ] = m n Chernoff Bound: For L ≥ 2eμ, Pr[Xi ≥ L] ≤ 2−L • When : • union bound: m ≥ n ln n μ ≥ ln n Pr [ Xi ≥ 2em n ] = Pr[Xi ≥ 2eμ] ≤ 1 n2 Pr [ max 1≤i≤n Xi ≥ 2em n ] ≤ n Pr [ Xi ≥ 2em n ] ≤ 1 n Max load is O w.h.p. ( m n ) ≤ 2−2eμ ≤ 2−2e ln n