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.

Below is the problem that I wanted to solve

When there are $m$ balls and $n$ bins, balls are thrown into bins where each ball is thrown into a bin uniformly at random. What is the expected number of bins that contain strictly more than 1 ball?

What I am understanding so far is that, each ball toss will be independent, and expected number of balls in each basket will be $m/n$. But this does not seem to help me solving the problem.

I heard this is very similar to the birthday problem, but with different number of bins and arbitrary number of balls.

How should I approach solving this problem?

share|improve this question

3 Answers 3

I suggest looking at this Related Problem

As the suggested answer in that related problem states, credit to user Henry.

This answer treats the balls and boxes as distinguishable so each pattern is of equal probability. I doubt there is a practical experiment to test this which does not also have them distinguishable.

The number of ways of putting $m$ balls in $n$ boxes is $n^m$ since each ball can go in any of the boxes.

The calculation for the number of ways of putting $m$ balls in $n$ boxes with each box having at least one ball is more complicated. Let's call it $A(m,n)$. If, when deciding what to do with the last ball, all the other boxes are full, then it can go in any of the $n$ boxes; if however one of the $n$ boxes is empty and the others full then it must go in the empty one. So $$A(m,n) = n A(m-1,n) + n A(m-1,n-1)$$ and clearly $A(m,1) = 1$ (there is only one way with one box) and $A(m,n) = 0$ for $m \le n$. $A(n,n)=n!$ as one would expect.

So the probability that all the boxes have at least one ball is $$ \frac{n! \, S_2 (m,n)}{n^m}.$$

For example, with 3 balls and 2 boxes, this gives $\frac{2 \times 3}{8} = 3/4$.

share|improve this answer
1  
I made some changes, for example to change nm into $n^m$ –  Henry Mar 12 '12 at 0:59
    
Thanks. I saw that I needed to clean up the formatting, but I had to leave for dinner. –  Joe Mar 12 '12 at 1:25

When trying to find the expectation of a "complicated" random variable, you can try using the very useful technique of writing the complicated variable as a sum of simpler variables and using the fact that the expectation of a sum of random variables is the sum of the individual expectations (note this is true of any sum, independence is not needed).

Here, for each $i=1$, $2$, $\ldots\,$, $n$, define the random variable
$$X_i=\cases{1,& if the $i^{\rm th}$ bin contains 2 or more balls,\cr0,&otherwise.}$$

Now let $X$ be the total number of bins that contain two or more balls. Note that $X=\sum\limits_{i=1}^n X_i$.

Using the linearity of expectation: $$ \Bbb E(X)=\sum_{i=1}^n \Bbb E(X_i). $$

Note each $X_i$ is a Bernoulli variable, so $\Bbb E(X_i)=P[X_i=1]$ for each $i$. Moreover, this quantity is independent of $i$.

So, all you have left to do is to find the probability that a particular bin has two or more balls (here, I'd calculate the probability of the complement of this event and subtract from 1).

share|improve this answer
    
Hi David! nice solution, I have asked for a similar problem, math.stackexchange.com/questions/382115/… if you can take a look thanks a lot +1 ! –  dynamic May 5 '13 at 13:50

For a particular bin the probability it has more than one ball is $1$ minus the probability it has no balls or one ball, i.e. $$1-\frac{(n-1)^m}{n^m} - \frac{m(n-1)^{m-1}}{n^m}.$$

The expected number of bins with more than one ball is $n$ times this, i.e. something like $$\frac{n^m-(n+m-1)(n-1)^{m-1}}{n^{m-1}}.$$

share|improve this answer
    
So, expected number of bins for any case would be n * probability of particular bin ?? –  John Mar 12 '12 at 1:25
1  
@John Yes, by Linearity of Expectation. See David Mitra's answer for more. –  Austin Mohr Mar 12 '12 at 1:27

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.