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:

\begin{aligned} \Pr(\epsilon_{ij}) &= \sum_b \Pr(\eta_j^b|\eta_i^b)\Pr(\eta_i^p) \\ &= \sum_b \frac{1}{n}\frac{1}{n} \\ &= \frac{1}{n} \end{aligned}

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:

\begin{aligned} E[\sum_{i\neq j}\mathbf{1}(\epsilon_{ij})] &= \sum_{i\neq j}E[\mathbf{1}(\epsilon_{ij})] \\ &= \sum_{i\neq j}\Pr(\epsilon_{ij}) = \sum_{i\neq j}\frac{1}{n} \\ &= \frac{1}{n}\binom{m}{2} \end{aligned}

Probability of no collision at all:

\begin{aligned} \prod_{i\neq j}\Pr(\bar{\epsilon}_{ij}) &= \prod_{i\neq j}(1-\frac{1}{n}) \\ &= (1-\frac{1}{n})^{\binom{m}{2}} \end{aligned}

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

## Counting

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:

$\binom{m}{k}\big(\frac{1}{n}\big)^k\big(1-\frac{1}{n}\big)^{m-k} \le \frac{m^k}{k!}\frac{1}{n^k},$

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:

$\sum_{i=k}^m\binom{m}{i}\big(\frac{1}{n}\big)^i\big(1-\frac{1}{n}\big)^{m-i}$

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

$\binom{m}{k}\frac{1}{n^k}\le \big(\frac{me}{nk}\big)^k$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}