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?
$\endgroup$3 Answers
$\begingroup$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).
$\endgroup$ 1 $\begingroup$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}}.$$
$\endgroup$ 2 $\begingroup$I suggest looking at this Related Problem
As the suggested answer in that related problem states, credit to user Henry.
$\endgroup$ 2This 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$.
