5
$\begingroup$

Suppose that we throw $m$ balls into $n$ bins uniformly and independantly at random. We consider collisions as distinct unordered pairs, e.g., if 3 balls are tossed in one bin, we count 3 collisions.

What is the probability of having at least $j$ collisions when we throw $m$ balls into $n$ bins, such that at least $j$ bins are empty at the end of the process?

Case $m \leq n$:

As we suppose $m < n$, this question is in fact equivalent to computing the probability that we toss $m$ balls in $m-j$ bins. Indeed, we throw our $m-j$ first balls in distinct bins, and the $j$ remaining balls in these $m-j$ bins. We can view tossing $m$ balls in $m-j$ as the following equation: $$x_1 + x_2 + \cdots + x_{m-j} = m$$ where $x_i$ is the number of balls in bin $i$. The number of solutions in $\mathbb{N}$ of this equation is a $m$-combination on a set of size $m-j$, i.e., $\binom{m+m-j-1}{m} = \binom{2m - j - 1}{m}$.

The number of ways to choose $m-j$ bins out of $n$ is $\binom{n}{m-j}$.

The number of possibilities to throw $m$ balls in $n$ bins is $n^m$, thus $$\mathbb{P}[\text{at least } j \text{ collisions}] = \frac{\binom{2m - j - 1}{m} \cdot \binom{n}{m-j}}{n^m}.$$

What do you think of this approach? Am I overcounting/undercounting something?

Case $m > n$:

In my opinion, this case is much harder to solve.

As I count collisions as distinct unordered pairs, the total number of collisions is $$\sum_{i = 1}^n \binom{x_i}{2}$$ where $x_i$ is the number of balls in bin $i$. Hence, to have exactly $j$ collisions, a necessary condition is to have $\sum_{i=1}^{n} \binom{x_i}{2} = j$. Let's tweak this equation a bit. $$ \begin{align*} \sum_{i=1}^{n} \binom{x_i}{2} = j & \iff \sum_{i=1}^n \frac{x_i!}{2 \cdot (x_i-2)!} = j\\ & \iff \sum_{i=1}^{n} \frac{x_i!}{(x_i-2)!} = 2j\\ & \iff \sum_{i=1}^n x_i(x_i-1) = 2j\\ & \iff \sum_{i=1}^n x_i^2 = 2j + \sum_{i=1}^n x_i\\ & \iff \sum_{i=1}^n x_i^2 = 2j + m \end{align*} $$ where the last equality follows from the fact the sum of the balls in each bins is the number of balls tossed.

Therefore, this problem is equivalent to solving the following problem: how many representations as a sum of $n$ squares does a number have? This problem seems far from trivial to me, as I did not find easy explicit formulas to work with.

However this approach was for finding exactly $j$ collisions, and I am interested in finding at least $j$ collisions. As $m > n$, we will have some collisions. We can express $m = qn + r$ for some $q, r \in \mathbb{N}$. The least collisions we will have is when the balls are uniformly distributed amongst the bins, thus we will have at least $$C_{min} = \sum_{i=1}^r \binom{q+1}{2} + \sum_{i=1}^{n-r} \binom{q}{2}$$ collisions, which forces $j > C_{min}$. The problem thus becomes, in how many ways can we distribute $m$ balls into $n$ bins such that $\sum_{i=1}^n \binom{x_i}{2} \geq j$.

Here I am stuck, I can't find an easy way with combinatorics to solve this. I am fine with this problem being solved asymptotically, so if you have any ideas and/or references on the subject... :).

Thanks for reading and helping


Edit

I think both cases above are wrong, because I was undercounting some things. Probability with the function given in the case $m \leq n$ This image shows that the probability of having $j$ collisions do not increase nor decrease. I was expecting something like a gaussian, or at least something with a low probabiliy of having a few collisions, a high probability of having an average number of collisions, and a low probability of having a lot of collisions.

I thought about another way of counting, and I think the results I obtain are better. For that, I need the following Lemma, taken from this paper, page 16.

Lemma 1: The probability that exactly $k$ bins are not empty after throwing $m$ balls is $\frac{\binom{n}{k}k!S(m,k)}{n^m}$, where $S(m,k)$ is a Stirling number of the second kind.

With this Lemma, I obtain the following result.

Lemma 2: Let $m$ be the number of balls thrown uniformly and independently ar random into $n$ bins. The probability of having at least $j>1$ collisions and at least $j$ empty bins is $$ \mathbb{P}[\text{at least } j \text{ collisions}] = \frac{1}{n^{m}} \sum_{i=1}^{n-j} \binom{n}{i} i! S(m,i). $$
Proof: As explained previously, the probability of having at least $j$ collisions and at least $j$ empty bins (or at most $n-j$ non-empty bins) is equal to the probability of tossing $m$ balls in at most $n-j$ bins. Let $A$ be the event "at most $n-j$ bins are not empty" and let $A_i$ be the event "exactly $i$ bins are not empty". Then $A = \cup_{i=1}^{n-j} A_j$ and $A_i \cap A_k = \emptyset$ if $i \neq k$, hence $\mathbb{P}[A] = \sum_{i=1}^{n-j}\mathbb{P}[A_j]$ and Lemma 1 concludes the proof. $\square$

We can see on the next plot that this results already seems closer to reality (this was plotted for $n = 500$, $m = 200$ and $j$ from $1$ to $1000$). enter image description here

Moreover, with this approach, we don't need to separate the cases $m \leq n$ and $m > n$ (at least I think, you might need to correct me on this).

The downside is that now we have to work with a sum... and Stirling numbers of the second kind...

Do you guys have any idea to remove the sum and obtain an upper bound of this?

$\endgroup$
  • $\begingroup$ I haven't digested it all yet, but in the $m\le n$ case you don't seem to be taking into account the fact that fewer than $j$ bins with multiple balls can cause $j$ collisions if the multiples are more than doubles. $\endgroup$ – joriki May 16 '16 at 11:24
  • $\begingroup$ @joriki I did not prove it, but I think that the minimum of collisions is achieved when the bins are equally loaded. Thus if I have m balls in m-j bin with $\geq$ 1 bin containing $\leq 1$ ball, the number of collisions will be greater than $j$ (I think this is what you said). I think this fact is contained in the $m$-combination as this counts the solutions where some bins have $\leq 1$ balls. However I might be wrong and have forgotten to count something, because the probability seems really low. $\endgroup$ – Laurent Hayez May 16 '16 at 11:53
  • $\begingroup$ You're right that the minimum number of collisions occurs when the balls in the occupied bins are maximally spread out. But if I understand correctly you're trying to count the number of cases in which you have at least $j$ collisions? Then you also have to take into account the case where less than $j$ bins are empty, but the resulting multiples are less spread out? $\endgroup$ – joriki May 16 '16 at 11:57
  • $\begingroup$ @joriki Ah I see what you mean, and I will edit the question accordingly. In fact in the problem, I need that at least $j$ bins are empty after throwing the $m$ balls. But otherwise this is correct, it could happen that less than $j$ bins are empty but the number of collisions is greater than $j$. $\endgroup$ – Laurent Hayez May 16 '16 at 12:02
  • $\begingroup$ How is this going to work for m<n? There always going to be at least 1 empty bin. Also, if there is 1 ball, does it means the collision is equal to 1? $\endgroup$ – Alex May 16 '16 at 16:48

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.

Browse other questions tagged or ask your own question.