[Math] Urn problem: probability of drawing balls of k unique colors

expectationprobability

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$?

Best Answer

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

Related Question