Return to Revisions

This is related to the coupon collector problem. Let $T_i$ be a geometric variable with parameter $1-i/n$, so that $ET_i=1/(1-(i-1)/n)$. You are asking about $K=\min\{k:\sum_{i=1}^k T_i>n\}.$ Since $E \sum_{i=1}^k T_i=n(1/n+1/(n-1)+...+1/(n-k+1))\sim n\log (n/n-k+1)$, we get from concentration that $\log (n/(n-K))\sim 1$, i.e $n-K\sim n/e$. But $E_n=E(n-K+1)/n\sim 1/e$.