1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want exactly $k$ balls or least $k$ balls? A single bucket with $k$ balls or at least one bucket with $k$ balls? Any bucket, or a specific bucket? $\endgroup$ – R B Jan 26 '15 at 16:00
  • $\begingroup$ At least one bucket with exactly $k$ balls. $\endgroup$ – nimcap Jan 26 '15 at 16:02
2
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.