- #1
mikepol
- 19
- 0
Hi Everyone,
I've been trying to do the following problem, which is exercise 5.4-2 in "Introduction to Algorithms 2ED" textbook by Cormen/Leiserson/Rivest/Stein. It's not starred, so should be fairly easy, but I just can't come up with a closed form solution! The problem is:
Suppose that balls are tossed into b bins. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses before at least one of the bins contains two balls?
I have a solution (which I'm pretty sure is correct), but in a form of a sum. Can anyone give me a little hint of how to get a closed form solution or even if a closed form solution is possible?
Thanks in advance!
I've been trying to do the following problem, which is exercise 5.4-2 in "Introduction to Algorithms 2ED" textbook by Cormen/Leiserson/Rivest/Stein. It's not starred, so should be fairly easy, but I just can't come up with a closed form solution! The problem is:
Suppose that balls are tossed into b bins. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses before at least one of the bins contains two balls?
I have a solution (which I'm pretty sure is correct), but in a form of a sum. Can anyone give me a little hint of how to get a closed form solution or even if a closed form solution is possible?
Thanks in advance!