Expected number of uniques in a non-uniformly distributed population

Question

I am wondering if there is any reasonably simple way of calculating the following problem:

Drawing, with replacement, $n$ balls from a bin of $N$ different colored balls, with a known probability of drawing each color of ball, what is the expected number of "unique" balls, i.e., balls with no other ball of the same color?

e.g.
$P(red) = 0.25$
$P(blue) = 0.3$
$P(green) = 0.2$
$P(yellow) = 0.25$

Some example outcomes with 5 balls:

$\{red, red, green, blue, yellow\}$ - 3 unique balls
$\{red, red, green, green, blue\}$ - 1 unique ball
$\{blue, blue, blue, yellow, yellow\}$ - 0 unique balls

Or, with 3 balls:

$\{red, green, blue\}$ - 3 unique
$\{red, red, blue\}$ - 1 unique
$\{red, red, red\}$ - 0 unique

For 1 ball, it's trivially 1; for 2 balls, it's 1 - the probability of the outcomes where the two balls are the same color * 2 balls, after that it starts getting more complicated.

Answer 1

Let $X_i$ be the random variable equal to $1$ when there is exactly one ball of color $i$ ($i = 1, 2, \ldots, m$; to avoid confusion I write $m$ instead of $N$). The count of color $i$ follows a Binomial($p_i$, $n$) distribution, implying the expectation of $X_i$ is

$$\eqalign{ \mathbb{E}[X_i] = &\sum_{j=0}^{n} \binom{n}{j} p_i^j (1-p_i)^{n-j} X_i(j) \cr = &\binom{n}{1} p_i (1-p_i)^{n-1} \cr = &n p_i (1-p_i)^{n-1}. }$$

The number of unique colors is the sum of the $X_i$. Because expectation is linear we obtain

$$\eqalign{ \mathbb{E}[X] = &\sum_{i=1}^{m}\mathbb{E}[X_i] = \sum_{i=1}^{m}n p_i (1-p_i)^{n-1} \cr = &n\sum_{i=1}^{m} p_i (1-p_i)^{n-1}. }$$

Answer 2

I will give the outline of the solution. Numbers of each coloured ball in a draw follows multinomial distribution as tshauck pointed out. Let $R$ denote the number of red balls, $G$ - number of green balls, $B$ - number of blue balls and $Y$ - number of yellow balls in the draw of the size $n$. Then the probability that in random draw we have exactly $x_1$ red balls, $x_2$ green balls, $x_3$ blue balls and $x_4$ yellow ball is

$$P(R=x_1,G=x_2,B=x_3,Y=x_4)=\frac{n!}{x_1!x_2!x_3!x_4!}p_r^{x_1}p_g^{x_2}p_b^{x_3}p_y^{x_4}$$

where $p_r$ is probability of picking red ball, $p_g$ - green, $p_b$ - blue, $p_y$ - yellow.

Denote the number of unique balls in a draw by $U$. Then $U=f(R,G,B,Y)$. Since you have the distribution of vector $(R,G,B,Y)$ you can calculate distribution of $U$. Since we have four colours $U$ can get values $0,1,2,3,4$. So to get probability that $U=0$ you need to find all the possible combinations of $(R,G,B,Y)$ for which $U=0$ and add the probabilities of these combinations. So when $U=0$? When

1. All the balls appear more than once: $R>1$, $G>1$, $B>1$, $Y>1$

2. One colour is absent and all others appear more than once

   a. $R=0$, $G>1$, $B>1$, $Y>1$

   b. $R>1$, $G=0$, $B>1$, $Y>1$

   c. $R>1$, $G>1$, $B=0$, $Y>1$

   d. $R>1$, $G>1$, $B>1$, $Y=0$

3. Two colours are absent and all others appear more than once. $6$ cases

4. Three colours are absent, all the draw is of one colour. $4$ cases

All the four cases are mutually exclusive, so you can add the probabilities. Cases of $U=1,2,3,4$ can be treated similarly.

This of course is not an elegant solution, but it I do not see why it should not work. I suggest asking this in math.stackexchange.com.

Update 1

This approach is for calculating the probability distribution of $U$. For expected value of $U$ - whuber's answer is the right one.

Answer 3

Maybe I'm being naive here, but would the Multinomial Distribution not work for this?

P(1 unique) = P(1 Blue) + P(1 Red) + P(1 Blue), there are probably a lot of details that would need to be fill in, like P(1 Blue) = The multinomial distribution for all possible combinations of the other ball combinations where there's one blue.

http://en.wikipedia.org/wiki/Multinomial_distribution