4
$\begingroup$

In the classic Coupon Collector's problem, it is well known that the time $T$ necessary to complete a set of $n$ randomly-picked coupons satisfies $E[T] \sim n \ln n $,$Var(T) \sim n^2$, and $\Pr(T > n \ln n + cn) < e^{-c}$.

This upper bound is better than the one given by the Chebyshev inequality, which would be roughly $1/c^2$.

My question is: is there a corresponding better-than-Chebyshev lower bound for $T$? (e.g., something like $\Pr(T < n \ln n - cn) < e^{-c}$ ) ?

  • 0
    also asked at http://stats.stackexchange.com/questions/7774/what-is-a-tight-lower-bound-on-the-coupon-collector-time and discussed at http://meta.math.stackexchange.com/questions/1733/what-is-the-proper-way-to-acknowledge-an-answer-posted-on-another-forum-site2011-03-03

1 Answers 1

2

The question was asked and answered at stats.SE: see https://stats.stackexchange.com/q/7774/. I am posting this just so that the question does not remain unanswered.