Jtdylktuy

(Using Chebyshev's inequality and Union bound)

Suppose that we throw $n$ balls into n bins uniformly at random. Let $k≥sqrt n$ be a positive integer Show that with probability at least $1-frac n{k^2}$, no bin has strictly more than $k$ balls.

Prove that the probability that there is some bins of $k+1$ or more balls is at most $frac n{k^2}$.

Consider of the distribution of balls that land in a particular bin, $X$. This will be a binomial distribution. Its mean is $ncdot$$1over n$$=1$ and its variance is $ncdot$$1over n$$cdot(1-$$1over n$$)$$=1-$$1over n$. Then Chebyshev tells us $P(|X-1|ge kcdot(1-$$1 over n$$)) le$$ 1over k^2$. For $1le klt n$, since $kover n$$lt 1$ this means $P(|X| ge k+1) le $$1over k^2$. Now if $k ge sqrt n$ then the probability of one of the n bins having more than k balls will be at most $nover k^2$ by the union bound (for $k lt sqrt n$ the upper bound we get is greater than 1 and so is meaningless). For the case $k=n$ simply note the $P(X=n)=($$1over n$$)^n$ so the union bound gives $P($n balls land in some box$)=$$n over n^n$$le$$ nover n^2$.