Show that when $n$ balls are thrown into $n^3$ cells, the chance that (at least) two balls will collide goes to zero as $n\to \infty$

Question

Show that when $n$ balls are thrown into $n^3$ cells, the chance that (at least) two balls will collide goes to zero, as a function of $n$:

$$\lim_{n\to \infty }P(\exists\, x,y:x,y\text{ collide})=0$$

Answer 1

Markov's inequality is the right idea. Let $X$ be the number of pairs of balls which are in the same cell. For example, when $n=6$, and the arrangement of balls is

• Cell 1: Balls $1$ and $2$.

• Cell 2: Balls $3,4$ and $5$.

• Cell 3: Ball 6.

• All other cells: empty.

then $X=4$, since the pairs are $(1,2)$, $(3,4),(3,5)$ and $(4,5)$.

You want to prove the probability of $X\ge 1$ goes to zero, so we can use Markov's inequality $P(X\le 1)\le E[X]$ to get an upper bound on this probability and instead show that $E[X]$ goes to zero.

By linearity of expectation, $E[X]$ is easy to calculate. There are $\binom{n}2$ pairs of balls. For each pair, the probability they are in the same cell is $\frac1{n^3}$. Therefore, $E[X]=\underline{\hspace{1.5cm}}$ (fill in the blank). Does this go to zero as $n\to\infty$?