7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ For two balls with probabilities p and 1-p and two draws the expectation equals 4p(1-p), not 1. With n > 2 draws the expectation is np(1-p)(p^(n-2) + (1-p)^(n-2)) because you cannot have two unique balls and the only way to have one unique ball is to draw n-1 of the other color. $\endgroup$ – whuber Dec 16 '10 at 16:21
9
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Perfect - I wasn't sure if something so simple existed or not. $\endgroup$ – lgaud Dec 16 '10 at 17:30
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Good analysis, but it leads to computationally intractable algorithms even for moderate numbers of colors and balls. In some cases that's ok when the approach suggests approximations or asymptotic formulas, but that does not seem to be the case here. It turns out the essence of this problem concerns the additivity of f: f(R,G,B,Y) = f(R,G,B) + some function of Y. If f were not additive but could still be computed recursively as f(R,G,B,Y) = g(f(R,G,B), Y) then there might be a dynamic programming solution of complexity O(n*N), which is still pretty efficient. $\endgroup$ – whuber Dec 16 '10 at 17:40
  • $\begingroup$ @whuber, I think it is possible to use recursion here. Maybe it is even possible to get analytic solution. I would be pretty hopeful that there is some combinatorical trick which provides it. $\endgroup$ – mpiktas Dec 16 '10 at 19:27
  • $\begingroup$ Yes, recursion works: it leads to the dynamic programming solution. You won't get a solution that's any simpler than the description of the urn, which involves the array (p_i) of individual probabilities. $\endgroup$ – whuber Dec 16 '10 at 19:48
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Just to clarify: by "P(1 Blue)" you must mean "probability of exactly one blue and no other color appears exactly once," etc. Otherwise the equation is not correct. Similarly in the second sentence you must restrict to combinations of all other colors where none of them appear exactly once. $\endgroup$ – whuber Dec 16 '10 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.