16
$\begingroup$

I've seen many variations of this problem but I can't find a good, thorough explanation on how to solve it. I'm not just looking for a solution, but a step-by-step explanation on how to derive the solution.

So the problem at hand is:

You have m balls and n bins. Consider throwing each ball into a bin uniformly and at random.

  • What is the expected number of bins that are empty, in terms of m and n?
  • What is the expected number of bins that contain exactly 1 ball, in terms of m and n?

How would I approach solving this problem?

Thanks!

2 Answers 2

26

You want to use what are called indicator variables. To see how this works, let's take your first problem. Let $Y$ be the number of bins that are empty. You want $E[Y]$. Now define the indicator variables $X_i$ so that $X_i$ is $1$ if bin $i$ is empty and $0$ otherwise. Then we have

$Y = X_1 + X_2 + \cdots + X_n.$

By linearity of expectation,

$E[Y] = E[X_1] + E[X_2] + \cdots + E[X_n].$

So now the problem reduces to calculating the $E[X_i]$ for each $i$. But this is fairly easy, as $E[X_i] = 1 P(X_i = 1) + 0 P(X_i = 0) = P(X_i = 1) = P(\text{bin $i$ is empty}) = \left(1 - \frac{1}{n}\right)^m,$ where the last equality is because balls $1, 2, \ldots, m$ must all go in a bin other than $i$, each with probability $1 - \frac{1}{n}$.

Therefore, $E[Y] = n \left(1 - \frac{1}{n}\right)^m.$

Your second problem can be worked in a similar fashion. Let $Y$ be the number of bins that have exactly $1$ ball. Let $X_i$ be $1$ if bin $i$ has exactly one ball and $0$ otherwise. Then all that's left is to figure out $E[X_i]$, which is the probability that a given bin has exactly $1$ ball, and go from there. Since this is homework, I'll let you finish.

  • 0
    @MikeSpivey How to approach if it's asked to calculate the variance?2017-08-15
5

Let's work out the probability there are $k$ balls (out of $m$) in the first bin (out of $n$). This is a simple binomial probability with $p=1/n$ and $1-p = (n-1)/n$ so the probability is ${m \choose k} \dfrac{(n-1)^{m-k}}{n^m}$.

The expected number of times the first bin has $k$ balls is the same, so the expected number of bins with $k$ balls is $n$ times this, i.e.

${m \choose k} \dfrac{(n-1)^{m-k}}{n^{m-1}}$

  • 0
    $Pr(K=k|m,n)$ $ = {m \choose k} \left(\dfrac{1}{n}\right)^k \left(\dfrac{n-1}{n}\right)^{m-k}$ $ = {m \choose k} \dfrac{1}{n^k} \cdot \dfrac{(n-1)^{m-k}}{n^{m-k}}$ $ = {m \choose k} \dfrac{(n-1)^{m-k}}{n^m}$2011-04-08