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/(k-1))\sim n\log (n/k)$, we get from concentration that $\log n/K\sim 1$, i.e $K\sim n/e$. But $E_n=E(n-K+1)/n\sim 1-1/e$.