(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 $n\cdot$$1\over n$$=1$ and its variance is $n\cdot$$1\over n$$\cdot(1-$$1\over n$$)$$=1-$$1\over n$. Then Chebyshev tells us $P(|X-1|\ge k\cdot(1-$$1 \over n$$)) \le$$ 1\over k^2$. For $1\le k\lt n$, since $k\over n$$\lt 1$ this means $P(|X| \ge k+1) \le $$1\over 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 $n\over 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)=($$1\over n$$)^n$ so the union bound gives $P($n balls land in some box$)=$$n \over n^n$$\le$$ n\over n^2$.