7
$\begingroup$

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$
7
$\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$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I made some changes, for example to change nm into $n^m$ $\endgroup$ – Henry Mar 12 '12 at 0:59
  • $\begingroup$ Thanks. I saw that I needed to clean up the formatting, but I had to leave for dinner. $\endgroup$ – Joe Mar 12 '12 at 1:25
2
$\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$
  • $\begingroup$ So, expected number of bins for any case would be n * probability of particular bin ?? $\endgroup$ – John Mar 12 '12 at 1:25
  • 1
    $\begingroup$ @John Yes, by Linearity of Expectation. See David Mitra's answer for more. $\endgroup$ – Austin Mohr Mar 12 '12 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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