The expected number of unique elements drawn with replacement

Question

I'm following this question which describes almost exactly my situation (with little modifications, in bold):

Drawing, with replacement, $k$ balls from a bin of $n$ different colored balls, with an equal probability of drawing each color of a ball, what is the expected number of "unique" colors? How many different colors are we expected to get?

As I'm not so strong in statistics, I approached this numerically, and after some computations and fitting I got this:

$$u(n,k) = n(1-e^{(-k/n)})$$

Where $u$ is the expected number of unique colors, $n$ is the number of available colors, and $k$ is the sample size (Note that $k$ may be larger than $n$). It seems to fit exactly the numerical results. My only problem is that I have no idea why it is so.

I read the answer to the question cited above and tried to implement it in my case with no success. I'll be glad for an explanation that doesn't assume knowledge of advanced statistics.

Answer 1

The solution to this problem makes use of a classic technique in probability, which is to begin by defining a set of so-called indicator (i.e. binary-valued) random variables, and then to use linearity of expectation.

We begin by defining for each of the $n$ bins the random variable $$ \begin{align*} I_j = \begin{cases} 1 & \text{if we draw at least one ball from the } j\text{th bin} \\ 0 & \text{otherwise}. \end{cases} \end{align*} $$ Letting $X$ be the random variable denoting the number of different colored balls we draw, we have $$ X = \sum_{j=1}^n I_j. $$ Now using linearity of expectation, $$ \mathbb{E}[X] = \mathbb{E}\left[\sum_{j=1}^n I_j\right] = \sum_{j=1}^n \mathbb{E}[I_j]. $$ It remains to compute $\mathbb{E}[I_j]$ for $j = 1,\dots,n$. Note that for any $j$ $$ \begin{align*} \mathbb{E}[I_j] & = P(I_j = 1) \\ & = P(\text{draw at least one ball from bin } j) \\ & = 1 - P(\text{draw zero balls from bin } j) \\ & = 1 - \left(\frac{n-1}{n}\right)^k. \end{align*} $$ So the expected number of unique colors is $$ \mathbb{E}[X] = n\left[ 1 - \left(\frac{n-1}{n}\right)^k \right] $$

Note that the answer you provide is a close approximation since $$ \left(\frac{n-1}{n}\right)^k = \left(1 - \frac{1}{n}\right)^{k} = \left(1 - \frac{1}{n}\right)^{n\cdot\frac{k}{n}} \approx e^{-k/n}. $$