1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I think I must be missing something; how do you get $(1/3)^4 + (2/3)^4$? All probabilities should be dyadic, right? $\endgroup$
    – user44191
    Commented Jun 16, 2019 at 2:25
  • $\begingroup$ @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. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Jun 16, 2019 at 16:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Jun 16, 2019 at 16:08
  • $\begingroup$ @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). $\endgroup$
    – John D
    Commented Jun 16, 2019 at 20:44
  • $\begingroup$ Given a particular $h$ function, so you have values $K_1, ..., K_n$ that specify the number of customers who like each card $\{1, ..., n\}$, you can get a simple exact answer if you change the problem to assume each of the $r$ customers arrives according to an independent Poisson process of rate $\lambda$. $\endgroup$
    – Michael
    Commented Aug 7, 2019 at 6:15

0

Reset to default

You must log in to answer this question.