4
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – EBH
    Aug 3, 2017 at 18:54
  • $\begingroup$ 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. $\endgroup$
    – tddevlin
    Aug 3, 2017 at 22:08
  • $\begingroup$ 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. $\endgroup$
    – EBH
    Aug 3, 2017 at 22:14
0
$\begingroup$

I had a similar question, and found this 5-year-old post. Regarding the answer above from tddevlin, I know it's correct, but it feels strange to me to assume that you can just sum up these Ij as independent values. As you have a limited number of draws and bins, if you happen to be lucky and have already covered a lot of unique bins, it's less likely for you to find new bins after that. The draws are independent, but I think the next Ij are dependent on previous ones -- Making 5 draws from 10 bins and be able to cover all 10 unique bins has 0 probability. Similarly, making 5 draws and cover 0 bins is also impossible. But I'm not sure if this dependency is accounted for in the calculation for P(draw at least one ball from bin j).

Improve this answer
$\endgroup$
3
  • $\begingroup$ You need to think about it in the sense that $I_1, \cdots I_n$ are identically distributed. Even though they are dependent, they will have the same expectations. Now if you wanted to take the variance of $\sum_{i=1}^n I_i$, then the dependency would come into play. $\endgroup$
    – user277126
    Jan 12 at 5:35
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Jan 12 at 6:58
  • $\begingroup$ Thanks, user277126, it's really helpful. $\endgroup$
    – Yunfei Chen
    Jan 12 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.