Balls-into-Bins m-balls-into-n-bins:max load <w.h.p. X1:load of the first bin m Xj 1 ball j goes to bin i X1= j=1 X=ginomial.司 m =E[X1]= n Chernoff bound: ix之naaBalls-into-Bins • m-balls-into-n-bins: max load <? w.h.p. X1: load of the first bin X1 = ￾ m j=1 X1j Xi j = ￾ 1 0 ball j goes to bin i otherwise µ = E[X1] = m n X1 = Binomial￾ m, 1 n ⇥ Chernoff bound: Pr[X ⇥ (1+￾)µ] ￾ ⇥ e￾ (1+￾)(1+￾) ￾µ