3
$\begingroup$

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

$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I think I follow you. But it should be $\frac{b}{a}$, not $\frac{a}{b}$, right? $\endgroup$
    – Lewistrick
    Commented Mar 5, 2015 at 0:49
  • $\begingroup$ Thanks, fixed, except that I did it by changing the meanings of $b$ and $a$. $\endgroup$
    – André Nicolas
    Commented Mar 5, 2015 at 0:52
  • $\begingroup$ 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. $\endgroup$
    – Lewistrick
    Commented Mar 5, 2015 at 9:24
  • $\begingroup$ @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. $\endgroup$
    – André Nicolas
    Commented Mar 5, 2015 at 16:11

You must log in to answer this question.

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