I collect coupons of theoretically $n$ different colours, which come up randomly, one at a time. Up to now, I have collected $c$ coupons in total, falling into $j$ different colour classes. From this data, I may suspect that coupons of different colours have unequal probabilities of appearing, for instance if 50% of the $c$ coupons collected are of only one colour, whereas the remaining 50% correspond to $j-1=20$ other colours. So, I realise that I will probably not have access to extremely rare colours and am interested in either of two quantities: either the smallest number $n_{99\%}$ of colours making up $t=99\%$ of the probabilities, ideally, or the number ${n'}_{\geq{}1\%}$ of colours having a probability larger or equal to $t'=1\%$.

  1. What can we say about $n_{t}$ and ${n'}_{t'}$?
  2. How good is my estimation of the unequal distribution of probabilities among colours (50% for 1, 50% for 20 remaining colours)? I mean that, if $c$ is very large, this estimate is expected to be reliable, whereas it is not if $c$ is low.
  3. Is there a way I can evaluate how close I am from having discovered all $n_{t}$ or ${n'}_{t'}$ colours or, say, half of them?

I know this has been answered in the case where colour classes have the same probability of appearing, but this case is obviously more general and more difficult. In particular, I am aware that this approach is used in language processing (estimating the size of the vocabulary based on a limited sample of words) and in ecology (estimating the number of species based on a limited sample observed), but to the best of my knowledge, there is usually an assumption that all classes are equally likely to be found.

  • 1
    $\begingroup$ (2) is answerable, but (1) and (3) are not, because without making assumptions, there is no upper limit to $n$ and there is no lower limit to the value of $c$ needed even to supply a bound on $n.$ $\endgroup$
    – whuber
    Feb 3, 2022 at 18:41
  • 1
    $\begingroup$ @Stanin Consider what happens as the probabilities of some subset of classes are lowered further and further. You need correspondingly larger and larger $c$ to have any decent chance to see them all. $\endgroup$
    – Glen_b
    Feb 3, 2022 at 23:12
  • $\begingroup$ Yes, I understand. My question 2. is whether and how this can be quantified. If you consider a physical or biological application for instance, it may well be enough to determine that the 99% most relevant colours are likely to be covered by only $n_{99\%{}}$ colours. In particular, the disbalance that I already observe in my samples does inform me that this is more likely than, say, having found a distinct colour for each observation. $\endgroup$
    – Stanin
    Feb 6, 2022 at 14:22

1 Answer 1


As pointed in the comments, the problem as stated is not well defined: it could be for example that $n=1000$ but $900$ of the colors have probabilities $p <10^{-20}$, which is practically indistinguishable from $n=100$ (as long as you don't collect $ \approx 10^{20}$ coupons).

So you will need to reformulate the question to make it well defined. For example you could say that you are only interested in colors with frequencies that are above some threshold - which correspondingly limits the possible number of colors (for example you can have at most 100 colors with $p>0.01$).

Very roughly, you can think of the observed number of coupons with each color as Poissonian and derive the confidence bounds on their frequencies. For example, if you collected a total of 300 then you can say with a certain confidence that $p<0.01$ for any color not observed, and thus that you observed all colors that have $p>0.01$.

  • $\begingroup$ Done. I hope this makes it better formulated. $\endgroup$
    – Stanin
    Feb 8, 2022 at 14:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.