Question

Suppose that we randomly drop n^(3/2) balls into n bins,give an upper bound on the expectation of the maximum number of balls in any bin

Answer 1

☆☆ranshsangwan☆☆



Let XiXi be the # of balls in the iith bin and X=max{X1,X2,⋯,Xn}X=max{X1,X2,⋯,Xn}. We have

E(X)=∑i≥1Pr(X≥i)≤∑i>2n1/2+9lnnPr(X≥i)+2n1/2+9lnnE(X)=∑i≥1Pr(X≥i)≤∑i>2n1/2+9ln⁡nPr(X≥i)+2n1/2+9ln⁡n

and for i>2n1/2+9lnni>2n1/2+9ln⁡n,

Pr(X≥i)=Pr(X1≥i ∨ X2≥i ∨ ⋯ ∨ Xn≥i)≤∑j=1nPr(Xj≥i)≤∑j=1nexp(−i−n1/23)≤∑j=1nexp(−3lnn)=1n2Pr(X≥i)=Pr(X1≥i ∨ X2≥i ∨ ⋯ ∨ Xn≥i)≤∑j=1nPr(Xj≥i)≤∑j=1nexp(−i−n1/23)≤∑j=1nexp(−3ln⁡n)=1n2

where

Xj∼Binomial (n3/2,1n)Xj∼Binomial (n3/2,1n) and E(Xj)=n−−√E(Xj)=n;

the first inequality uses the union bound;

the second inequality uses a loose form of Chernoff bound:

Pr(X≥(1+δ)μ)≤exp(−δμ3)for δ>1Pr(X≥(1+δ)μ)≤exp(−δμ3)for δ>1

Therefore,

∑i>2n1/2+9lnnPr(X≥i)≤n3/2⋅1n2=1n−−√∑i>2n1/2+9ln⁡nPr(X≥i)≤n3/2⋅1n2=1n

implying an upper bound

E(X)≤2n−−√+1n−−√+9lnn