# another balls and bins question

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!

-

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.

-
I didn't quite follow how you got the (1-1/n) term and why you raise it to power m? –  Hristo Mar 25 '11 at 3:51
So I explained to myself the (1-1/n) term but I'm still confused on why its raised to power m... –  Hristo Mar 25 '11 at 3:58
@Hristo: The probability that the first ball goes into bin $i$ is $1/n$, so the probability that the first ball goes into a bin other than $i$ is $1 - 1/n$. The probability that the second ball goes into a bin other than $i$ is also $1 - 1/n$. The same is true for the third, and so forth. In order for bin $i$ to be empty, ball $1$ and ball $2$ and ball $3$ and so forth must all be in bins other than $i$. That means you have to multiply $1-1/n$ by $1-1/n$ by $1-1/n$, etc., with a factor of $1-1/n$ for each of the $m$ balls. That's $(1-1/n)^m$. –  Mike Spivey Mar 25 '11 at 3:59
Got it. That makes sense. Now why is that whole thing multiplied by n? Is it because this (1-1/n)^m term can happen for each bin? Since there are n bins, then each has (1-1/n)^m probability to be empty, so you get n*(1-1/n)^m? –  Hristo Mar 25 '11 at 4:06
@Hristo: Yes. Go back to the $E[Y] = E[X_1] + E[X_2] + \cdots E[X_n]$ equation. Since, for each $i$, $E[X_i] = (1-1/n)^m$, we have $E[Y] = (1-1/n)^m + (1-1/n)^m + \cdots + (1-1/n)^m = n (1-1/n)^m$. –  Mike Spivey Mar 25 '11 at 4:22

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

-
can you somehow rewrite the equations? they didn't render well –  Hristo Mar 25 '11 at 18:41
@Hristo: better? –  Henry Mar 25 '11 at 18:46
Yup... much better! Thanks! Now I need to understand it :) –  Hristo Mar 25 '11 at 21:28
@Henry... so I've been trying to understand your solution and I'm not quite sure how you're coming up with m-k as the exponent in the numerator and m-1 as the exponent in the denominator? Also, why do you do m choose k? –  Hristo Mar 25 '11 at 21:56
You have a binomial distribution (with $m$ rather than $n$, and $p=1/n$ and $1-p = (n-1)/n$). $m-k$ is the exponent of $(1-p)$ since $m-k$ balls do not go in the bin. $m-1$ is the exponent of denominator because I multiplied the previous expression by $n$; $m$ had been the denominator exponent because I had $p^n (1-p)^{m-k}$ and $n$ was the denominator of both $p$ and $1-p$. –  Henry Mar 25 '11 at 22:36