Originally Posted by

**MJ0** I posted this thread in the 'pre-university probability and statistics'-section and so far there have not been any replies. Probably I should have posted it it in the advanced section in the first place.

I have had a hard time trying to solve the following problem. I would be pleased if anyone can help me on this (this problem's description actually originates from a *hashing *problem, known in computer science, which I have tried to simplify by describing a more general understandable situation):

There are **m** open boxes, each of which can contain at most one ball. There is a ball throwing machine that fires a total of **n** balls towards the boxes, one by one. For each box, the probability that when the machine throws a ball, the ball falls onto that specific box, is **1/m** (equal for each box). The thrown ball will always fall onto one of the boxes. However, the probability that the ball will actually fall __into__ any box is less than 1 after the first throw (provided that **n **> 1), because a box which is already filled with a ball (from the previous throw(s)), will prevent the thrown ball from falling into that box. Call this a collision. Assume that a thrown ball, which collides with one of the balls in a box, simply disappears.

I need a formula with which I can calculate the expected number of collisions, given **m** boxes and **n** balls.

Thanks in advance.

Let $\displaystyle N$ be the (random) number of collisions.

Since the $\displaystyle m$ boxes are identical in this problem, we have:

$\displaystyle E[N]=mP(\mbox{there is a collision in the first box}).$

And a collision happens in the first box iff at least two balls fall onto it, iff neither 0 nor 1 ball exactly fall onto it.

0 ball in the first box happens with probability $\displaystyle \left(\frac{m-1}{m}\right)^n$

1 ball in the first box happens with probability $\displaystyle n\left(\frac{m-1}{m}\right)^{n-1}$

Thus,

$\displaystyle P(\mbox{there is a collision in the first box})=1-\left(\frac{m-1}{m}\right)^n-n\left(\frac{m-1}{m}\right)^{n-1}. $

and finally

$\displaystyle E[N]=m\left(1-\left(\frac{m-1}{m}\right)^n-n\left(\frac{m-1}{m}\right)^{n-1}\right). $