Expected number of random choices required to find all combinations

117 Views Asked by At

If I have $n$ urns each containing $m$ distinct items, where the the urns are disjoint sets, and I repeatedly draw an item from each urn with replacement to make an $n$-combination, how many such $n$-combinations would I expect to have to make in order to see every one of the $m^n$ possible $n$-combinations?

1

There are 1 best solutions below

5
On BEST ANSWER

This is a variation of the Coupon Collector's Problem. The expected number of draws will be:

$$m^nH_{m^n}$$

where $H_n$ is the $n$-th harmonic number.