Balls and bins problem from 'introduction to algorithms' textbook

[mikepol]

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!

 

[CRGreathouse]

The probability that all bins will have at most one ball can be computed by a simple product. The product can then be re-expressed in terms of factorials and powers.

 

[mikepol]

Thanks for your fast reply CRGreathouse! I have tried the way you suggested, but still a closed form solution evades me! Here is my analysis:

First, I think the problem is stated a little ambiguously, so this is my understanding on it. Suppose I perform the following experiment: take b empty bins and start tossing balls into them at random. As soon as a ball lands in already occupied bin, I record the number of throws I had made. The problem asks to find the expected number these recorded numbers, which will be the average over this experiment performed great many times. In other words, I need to find the expected number tosses before a collision occurs.

I have approached this from two paths.
First way is define a random variable X such that event X=k means that after k-1 tosses, there were no collisions, but k'th toss resulted in a collission. In other words, X=k is the event that k'th toss results in a single bin having two balls, while all the rest have at most one. Then probability of X=k is:

$$P(X=k) = \frac{(b)_{k-1}(k-1)}{b^k}$$

 

[mikepol]

Sorry, please disregard my previous post, I hit submit by mistake.

Thanks for your fast reply CRGreathouse! I have tried the way you suggested, but still a closed form solution evades me! Here is my analysis:

First, I think the problem is stated a little ambiguously, so this is my understanding of it. Suppose I perform the following experiment: take b empty bins and start tossing balls into them at random. As soon as a ball lands in already occupied bin, I record the number of throws I had made. The problem asks to find the expected value of these recorded numbers, which will be the average over this experiment performed great many times. In other words, I need to find the expected number of tosses that result in a single collision on the last toss.

I have approached this from two paths.

First way is define a random variable X such that event X=k means that after k-1 tosses, there were no collisions, but k'th toss resulted in a collission. In other words, X=k is the event that k'th toss results in a single bin having two balls, while all the rest have at most one. Then probability of X=k is:

$$P(X=k) = \frac{(b)_{k-1}(k-1)}{b^k}$$

Where $$(b)_{k}=\frac{b!}{(b-k)!}$$. And the expected value that the problem is to compute is:

$$E(X) = \sum_{k=2}^{b+1} kP(X=k) = \sum_{k=2}^{b+1} \frac{(b)_{k-1}(k-1)}{b^k}k$$

This is a solution in a form of a sum.

From the fact that X is a random variable and that it takes values from 2 to b+1, we also have:

$$\sum_{k=2}^{b+1}P(X=k) = \sum_{k=2}^{b+1}\frac{(b)_{k-1}(k-1)}{b^k} = \frac{1}{b}\sum_{k=1}^{b}\frac{(b)_{k}k}{b^k}=1$$

A second way of getting an answer is define an indicator random variable $$I_{k}$$ such that the event $$I_{k}=1$$ means that there was k'th toss, and define $$I_{k}=0$$ otherwise. In other words, it means that previous tosses have resulted in no collisions, and therefore we made k'th toss, the result of which is unknown. The probability of this event is equals to the probability that previous k-1 tosses had no collisions. It is:

$$P(I_{k}=1) = \frac{(b)_{k-1}}{b^{k-1}} = E(I_{k})$$

And random variable X can be expressed in terms of I's:

$$X=\sum_{k=1}^{b+1}I_k$$

So by linearity of expectations we have:

$$E(X)=\sum_{k=1}^{b+1}E(I_k) = \sum_{k=1}^{b+1}\frac{(b)_{k-1}}{b^{k-1}} = \sum_{k=0}^{b}\frac{(b)_k}{b^k}$$

And I can show that this formula for E(X) is consistent with previous formula for E(X) by direct derivation:

$$\sum_{k=1}^{b+1}\frac{(b)_{k-1}(k-1)}{b^k}k = \sum_{k=1}^{b}\frac{(b)_{k-1}}{b^{k-1}}k - \sum_{k=1}^{b}\frac{(b)_k k}{b^k} + \frac{b! b (b+1)}{b^{b+1}} = \sum_{k=1}^{b-1}\frac{(b)_k}{b^k}(k+1) - \sum_{k=1}^{b}\frac{(b)_k k}{b^k} + \frac{b! (b+1)}{b^b} = \sum_{k=1}^{b-1}\frac{(b)_k}{b^k} + \frac{b!}{b^b} = \sum_{k=1}^{b}\frac{(b)_k}{b^k}$$

But I still don't have a closed form solution! This problem has been annoying me for about a day already. I think the authors wouldn't put this with other simple problems if it wasn't relatively simple to solve, so I still believe that a closed form solution is out there. Does anyone have any ideas?

Thank you.

 

[CRGreathouse]

Chance of all bins having at most one ball:
Turn 1, 1
Turn 2, 1 - 1/b
Turn 3, (turn 2) * (1 - 2/b) = (1 - 1/b)(1 - 2/b)
Turn 4, (turn 3) * (1 - 3/b) = (1 - 1/b)(1 - 2/b)(1 - 3/b)
etc.

 

[mikepol]

Thanks CRGreathouse.

The formula for all b bins having at most 1 ball after k tossings that you wrote is:

$$\frac{(b)_k}{b^k}$$

So the probability that at least one collision occurs in k throwings (that at least one bin will contain at least two balls) is:

$$1-\frac{(b)_k}{b^k}$$

But that probability is not related directly to this problem since the collision does not necessarily occur at the k'th toss and there might be more than one bin with at least two balls or bins with more than two balls.

I think the problem is asking for probability of the first and only collision in k throws to occur on the last toss. In other words, after k-1 throws there were no collisions, but k'th throw resulted in a collision. Thus, there is only one bin with two balls, and the second ball in that bin resulted from the last toss. The probability of this event is:

$$\frac{(b)_{k-1}(k-1)}{b^k}$$

And then the expected number of throws that the problem is asking for would be:

$$E(X) = \sum_{k=1}^{b+1} \frac{(b)_{k-1}(k-1)}{b^k} k$$

But now I don't know how to express this in closed form, if that is at all possible. I also have another expression for E(X) as a sum in my previous post, but that does not help me either.

Any other ideas?

Thanks.

 

[Focus]

$$E(X) = \sum_{k=1}^{b+1} \frac{(b)_{k-1}(k-1)}{b^k} k$$

But now I don't know how to express this in closed form, if that is at all possible. I also have another expression for E(X) as a sum in my previous post, but that does not help me either.

Any other ideas?

Thanks.

Sorry but your answer is already in closed form. Why doesn't this help you?

 

[mikepol]

Hi Focus, thanks for pointing this out.

Sorry for the confusion, I didn't use this term in a prcise way. What I want is get rid of the sum. However, factorials are still allowed. Is this possible for this problem?

Thanks!

 

[CRGreathouse]

But that probability is not related directly to this problem since the collision does not necessarily occur at the k'th toss and there might be more than one bin with at least two balls or bins with more than two balls.

Pr(collision in exactly k turns) = Pr(collision happens in at most k turns) - Pr(collision happens in at most k-1 turns)