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$
  • $\begingroup$ What probabilities do you know how to find (say, the probability that exactly $5$ bins are occupied)? $\endgroup$ – Jonathan Y. Aug 18 '13 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$ – Changwang Zhang Aug 18 '13 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$ – Jonathan Y. Aug 18 '13 at 19:53
3
$\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$
  • $\begingroup$ Thanks a lot. Really appreciate it. $\endgroup$ – Changwang Zhang Aug 18 '13 at 19:53
  • $\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$ – André Nicolas Aug 18 '13 at 19:57

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.