# Hashed 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 both 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.

• I think I must be missing something; how do you get $(1/3)^4 + (2/3)^4$? All probabilities should be dyadic, right? – user44191 Jun 16 at 2:25
• @user44191: The random customers could either all be the one customer, that likes card 1, or all of them could be one of the two customers, who like card 2. – Jan-Christoph Schlage-Puchta Jun 16 at 16:00
• For any given map $h$ the probability can be computed by a weighted coupon colector problem. The distribution of $h$ can also be computed. The combination of both counting problems can become quite difficult, depending on what parameter range and what accuracy you look at. If $\delta$ is much bigger than the probability that $h$ is not surjective, you can neglect all "strange" partitions occurring as pre-image of $h$, and some standard coupon collector results suffice. If $\delta$ is close to that probability, the problem will become pretty difficult. – Jan-Christoph Schlage-Puchta Jun 16 at 16:08
• @Jan-ChristophSchlage-Puchta- I had hard times deriving any bound that I can work with by looking at all possible $h$ values. I'm also not looking for a tight bound, just some rough estimate on how this behaves would do, even in the case where the probability of being surjective is large. Specifically, I have $r\gg n$, and $\delta$ that can be a relatively large constant (say, 1/3). – John D Jun 16 at 20:44