Let $I=\{1,2,\ldots, 1000\}$. Let $A$ be an empty set. I take a random integer from $I$ with replacement and put in $A$. I do this process 1000 times. What is the expected size of $A$?
This is my approach.
Let $X_i$ be binary random variable which takes 1 iff $i$-th integer is different from previous drawn integers.
Then probaility of $X_i=1$ is $\frac{1000-(X_1+\ldots+X_{i-1})}{1000}$. Then our target is to find $\sum_{i=1}^{1000} E(X_i)$.
Definitely $E(X_1)=1$, $E(X_2)=\frac{999}{1000}$ etc. I would like to know whether this approach is correct. I know this problem is very close to coupan collector problem.
I think another idea. Let $X_i$ be the number of different intger upto $i$-th round. Then $X_{i+1}$ becomes $1+X_i$ with probability $\frac{1000-X_i}{1000}$. I am trying some recursive relation.
