Given the set of numbers from 1 to n: { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw?
I came across this question on Brainstellar. I have understood a way to solve this problem using Stack Exchange but I am not able to understand the fault in my methods.
$X_i$ represents if I have picked up a unique number on the $i^{th}$ pick. Naturally,
$X_i$
= 1 when I have picked up a number that was not picked earlier.
= 0 when I have picked up a number that was already picked earlier.
$E[\sum_{i=0}^n X_i]$ should be my answer to the problem. $E[X_1] = 1$ as I would definitely pick a unique number on the first trial.
$E[X_i] = \frac{(n-1)^{i-1}}{n^{i-1}}$ where $i \neq 1$
The first part is the probability that in the $i-1$ trials a particular number was never picked. This is how I got the $E[X_i]$.
Now all i need to do is $1 + \sum_{i=2}^n E[X_i]$
And what I get is $$1 + \frac{(n-1)}{n} + \left(\frac{(n-1)}{n}\right)^n$$
I am not able to find the folly in this approach.
PS: I am not a maths student so kindly forgive any silly mistakes you might find. I have been struggling for hours trying to find the mistake but to no avail.
Ok I have figured it out.
Mistake made: I tried adding $1$ even after summing over from $i$ = 1 to $i = n$
Also the E[$X_i$] was calculated wrong the first time as $\frac{1}{n}$$\left(\frac{(n-1)}{n}\right) ^ {i-1}$
Correct value is E[$X_i$] = $\left(\frac{(n-1)}{n}\right) ^ {i-1}$
So the answer is $\sum_{i=1} ^n \left(\frac{(n-1)}{n}\right) ^ {i-1}$
The answer is $n$$\left(1 - \left(\frac{(n-1)}{n}\right) ^ {n}\right) $
Thanks to @lulu in the comments for pointing out