Suppose that we toss balls into four bins until some bin con

Suppose that we toss balls into four bins until some bin contains three 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?

Solution

Eb is the expected number of trials for b bins:

E1 = 1 + 1/1
E2 = 1 + 2/2 + 2/4
E3 = 1 + 3/3 + 6/9 + 6/27
E4 = 1 + 4/4 + 12/16 + 24/256

and so on. That is, in general:

Eb = 1 + b/b + b*(b-1)/b^2 + .... + b!/b^b