Uniques out of bag

Let X to be the number of unique values in the sequence. We want to compute $E[X/n] = E[X]/n$ .

We can write X as a sum of indicator functions: $X = \sum_{i=1}^{n} \mathbb{I}(i \text{ occurred once})$ . The expectation then:

$E[X]/n = \frac{1}{n}\sum_{i=1}^nE[\mathbb{I}(i \text{ occurred once})] = \frac{1}{n}\sum_{i=1}^nP(i \text{ occurred once}) =$ $= \frac{1}{n}\sum_{i=1}^nP(1 \text{ occurred once}) = P(1 \text{ occurred once})$ .

If value 1 has occurred only at one place in the sequence of recorded numbers, there are $n$ possible slots for it. There are $n-1$ slots remaining to be filled with any of the $n-1$ values (excluding $i$ ). So we have $n(n-1)^{(n-1)}$ possibilities when $i$ is unique for any $i$ . The total number of ways to record $n$ numbers is $n^n$ . Therefore, $P(1 \text{ occurred once}) = \frac{n(n-1)^{(n-1)}}{n^n} = (1-1/n)^{n-1} = E[X]/n$ .

Take limit: $\lim_{n \to \infty}(E[X]/n) = e^{-1}$ .

Bonus problem: Same approach: $X = \sum_{i=1}^{n} \mathbb{I}(i \text{ not observed})$ $E[X]/n = \frac{1}{n}\sum_{i=1}^nE[\mathbb{I}(i \text{ not observed})] = P(1 \text{ not observed}) = (1-1/n)^n$ . The limit of this is again $e^{-1}$ (about 36% of values are not observed).