9
$\begingroup$

The coupon collector's problem

Let there be $n$ different types of coupons and we try to collect all of the types.

We do this by independent random draws of coupons in which each type of coupon has an equal probability, $1/n$, to be drawn.

How many draws $k$ do we need to collect all coupons?

What is the probability distribution of the variable $K$?

Solution

  • The distribution of $K$ follows the distribution $$P(K \leq k) = \frac{k!{{n}\brace{k}}}{k^n}$$ where ${{n}\brace{k}}$ are Stirling numbers of the second kind.

  • The distribution can also be seen as the distribution of the sum of independent geometric distributed variables. $$K = \sum_{i=1}^{n} X_i \qquad \text{with $X_i \sim Geom(p = i/n)$} $$

Problem of this question

We can approximate the above results with a Gumbel distribution.

  • I have found in a section of the Wikipedia page that several people found the limiting distribution $e^{-e^{-c}}$, but no resources are given.
  • In 'asymptotics of the Stirling number of the second kind revisited' by Guy Louchard it is stated on page 196 that Erdõs and Szekeres came with a an approximation for the Stirling number of the second type in the form of $e^{-e^{-c}}$. But the resource points to page 164 in Sachkov's book 'probabilistic methods in combinatorial analysis' and I can not track down the original source (and there is a lot to search through).
  • The article from Lars Holst, 'Extreme value distributions for random coupon collector and birthdays problems', is getting close to what I am searching for. But it still becomes quite technical.

So, what I am trying with this question is prove that the coupon collector's problem approaches the Gumbel distribution. Potentially, make it also intuitive why it is a type of extreme value distribution that is the limiting distribution. Is there a relation with extreme values? Or do extreme values and these types of combinatorial problems for some reason have similar behavior in the limit?

I have tried to manipulate the characteristic function of the sum of geometric variables but got stuck there. Maybe I have to dig harder or try some other route.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Doesn't this come down to a direct application of the Fisher-Tippett-Gnedenko theorem? $\endgroup$
    – whuber ♦
    Commented Oct 7, 2021 at 13:29
  • $\begingroup$ Fair enough. I just looked at the abstract of Holst's paper--it sketches the connection. $\endgroup$
    – whuber ♦
    Commented Oct 7, 2021 at 13:40

1 Answer 1

Reset to default
5
$\begingroup$

Below is a bastardized short version of the connection made in the paper by Holst:

The connection with the Gumbel distribution is made with the following steps...

  • Viewing the waiting time to collect all the coupons by the individual waiting times to collect each individual coupon.
  • The waiting time to collect all coupons is the maximum of these individual waiting times.
  • The individual waiting times are approximately independent and exponential distributed (this independence is still fuzzy to me).
  • Then the waiting time to collect all coupons approaches an extreme value distribution. Since the distributions involved are approximately exponential distributions, the limiting distribution will be a Gumbel distribution.

An illustration relating to Holst's approach in this post on mathematics.

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1 Sextus Empiricus, Can you say a little about your fuzziness regarding the independence of the argument about individual waiting times (of each coupon) being approximately independent (and exponentially distributed)? The notion that the coupon problem can be conceived of as sampling with replacement makes me hunch at independence, so I would love to learn why that might not be the case. $\endgroup$
    – Alexis
    Commented Nov 30, 2021 at 17:31
  • 1
    $\begingroup$ @Alexis I made an illustration relating to Holst's approach in this post on mathematics. It may help to explain the difference. In this approach, the variables are considered as a Poisson process and in that case, the connection between the 'watining time' and the 'extreme value' is very clear and without any troubles.... $\endgroup$
    – Sextus Empiricus
    Commented Nov 30, 2021 at 19:57
  • 1
    $\begingroup$ ... the trouble with the Birthday problem is that it is not like that Poisson noise. The waiting time is in the number of coupons, with the Poisson process the waiting time is the unit of time. After waiting for one coupon, it is certainly gonna give you a coupon (so that's the dependence; if one box is without coupons this increases the probability of another contacting is). With the Poisson process, after waiting one unit of time, you may have a different number of coupons.... $\endgroup$
    – Sextus Empiricus
    Commented Nov 30, 2021 at 20:05
  • 1
    $\begingroup$ --- But, this is just fuzzy. Intuitively I see these problems disappear for a larger number of coupons. The exponential distribution for the Poisson process and the geometric distribution for the coupons are gonna be very close to each other. In addition the 'Poissonation' and approximation of the coupons as independent Poisson processes exponential variables becomes better when the number of coupons is very large. $\endgroup$
    – Sextus Empiricus
    Commented Nov 30, 2021 at 20:08

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.