Expected number of different colors

Question

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.

Answer 1

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[
  Total[Sign[
    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