# Hashes coupon collector

The story:

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.