Number of unique elements in new set

Question

Suppose that we have a set with n elements. Choose at random with replacement any n elements. I.e create new empty set and n times add to this set element from old set (there can be repetitions). How asymptotically many unique elements are there in new set? Any hints?

Answer 1

I'm not completely sure I understand what you are asking, but I think it is this. We sample a set of $n$ elements uniformly at random, with replacement, $n$ times. What is the expected number of distinct elements in the sample? Give an asymptotic value as $n\to\infty.$

For $i=1,2,\dots,n$ let $X_i$ be a random variable whose value is $1$ if element $i$ appears in the sample and $0$ otherwise, and let $X=\sum_{i=1}^nX_i$. Then we want $$E(X)=E\left(\sum_{i=1}^nX_i\right)=\sum_{i=1}^nE(X_i)=n\left(1-\left({n-1\over n}\right)^n\right)\sim n\left(1-\frac1e\right)$$ as $n\to\infty$.