A sport card store manager has $ r$ customers, that together wish to assemble a $ n$ -cards collection. Every day, a random customer arrives and buys his favorite card (that is, each customer is associated with a single card), even if it has purchased the same card before. How many days will past before the customers complete their collection?
Formally, let $ n\le r$ be integer parameters, and let $ h:[r]\to [n]$ be a random projection from $ [r]$ to $ [n]$ (i.e., it maps every element uniformly and independently). How many random samples (with replacement) $ (x,h(x))$ to we need to get before we see all $ n$ values possible for $ h$ ?
Clearly, there is some chance that $ h$ is not onto and thus the expectation of the required number is not bounded.
I’m interested in a bound of the form:
- After $ T(r,n,\delta)$ samples, with probability at least $ 1-\delta$ , we have seen all possible $ n$ values.
For example, if $ r=3,n=2$ , we have a probability of $ 1/4$ that $ h$ is not onto, and if it is, then after collecting $ 4$ cards, the chance of not seeing all $ h$ values is $ (1/3)^4+(2/3)^4\le 0.21$ . This means that $ T(3,2,0.46)=4$ is a correct upper bound.