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之naa
Balls-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+) µ
X1:load of the first bin 名=Binomial m =E[X]= n Chernoff bound: rXn+mn】 For m=n,u=1. 1 The max load is Pr[X≥LU≤ eLL n2 Omiw.h.p. when L= elnn Inlnn
X1: load of the first bin µ = E[X1] = m n X1 = Binomial m, 1 n ⇥ Chernoff bound: Pr[X ⇥ (1+)µ] ⇥ e (1+)(1+) µ For m = n, µ = 1. Pr[X ⇥ L] eL eLL 1 n2 when L = e lnn lnlnn The max load is O lnn lnlnn ⇥ w.h.p
X1:load of the first bin Binomial m u=E[X1]= n Chernoff bound: Pr[X≥t]≤2-for t≥2eu Form≥nlnn,u≥lnn. x2W=mX2gu≤2ws22a<点 The max load is ()w.h.p
X1: load of the first bin µ = E[X1] = m n X1 = Binomial m, 1 n ⇥ Chernoff bound: Pr[X ⇤ t] ⇥ 2t for t ⇤ 2eµ For m n lnn, µ lnn. Pr X1 ⇤ 2em n ⇥ = Pr[X1 ⇤ 2eµ] ⇥ 22eµ ⇥ 22e lnn < 1 n2 The max load is O m n ⇥ w.h.p