Coupon Collector's Problem - Extensions and Generalizations

Extensions and Generalizations

Paul Erdős and Alfréd Rényi proved the limit theorem for the distribution of T. This result is a further extension of previous bounds.

$\operatorname{P}(T < n\log n + cn) \to e^{-e^{-c}}, \ \ \text{as} \ n \to \infty.$

Donald J. Newman and Lawrence Shepp found a generalization of the coupon collector's problem when k copies of each coupon needs to be collected. Let T_k be the first time k copies of each coupon are collected. They showed that the expectation in this case satisfies:

$\operatorname{E}(T_k) = n \log n + (k-1) n \log\log n + O(n), \ \ \text{as} \ n \to \infty.$

Here k is fixed. When k = 1 we get the earlier formula for the expectation.

Common generalization, also due to Erdős and Rényi:

$\operatorname{P}(T_k < n\log n + (k-1) n \log\log n + cn) \to e^{-e^{-c}/(k-1)!}, \ \ \text{as} \ n \to \infty.$

Read more about this topic: Coupon Collector's Problem

Famous quotes containing the word extensions:

“If we focus exclusively on teaching our children to read, write, spell, and count in their first years of life, we turn our homes into extensions of school and turn bringing up a child into an exercise in curriculum development. We should be parents first and teachers of academic skills second.”
—Neil Kurshan (20th century)