Assume there are $m$ balls and $n$ bins. We denote $\eta_{i}^b$ the event that ball $i$ falls into bin $b$, and denote $\epsilon_{ij}$ the event that balls $i$ and $j$ collide.

Collision probability

Probability of any two particular balls collide:

Expected number of collision after tossing $m$ balls: Define indicator function $\mathbf{1}(\epsilon_{ij})$. Then the number of collisions is $\sum_{i\neq j}\mathbf{1}(\epsilon_{ij})$. The expected number of collision is therefore:

Probability of no collision at all:

Number of balls to throw to expect a collision: Solve for $m$ in $(1-\frac{1}{n})^{\binom{m}{2}}=\frac{1}{2}$


Probability of a particular bin is empty: $\big(1-\frac{1}{n}\big)^{\binom{m}{2}} \approx e^{-m/n}$

Probability that a particular bin has exactly $k$ balls:

which the bound is obtained by the inequality $\big(\frac{n}{r}\big)^r \le \binom{n}{r} \le \frac{n^r}{r!} \le \big(\frac{en}{r}\big)^r$.

Probability that a bin has at least $k$ balls:

By considering only $k$ balls out of $m$ and ignoring the others, we have the probability upperbounded by