2
$\begingroup$

There are $n$ balls and $N$ bins.

At each time, a ball is thrown in one bin of $N$ bins at random. This repeats n times. So that in total $n$ balls are thrown into bins.

The question is, on average, how many bins are occupied (with at least one ball in it) in the end.

Thanks.

$\endgroup$
3
  • $\begingroup$ What probabilities do you know how to find (say, the probability that exactly $5$ bins are occupied)? $\endgroup$ Aug 18, 2013 at 19:38
  • $\begingroup$ I am thinking about the average number of bins that are occupied at the end. It can be calculated by multiplying all potential number of occupied bins and their probability. Or if there is another cleverer way around? $\endgroup$ Aug 18, 2013 at 19:44
  • $\begingroup$ There is, as Andre Nicolas shows us, but I find it best to start with wherever we can continue from there. $\endgroup$ Aug 18, 2013 at 19:53

1 Answer 1

5
$\begingroup$

Define indicator random variables $X_i$ by $X_i=1$ if Bin $i$ ends up occupied, and $X_i=0$ if it does not. Let $Y$ be the number of occupied bins. Then $$Y=X_1+X_2+\cdots+X_N.$$ We want to find $E(Y)$.

The probability Bin $i$ is not occupied is $\left(1-\frac{1}{N}\right)^n$. So the probability it is occupied is $1- \left(1-\frac{1}{N}\right)^n$. Thus the mean of each $X_i$ is $1- \left(1-\frac{1}{N}\right)^n$.

By the linearity of expectation, the mean number of occupied bins is $N\left(1- \left(1-\frac{1}{N}\right)^n\right)$.

$\endgroup$
2
  • $\begingroup$ Thanks a lot. Really appreciate it. $\endgroup$ Aug 18, 2013 at 19:53
  • 1
    $\begingroup$ You are welcome. Linearity of expectation often lets us calculate means in situations where going through the probability distribution is either more difficult or totally unfeasible. $\endgroup$ Aug 18, 2013 at 19:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .