I have a box containing $n$ colored balls. There are $c$ different colors. $k_1$ balls have color $1$, $k_2$ balls have color $2$, ... and $k_c$ balls have color $c$. When I draw $m$ balls with replacement, what is the expected number of different colors?

Referencess to similar problems are approximations are also appreciated.


After $m$ balls had been sampled with replacement, let $(B_1, B_2, \ldots, B_c)$ be the random vector recording the number of balls of each color in the sample. Clearly $\sum_{k=1}^c B_k = m$ and the vector is multnomially distributed with $$ \mathbb{P}\left(B_1=b_1,\ldots,B_c=b_c\right) = \frac{m!}{b_1!\cdots b_c!} \left(\frac{k_1}{n}\right)^{b_1} \cdots \left(\frac{k_c}{n}\right)^{b_c} $$ The random variable of the number of colors in the sample is $$ N_c = \sum_{r=1}^c [ B_r > 0 ] $$ where $[ \bullet ]$ denotes the Iverson bracket. Thus $$ \mathbb{E}\left(N_c\right) = \sum_{r=1}^c \mathbb{E}\left( [ B_r > 0 ] \right) = \sum_{r=1}^c \mathbb{P}\left( B_r > 0 \right) = \sum_{r=1}^c \left(1-\left(1-\frac{k_r}{n}\right)^m \right) $$ where we used the fact that each $B_r \sim \operatorname{Bin}\left(m,\frac{k_r}{n} \right)$.

Here is a confirmation with simulations in Mathematica:

In[33]:= kvec = {2, 5, 3, 4, 6};
n = Total[kvec];
m = 5;

In[37]:= Mean[
    RandomVariate[MultinomialDistribution[m, kvec/n], 
     10^4]], {2}]] // N

Out[37]= 3.2322

In[39]:= Sum[1 - (1 - ki/n)^m, {ki, kvec}] // N

Out[39]= 3.23275

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.