# Urn problem: probability of drawing balls of k unique colors

Given an urn with $N$ balls in $K$ colors, divided evenly (so $N$ $mod$ $K$ = $0$).

What is the probability that I draw $k$ different colors if I do $n$ draws without replacement?

And, more general, is there an easier way to calculate the expected value of the number of unique colors than summing $k * P(k)$ for all $k$ if $K <= k <= n$?

We find a simple formula for the expected number of different colours. For this we use the method of Indicator Random Variables.

For $$i=1$$ to $$K$$, let $$I_i=1$$ if colour $$i$$ is drawn at least once, and let $$I_i=0$$ otherwise. Then the number $$Y$$ of colours drawn is $$I_1+I_2+\cdots+I_K$$, and by the linearity of expectation we have $$E(Y)=E(I_1)+E(I_2)+\cdots +E(I_K).$$

$$E(I_i)$$ is defined as: $$E(I_i) = 1 \cdot Pr(I_i=1) + 0 \cdot Pr(I_i=0)$$ $$E(I_i) = 1 \cdot Pr(I_i=1)$$

Hence, we need to find $$\Pr(I_i=1)$$ to solve for $$E(I_i)$$. However, it turns out to be simpler to find $$\Pr(I_i=0)$$ and then use the fact that $$\Pr(I_i=1)=1-\Pr(I_i=0)$$.

In general, there are $$b=\binom{N}{n}$$ equally likely ways to choose $$n$$ balls. More specifically, there are $$N-N/K$$ balls not of colour $$i$$, so there are $$a=\binom{N-N/K}{n}$$ ways to choose $$n$$ balls, none of colour $$i$$.

It follows that $$\Pr(I_i=1)=1-\frac{a}{b}$$ and therefore $$E(Y)=K\left(1-\frac{a}{b}\right).$$

• I think I follow you. But it should be $\frac{b}{a}$, not $\frac{a}{b}$, right? Commented Mar 5, 2015 at 0:49
• Thanks, fixed, except that I did it by changing the meanings of $b$ and $a$. Commented Mar 5, 2015 at 0:52
• It took me a while to figure out which step I was missing. That was the explanation of why $E(X_i) = P(X_i = 1)$. The expectation function $E(X)$ sums the possible values of $X$ (namely 0 and 1) multiplied them by their probabilities. So, $E(X_i) = 1*Pr(X_i = 1) + 0*Pr(X_i = 0) = Pr(X_i = 1)$. Actually, that was pretty easy. Commented Mar 5, 2015 at 9:24
• @Lewistrick: Yes, if $W$ is a Bernoulli random variable (can only take on values $1$ and $0$) then $E(W)=\Pr(w=1)$, as you just showed. The method we used (the indicator random variables $X_i$, together with linearity of expectation can be a very useful tool in calculating expectations. Commented Mar 5, 2015 at 16:11