Say we draw $D$ marbles out of a bag (with infinite marbles), where each marble could be one color out of $C$ colors (each with equal probability). What is the expected value of the number of different colors our total draw includes?

So for example, if $D=4$ and $C=3$, we are drawing $4$ marbles total, where each could be red, green, or blue with equal likelihood. What is the average number of different colors represented in our draw (anywhere from $1$ to $3$) we can expect to have?

After playing around, I came up with the following way to express it:

$$E[C;D] = \frac{1}{C^D} \big[ (1)(C) + (2)(\text{number of arrangements of two different colors}) + ... + (C)(\text{number of arrangements of $C$ different colors}) \big]$$

And after testing with some low numbers, I came up with the following formula:

$$E[C;D] = C - \frac{(C-1)^{D}}{C^{D-1}}$$

It works for the numbers I tested, and also makes intuitive sense since $\lim_{D \rightarrow \infty}E[C;D] = C$.

But I'm curious to know: Is this formula correct? If so, how can I prove it?


1 Answer 1


For $j=1,\ldots,C$, let

$$I_j = \begin{cases} 1 & \text{if color $j$ is drawn at least once} \\ 0 & \text{if color $j$ is never drawn} \\ \end{cases} $$

Then we seek $E\left(\sum_{j=1}^C{I_j}\right) = \sum_{j=1}^C{E\left(I_j\right)}$ by linearity of expectation.

For any $j = 1,\ldots,C,$ we have:

\begin{eqnarray*} E(I_j) &=& P(\text{Color $j$ drawn at least once}) \\ &=& 1-P(\text{Color $j$ never drawn}) \\ &=& 1-\left(\dfrac{C-1}{C}\right)^D. \end{eqnarray*}

So, our required value is $$C\cdot E(I_1) = C\left[1-\left(\dfrac{C-1}{C}\right)^D\right] = C-\dfrac{(C-1)^D}{C^{D-1}}.$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .