Question : Suppose that n balls are tossed into b bins so that each ball is equally likely to fall into any of the bins and that the tosses are independent.

c) What is the expected number of balls tossed until a particular bin contains a ball?

d) What is the expected number of balls tossed until all bins contain a ball?

My work:

For part (c), I defined a new indicator r.v $X_i$ which takes the value $1$ if all the previous $i$ balls didn't go into the bin and $0$ otherwise. Then it follows that the number of balls tossed until a particular bin contains a ball is:

$X=X_1+X_2+...+X_n+1$. Therefore $E(X)=1+\sum_{i=1}^n{E(X_i)}$. We know that $E(X_i)$ is the expectation that all i balls don't go into that particular bin so we have: $E(X_i)=(\frac{b-1}{b})^i$. So $E(X)=1+\sum_{i=1}^n{E(X_i)}=1+\sum_{i=1}^n{(\frac{b-1}{b})^i}=\sum_{i=0}^n{(\frac{b-1}{b})^i}=b(1-(\frac{b-1}{b})^n)$. Any problems with the answer so far?

(d) I am lost with this one, any hints on a suitable r.v?

  • $\begingroup$ Part $d$ is the Coupon Collector's Problem. $\endgroup$ – lulu Oct 15 '16 at 11:59
  • $\begingroup$ Thanks, I just checked the Wikipedia page and I think I get it. Also, do you think there is any problem with my answer of (c)? $\endgroup$ – AspiringMat Oct 15 '16 at 12:22
  • $\begingroup$ For c, just think of it as a binomial process. Each toss is either a success or a failure, success meaning that your favorite bin gets the ball. The probability of success on a particular trial is $\frac 1b$, so the answer is $b$. $\endgroup$ – lulu Oct 15 '16 at 12:30
  • $\begingroup$ But doesn't your answer assume that this is a geometric distribution when it is not? Since we have only n balls so we eventually HAVE to stop if we don't reach success? For example, if I take the limit of my answer to infinity, it gives me b, however, n is finite here no? $\endgroup$ – AspiringMat Oct 15 '16 at 12:35
  • 1
    $\begingroup$ No. My formula assigns the value $0$ to all the tosses after the first $n$, you assign the value $n+1$. Neither is part of the ordinary definition of expectation...I think mine is more natural, but it's just a definition and we can set it how we like. As you say, you should ask what was intended. $\endgroup$ – lulu Oct 15 '16 at 13:28

Your Answer

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

Browse other questions tagged or ask your own question.