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:

“The psychological umbilical cord is more difficult to cut than the real one. We experience our children as extensions of ourselves, and we feel as though their behavior is an expression of something within us...instead of an expression of something in them. We see in our children our own reflection, and when we don’t like what we see, we feel angry at the reflection.”
—Elaine Heffner (20th century)