Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer
    
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
5  
@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}}$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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