0
$\begingroup$

Say we have a collection of $b$ distinct, uncoloured balls distributed among $s$ nonempty sets of known sizes. We randomly select one ball and paint it black, and another $r$ balls and paint them red. What's the probability that the black ball is in the same set as a red ball?

I found a formula which works for the case where $r = 1$. Let $C$ be the set of ball sets, so $\left|C\right| = s$. Then the probability that the black ball is in the same set as the red ball is $$\frac{\sum_{c \in C} \left|c\right| \left(\left|c\right| - 1\right)}{b \left(b-1\right)}.$$

However, I don't see how to generalize this formula to arbitrary values of $r$.

$\endgroup$
0
$\begingroup$

The total number of ways to color one ball black and $r$ balls red is $$ b\cdot{{b-1}\choose{r}}=\frac{b!}{r!(b-r-1)!}. $$ Of these, the number that place the black ball in a set with no red balls is $$ \sum_{c\in C}\left|c\right|{{b - \left|c\right|}\choose{r}}=\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)!}{r!(b-\left|c\right|-r)!}, $$ where the sum is over sets such that $b-\left|c\right|\ge r.$ The probability that the black ball is in a set with at least one red ball is therefore $$ 1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)!(b-r-1)!}{b!(b-\left|c\right|-r)!}. $$ In the $r=1$ case, this becomes $$ 1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)}{b(b-1)}=\sum_{c\in C}\frac{\left|c\right|}{b}-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)}{b(b-1)}=\sum_{c\in C}\frac{\left|c\right|(\left|c\right|-1)}{b(b-1)}, $$ agreeing with your answer. For $r=2$, the result is $$ 1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)(b-\left|c\right|-1)}{b(b-1)(b-2)}, $$ and so on.

$\endgroup$
  • $\begingroup$ I'm not sure I follow. How can $$ 1-\sum_{c\in C}\frac{\left|c\right|(b-\left|c\right|)!(b-r-1)!}{b!(b-\left|c\right|-r)!} $$ give a correct answer for the case that there is only one set of balls (i.e., $s = 1$)? In this case $b = \left|c\right|$, so $b - \left|c\right| - r$ must be negative, and you can't compute the factorial of a negative number. $\endgroup$ – Psychonaut Apr 4 '14 at 9:52
  • $\begingroup$ Oh, never mind, I see now that this sum, like the previous one you wrote, is meant to apply only to those sets where $b - \left|c\right| \geq r$. $\endgroup$ – Psychonaut Apr 4 '14 at 10:30

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.