How can I solve bins-and-balls problems?

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?

Solution 1:

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).

Solution 2:

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

Solution 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$.