Expected number of bags to get one ball of each color

84 Views Asked by At

There are bags with n balls, and each ball can have any of the n different colors with equal probability. A bag can contain each color multiple times. What is the expected number of bags until we get at least one ball of each color?

The closest problem I could find is the coupon collector's problem, but in that problem you buy the boxes one by one, whereas in this problem you can only select a multiple of n balls.

What I got so far is the expected number if we are only interested in getting one specific color $i$, which would then have a geometric distribution with $p=1-(\dfrac{n-1}{n})^n$, since getting color $i$ in a bag would be the complement of getting n balls with a color other than $i$, but I feel like this not the right direction.

1

There are 1 best solutions below

3
On

NOTE

OP has modified the question after the answer was posted so that now it is a well known coupon collector problem with multiple coupons in each packet. The answer below addresses what I understood to be the original query


It is always good to change abstract problems so that they come within the milieu of familiar types.

So consider, as a parallel for one bag, that a normal die is thrown $6$ times, what is the probability that you get each number exactly once ?

You will immediately say, $Pr = \Large\frac{6!}{6^6}$, won't you ?

So for $n$ colors, for any particular bag, $Pr = \Large\frac{n!}{n^n}$

and applying linearity of expectation, we just multiply the above expression by $b$, the number of bags.