5
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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