Probability of $k$ collisions

Question

Say we have $m$ buckets. We select a random bucket and put a ball in it, we repeat this $n$ times. In the end what is the probability of having at least one bucket with exactly $k$ balls?

I have tried several approaches, the closest I got is this. The probability of putting first $k$ balls into that cell is $\frac1{m^k}$ and not putting the rest of the balls is $\left( 1 - \frac1{m} \right)^{n-k}$. We have $\left(\begin{smallmatrix}n\\k\end{smallmatrix}\right)$ such configurations, i.e. a cell getting $k$ balls and not having the rest, hence the final probability is: $$ \begin{pmatrix}n\\k\end{pmatrix} \frac1{m^k} \left( 1 - \frac1{m} \right)^{n-k} $$

We have $m$ such cells, so the final probability is: $$ m\begin{pmatrix}n\\k\end{pmatrix} \frac1{m^k} \left( 1 - \frac1{m} \right)^{n-k} $$

I have implemented a simulation where I simulate the procedure million times and report the results. For small probabilities simulation and the expression produces close results. However for particular values they don't coincide.

I suspect that the expression above needs more terms, but for small probabilities those terms tend to be very small and could be discarded to approximate.

EDIT Problem solved, see the answer below.

Answer 1

Your approach makes the error of "double counting": a configuration that has $k$ balls in the first bucket and in the second is counted twice. You could try by using inclusion-exclusion, but the result would probably be complicated.

A simple approximation, it should work for $m\to \infty$ , $n/m \to t$ constant

The model can be approximated as $m$ iid Poisson vars, with mean $t=n/m$. Then the desired probability is

$$ P \approx 1 - \left(1- e^{-t} \frac{t^k}{k!}\right)^m $$

Answer 2

Starting with probability of putting $k$ balls into one box and generalizing to $m$ box followed by inclusion-exclusion principle I got the expression below.

$$ \sum^{\lfloor \frac{n}{k} \rfloor}_{i=1} (-1)^{i+1} \binom{m}{i} \left[ \prod^{i-1}_{j=0} \binom{n-jk}{k} \right] \left( \frac1{m} \right)^{ik} \left( \frac{m-i}{m} \right)^{n-ik} $$

Compared it with experimental results, they coincided perfectly. More details here.