# Probability of throwing balls into bins.

Suppose we have $M$ balls placed randomly into $N$ boxes, wherein each ball has an equal chance of landing in each bin. How would we go about finding the expected number of balls in the first box?

I assumed we could use a binomial distribution, wherein we would regard a ball being thrown into the first box as a success, and the probability of success is $1/N$. Hence, from this, the expected value of balls in the first box is $M/N$. Is this a correct approach?

• Do you mean 1/N and M/N? – Marcus Andrews Apr 10 '15 at 13:46
• My mistake, I have altered the question now. – FinneganJ Apr 10 '15 at 13:50

One way to verify the result:

Let $E_N(M)$ be the expected number of balls in the first bin given $N$ bins and $M$ balls, where $E_N(0) = 0$. When allocating a single ball, there is a $\frac{1}{N}$ chance of it going to any particular fixed bin. For a given trial, there are two outcomes: Either a ball goes to the first bin and we add one to the desired total, or it goes somewhere else and we add nothing. Either way, we start over with $M-1$ balls.

$$E_N(M) = \frac{1}{N}(1 + E_N(M-1)) + \frac{N-1}{N}(E_N(M-1)) = \frac{1}{N}+E_N(M-1)$$

In other words:

$$E_N(M) = \sum_{k=1}^{M} \frac{1}{N} = \frac{M}{N}$$

Number the $M$ balls with each integer $i$ from $1$ to $M$, inclusive.

The first ball can either be in the first box, with probability $1/N$, or not, with probability $1-1/N$. The expected number of copies of the first ball in the first box is thus $$E_1 = 1(1/N) + 0(1-1/N) = 1/N$$

This reasoning works for all of the $i$ (there is nothing special about the first ball). Further, since the placements of the balls are physically independent events, they must be mathematically independent, so we may simply add the $E_i$:

$$\displaystyle\sum_{i=1}^M E_i = \frac{M}{N}$$

let $E_j$ be the expected number of balls in the $j^{th}$ box. then by symmetry $E_i=E_j$. also
$$\sum_{i=1}^N E_i = M$$