Asymptotics of expected number of draws until repeat

72 Views Asked by At

Suppose there are $n$ distinct balls in a bag and they are drawn with replacement until the first repeat. Let $X$ be the number of balls drawn. I have shown that the distribution is unimodal and that the mode is asymptotically equal to $\sqrt n$. The expectation of the distribution is derived here to be

$$ \sum_{k \ge 0} \binom{n}{k} \frac{k!}{n^k} $$

I believe that this also should asymptotically equal $\sqrt n$ or $C \sqrt n$ for some $C$, and my numerical experiments have confirmed this. Is this true and why?

1

There are 1 best solutions below

1
On BEST ANSWER