# The expected number of unique elements drawn with replacement

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.

## 1 Answer

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}.$$

• Thank you for the reply! I will take some time to make sure I understand this. My main difficulty is with the approximation at the end. – EBH Aug 3 '17 at 18:54
• Glad you found the answer helpful! Note that understanding the approximation at the end is not essential to the solution. I only included that bit to explain why your proposed answer agrees well with simulation. – tddevlin Aug 3 '17 at 22:08
• Well, in the meantime I found that the difference in the result never exceeds 1, and since I work in a discrete system where all values are integers, that virtually means no difference at all. – EBH Aug 3 '17 at 22:14