2
$\begingroup$

The Coupon Collector Problem is a well-known one in mathematics and statistics.

The problem assumes that all unique coupons are equally likely a priori and gives the expected (mean) number of coupons needed to be collected in order to observe one of each unique type.

The solution is:

$N = n(ln(n) + \gamma) + \frac{1}{2}$,

where $n$ is the number of unique coupons and $\gamma$ is the Euler-Mascheroni constant. $ln$ is the base of the natural logarithm.

My intrigue concerns the case where coupons are not equally likely. Further, suppose one does not know the frequencies of all unseen unique types, but can estimate the total number of unique types (both seen and unseen).

For example, suppose one collects 50 objects, of which 5 are unique. The person surmises that there are a total of 10 unique objects (thus, they need to observe 5 more unique objects). However, the frequencies at which these 5 unseen unique objects occur is NOT known beforehand.

To me, finding a solution (either a closed-form formula or via simulation) to such a problem would be very challenging, if possible at all. One can only make the claim that unseen unique types are likely very rare (low probability of detection).

Has anyone or can anyone here propose(d) a way forward?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ On what basis does one "surmise there are a total of 10 unique objects" upon observing only five types of objects among 50? Of course you cannot find a solution per se, but can only make an estimate--and there's no reasonable upper bound to that estimate, because there could be arbitrarily many objects having vanishingly small probabilities. What, then, do you mean by "a way forward" exactly? $\endgroup$
    – whuber ♦
    Commented Jul 27, 2018 at 17:21
  • $\begingroup$ Note that the solution above is not for how many coupons need to be collected to observe one of each unique type, but for the expected number of coupons that will need to be collected to observe one of each type. $\endgroup$
    – jbowman
    Commented Jul 27, 2018 at 18:20
  • $\begingroup$ @jbowman Corrected - thanks! Completely glossed over that detail. $\endgroup$
    – compbiostats
    Commented Jul 27, 2018 at 18:21
  • $\begingroup$ @whuber Apologies, your correct in that it is unclear - What I mean by "a way forward" is whether any further assumptions must/should be made for a finite solution to exist. For instance, perhaps each unobserved object only occurs once in an infinitely large population. In fact, this very example is the worst-case scenario. $\endgroup$
    – compbiostats
    Commented Jul 27, 2018 at 18:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.