5.4-2

5.4-2 Suppose that we toss balls into b bins until some bin contains two balls. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses?
To solve this lets take an example where we have 4 bins:
[] [] [] []
A bin can contain two balls only after two throws. Let $X_i$ be the variable when a bin contains two throws. Let X be a variable that counts no of bins that have two balls. So lets start at 2 throws It doesn't matter if the first throw hits any of the three boxes but the second throw has to hit the same box if a bin has to contain two balls.
Probability for bin to have two balls after two throws is 1 (first throw). 1/4(second throw the probability of hitting the first bin that has ball)
First throw can land in any of the 4 bins:
[B] [] [] []
[] [B] [] []
[] [] [B] []
[] [] [] [B]
the second throw has to land on any of the above 4 bins.
the final probability: 1 .1/4 (since the above events are independent)
for 3 throws:
First throw can land in any of the 4 bins:
[B] [] [] []
[] [B] [] []
[] [] [B] []
[] [] [] [B]
the second throw has to land on any of the above 3 bins other than the one containing the ball.
[B] [B] [] [] Or
[] [B] [B] [] Or
[] [B] [B] [] Or
[] [] [B] [B]
The probability is for second throw is 3/4.
The third throw has to land in any of two bins containing balls hence 1/2 (2 out of 4 bins)
The final probability: 1.3/4.1/2
for four throws:
for second throw the probability is: 3/4
for third throw we have two empty bins the probability is: 1/2
for fourth throw it has to fall in either of three bins containing a ball : 3/4
The final probability: 1.3/4.1/2.3/4
for five throws:(This is the final case since even 4 throws make it to distinct bins the fifth has to make one of the four to make the count to 2)
for second throw the probability is: 3/4
for third throw we have two empty bins the probability is: 1/2
for fourth throw it has to fall final empty bin : 1/4
for fifth throw it can fall in any bin to make the no of balls in a bin to 2 : 1
The final probability: 1.3/4.1/2.1/4 $$E[X] = 2 * 1 .1/4 + 3 * 1.3/4.1/2 + 4 * 1.3/4.1/2.3/4+ 5 * 1.3/4.1/2.1/4.1 $$ The above equation is of the form $$E[X] = \sum_{k=2}^b+1 k (k-1) b.(b-1)...(b-k+1)/b^k $$ The above sum is the no of throws in which we can get two balls in a bin.