5
$\begingroup$

Suppose that there are $n$ different coupons, equally likely, from which coupons are being randomly drawn with replacement. Find the expected number of draws for some coupon to be drawn twice.

I've attempted to solve this from the basic definition of expectation. If $N$ is a randomly variable for the number of draws for some coupon to be drawn twice, then $1\lt N\le n+1$ and

$$ E[N]=\sum_{i=2}^{n+1} n*Pr(N=n)\\ =2*\left(\frac{1}{n}\right)+3*\left(\frac{n-1}{n}\right)\left(\frac{2}{n}\right)+4*\left(\frac{n-1}{n}\right)\left(\frac{n-2}{n}\right)\left(\frac{3}{n}\right)+... $$

(Sorry for not finishing the equation, hopefully you get the idea, it goes up to $n+1$, my latex maths is pretty crap.)

Is this correct? How do I evaluate this sum or is there a closed-form solution to this sum? Is there a better way to solve this?

$\endgroup$
  • 1
    $\begingroup$ The material in the referred to question is relevant but quite different. For one thing, it is concerned with the expected number of draws in order to get two pairs of duplicates, not $1$. $\endgroup$ – André Nicolas Jun 3 '13 at 18:51
  • 1
    $\begingroup$ Wikipedia gives an expression for the mean number needed in the birthday problem. It is not in a closed form. $\endgroup$ – Henry Jun 24 '13 at 23:08
  • 1
    $\begingroup$ You never use the index $i$. I'm guessing some of those $n$s should be $i$s. $\endgroup$ – dfeuer Jun 25 '13 at 4:00
4
$\begingroup$

\begin{align} E[N]&=\sum_{k=0}^n\textsf{Pr}(N\gt k)\\ &=\sum_{k=0}^n\frac{n!}{(n-k)!n^k}\\ &=\sum_{k=0}^n\frac{n!}{k!n^{n-k}}\\ &=\frac{n!}{n^n}\sum_{k=0}^n\frac{n^k}{k!}\\ &\sim\frac{n!}{n^n}\frac{\mathrm e^n}2\\ &\sim\sqrt{\frac{\pi n}2}\;, \end{align}

where the first approximation takes the terms of the exponential series to be approximately symmetric about its maximum at $k=n$, and the second approximation is Stirling's. According to Wikipedia, the next term in the expansion in terms of $\sqrt n$ is $-\frac13$.

$\endgroup$
  • $\begingroup$ Though you also need to add $1$ $\endgroup$ – Henry Nov 16 '16 at 21:56
  • $\begingroup$ @Henry: True, thanks. So the next term in the expansion is actually $+\frac23$. $\endgroup$ – joriki May 30 '18 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.