I am given $n$ balls. For $n$ times, I pick one of them with uniform probability and put it back after picking it.
Let $U$ be the number of balls I have never picked, so $U\in \{0,\ldots,n-1\}$. We are interested in the expected value $E_n:= E(U)$.
What is the value of $\lim_{n\to\infty} \frac{E_n}{n}$, if it exists?
(This is a follow-up question to this question.)
When tossing $n$ balls uniformly and independently into $n$ bins, the distribution of the number of balls in any specific bin is binomial with parameters $n$ and $p=\frac{1}{n}$. Thus, the probability that a bin is left empty is $(1-\frac{1}{n})^n$, which tends to $\frac{1}{e}$. By linearity, the expected number of empty bins is $n (1-\frac{1}{n})^n \approx \frac{n}{e}$.
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$.
