8
$\begingroup$

This arose out of an online game, and both exact answers and approximations would be greatly appreciated.

$280$ balls are randomly put into $56$ bins such that all bins contain exactly $5$ balls. Among all $280$ balls, $2$ of them are colored red, $2$ of them green, $2$ of them blue (the rest can be considered uncolored, or any other color). I want to know the probability that, among the $56$ bins of balls, there exists $\ge 1$ bin which satisfies the following condition: the bin contains balls of at least two colors among the colors red, green, and blue.

For example, if we use "O" to denote a ball that is not colored as red, green, or blue. $\{R, B, O, O, O\}$ and $\{R,R,G,O,O\}$ are bins that satisfy the condition, while $\{R,R,O,O,O\}$ and $\{B,O,O,O,O\}$ do not.

My Attempt

I think an exact answer can be arrived (using multinomials), but I could not proceed beyond writing out the denominator. I decided to do a Poisson approximation, where $n = 56$ and $p$ is the probability that, when we randomly sample $5$ balls out of $280$, the $5$ balls satisfy the condition.

I calculated $p$ as follows:

$$ 1 - \frac { \binom{274}{5} + \binom{6}{1} \binom{274}{4} + 3 \binom{2}{2} \binom{274}{3} } {\binom{280}{5}} $$

And from then on I used $\lambda = n p$ and used $1 - e^{-\lambda}$ as the final probability that there exists $\ge 1$ bin which satisfies the condition.

  • Is my $p$ correct, or did I count it wrong?
  • Can I use Poisson approximation here? I know that Poisson can be used for weakly dependent events, but I am not sure this qualifies.

Edit: The Randomization Process

I realized that I probably should have stated the randomization process. The original game was randomized by randomly sampling 5 out of 280 into the first bin, 5 out of the remaining 275 into the second, 5 out of the remaining 270 into the third, and so on.

$\endgroup$
1
$\begingroup$

I approached this by drawing a tree diagram, starting with $R_1$ in any bin.

Adding $G_1$ has two possible outcomes: (Note that these are not $\frac{1}{56}$ and $\frac{55}{56}$)

  • $Node_1$ has $G_1$ in same bin as $R_1$ with probability $\color{green}{P_1=\frac{4}{279}}$
  • $Node_2$ has $G_1$ in new bin with probability $P_2=\frac{275}{279}$

The first case satisfies the condition of having at least two colors in one bin, so we stop there and add this to a list of successes. Continuing from $Node_2$, adding $B_1$ has three possible outcomes:

  • $Node_3$ has $B_1$ with $R_1$, probability $\color{green}{P_3=\frac{4}{278}}$
  • $Node_4$ has $B_1$ with $G_1$, probability $\color{green}{P_4=\frac{4}{278}}$
  • $Node_5$ has $B_1$ in new bin, probability $P_5=\frac{270}{278}$

From $Node_5$, adding $R_2$ has four possible outcomes:

  • $Node_6$ has $R_2$ with $R_1$, probability $P_6=\frac{4}{277}$
  • $Node_7$ has $R_2$ with $G_1$, probability $\color{green}{P_7=\frac{4}{277}}$
  • $Node_8$ has $R_2$ with $B_1$, probability $\color{green}{P_8=\frac{4}{277}}$
  • $Node_9$ has $R_2$ in new bin, probability $P_9=\frac{265}{277}$

From $Node_6$, adding $G_2$ has four possible outcomes:

  • $Node_{10}$ has $G_2$ with $R_1R_2$, probability $\color{green}{P_{10}=\frac{3}{276}}$
  • $Node_{11}$ has $G_2$ with $G_1$, probability $P_{11}=\frac{4}{276}$
  • $Node_{12}$ has $G_2$ with $B_1$, probability $\color{green}{P_{12}=\frac{4}{276}}$
  • $Node_{13}$ has $G_2$ in new bin, probability $P_{13}=\frac{265}{276}$

From $Node_9$, adding $G_2$ has five possible outcomes:

  • $Node_{14}$ has $G_2$ with $R_1$, probability $\color{green}{P_{14}=\frac{4}{276}}$
  • $Node_{15}$ has $G_2$ with $R_2$, probability $\color{green}{P_{15}=\frac{4}{276}}$
  • $Node_{16}$ has $G_2$ with $G_1$, probability $P_{16}=\frac{4}{276}$
  • $Node_{17}$ has $G_2$ with $B_1$, probability $\color{green}{P_{17}=\frac{4}{276}}$
  • $Node_{18}$ has $G_2$ in new bin, probability $P_{18}=\frac{260}{276}$

From $Node_{11}$, adding $B_2$ has four possible outcomes:

  • $Node_{19}$ has $B_2$ with $R_1R_2$, probability $\color{green}{P_{19}=\frac{3}{275}}$
  • $Node_{20}$ has $B_2$ with $G_1G_2$, probability $\color{green}{P_{20}=\frac{3}{275}}$
  • $Node_{21}$ has $B_2$ with $B_1$, probability $P_{21}=\frac{4}{275}$
  • $Node_{22}$ has $B_2$ in new bin, probability $P_{22}=\frac{265}{275}$

From $Node_{13}$, adding $B_2$ has five possible outcomes:

  • $Node_{23}$ has $B_2$ with $R_1R_2$, probability $\color{green}{P_{23}=\frac{3}{275}}$
  • $Node_{24}$ has $B_2$ with $G_1$, probability $\color{green}{P_{24}=\frac{4}{275}}$
  • $Node_{25}$ has $B_2$ with $G_2$, probability $\color{green}{P_{25}=\frac{4}{275}}$
  • $Node_{26}$ has $B_2$ with $B_1$, probability $P_{26}=\frac{4}{275}$
  • $Node_{27}$ has $B_2$ in new bin, probability $P_{27}=\frac{260}{275}$

From $Node_{16}$, adding $B_2$ has five possible outcomes:

  • $Node_{28}$ has $B_2$ with $R_1$, probability $\color{green}{P_{28}=\frac{4}{275}}$
  • $Node_{29}$ has $B_2$ with $R_2$, probability $\color{green}{P_{29}=\frac{4}{275}}$
  • $Node_{30}$ has $B_2$ with $G_1G_2$, probability $\color{green}{P_{30}=\frac{3}{275}}$
  • $Node_{31}$ has $B_2$ with $B_1$, probability $P_{31}=\frac{4}{275}$
  • $Node_{32}$ has $B_2$ in new bin, probability $P_{32}=\frac{260}{275}$

From $Node_{18}$, adding $B_2$ has six possible outcomes:

  • $Node_{33}$ has $B_2$ with $R_1$, probability $\color{green}{P_{33}=\frac{4}{275}}$
  • $Node_{34}$ has $B_2$ with $R_2$, probability $\color{green}{P_{34}=\frac{4}{275}}$
  • $Node_{35}$ has $B_2$ with $G_1$, probability $\color{green}{P_{35}=\frac{4}{275}}$
  • $Node_{36}$ has $B_2$ with $G_2$, probability $\color{green}{P_{36}=\frac{4}{275}}$
  • $Node_{37}$ has $B_2$ with $B_1$, probability $P_{37}=\frac{4}{275}$
  • $Node_{38}$ has $B_2$ in new bin, probability $P_{38}=\frac{255}{275}$

That completes the tree. Now add up the successes, multiplying through each parent node. $$\begin{array}{rl} P_1= & \frac{4}{279}\\ P_2(P_3+P_4)= & \frac{275}{279}\cdot\frac{8}{278}\\ P_2 P_5(P_7+P_8)= & \frac{275}{279}\cdot\frac{270}{278}\cdot\frac{8}{277}\\ P_2 P_5 P_6(P_{10}+P_{12})= & \frac{275}{279}\cdot\frac{270}{278}\cdot\frac{4}{277}\cdot\frac{7}{276}\\ P_2 P_5 P_9(P_{14}+P_{15}+P_{17})= & \frac{275}{279}\cdot\frac{270}{278}\cdot\frac{265}{277}\cdot\frac{12}{276}\\ P_2 P_5 P_6 P_{11}(P_{19}+P_{20})= & \frac{275}{279}\cdot\frac{270}{278}\cdot\frac{4}{277}\cdot\frac{4}{276}\cdot\frac{6}{275}\\ P_2 P_5 P_6 P_{13}(P_{23}+P_{24}+P_{25})= & \frac{275}{279}\cdot\frac{270}{278}\cdot\frac{4}{277}\cdot\frac{265}{276}\cdot\frac{11}{275}\\ P_2 P_5 P_9 P_{16}(P_{28}+P_{29}+P_{30})= & \frac{275}{279}\cdot\frac{270}{278}\cdot\frac{265}{277}\cdot\frac{4}{276}\cdot\frac{11}{275}\\ P_2 P_5 P_9 P_{18}(P_{33}+P_{34}+P_{35}+P_{36})= & \frac{275}{279}\cdot\frac{270}{278}\cdot\frac{265}{277}\cdot\frac{260}{276}\cdot\frac{16}{275} \end{array}$$ The sum is $$\frac{4440294}{27452639}\approx 16.17438\%$$

$\endgroup$
1
$\begingroup$

First, let me say that I think that your calculation of $p$ is correct, and that a Poisson approximation is appropriate here.

Consider the complementary problem: What is the probability that no bin contains more than one color? In other words, each bin either contains all colorless balls, or one or two balls of the same color with all the other balls in the bin colorless.

The balls can be sequenced in $280!$ ways, all of which we assume are equally likely. We consider the first five balls in the sequence to constitute bin 1, the second five balls to be bin 2, etc. Notice that this means the order of the balls in each bin is significant. We say that a sequence is "acceptable" if each bin contains all colorless balls or a mix of colorless balls and balls of a single color. So each bin in an acceptable sequence either contains no colored balls, or one or two balls of a single color with the remaining balls colorless. We break the acceptable sequences into four cases based on the number of bins which contain two colored balls: there may be zero, one, two, or three such bins. Let's say $p_n$ is the probability of an acceptable sequence which has $n$ bins with two colored balls, for $n = 0, 1, 2, 3$. We compute these probabilities below.

Case $n=0$: There are $\binom{56}{1,1,1,1,1,1,50}$ ways (a multinomial coefficient) to select the bins containing colored and uncolored balls, and in each of the six bins containing colored balls, the single colored ball can be placed in $5$ ways; then the $274$ colorless balls can be sequenced in $274!$ ways. So $$p_0 = \frac{\binom{56}{1,1,1,1,1,1,50} \cdot 5^6 \cdot 274!}{280!} = 0.799991$$

Case $n=1$: One of the bins contains two colored balls, and the color of the balls can be chosen in $3$ ways. The bins containing colored and uncolored balls can be chosen in $\binom{56}{1,1,1,1,1,51}$ ways. In each of the four bins containing one colored ball, the ball can be placed in $5$ ways; and in the bin containing two colored balls, the balls can be placed in $\binom{5}{1,1,3}$ ways. The uncolored balls can be sequenced in $274!$ ways. So $$p_1 = \frac{ 3 \cdot \binom{56}{1,1,1,1,1,51} \cdot 5^4 \cdot \binom{5}{1,1,3} \cdot 274!}{280!} = 0.037647$$

The remaining cases are similar. We find $$p_2 = \frac{3 \cdot \binom{56}{1,1,1,1,52} \cdot 5^2 \binom{5}{1,1,3}^2 \cdot 274!}{280!} = 0.000579$$

$$p_3 = \frac{\binom{56}{1,1,1,53} cdot \binom{5}{1,1,3}^3 \cdot 274!}{280!} = 2.91 \times 10^{-6}$$

So the total probability of an acceptable sequence is $$p = p_0+p_1+p_2+p_3 = 0.83822$$ and the answer to the original problem, the probability that at least one bin contains balls of more than one color, is $$1-p = \boxed{0.16178}$$

$\endgroup$

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.