# Not a run of the mill 20 balls in a bag problem!

I'm trying to work out this problem with mixed results and have tried several ways.

Here is the problem in its easiest way to explain:

There is a bag of 20 coloured balls:

3 Blue 4 Pink 5 Yellow 8 Green

If I pick balls out the bag without replacement until I have 3 the same colour, what are the probabilities that the 3 balls of the same color are Blue, Pink, Yellow or Green?

I can work out things like getting 3 greens from just 3 picks etc as I believe this is 0.049122807 but am I right in that there is 27 ways to end up with 3 greens with all different probability?

As the order is only relevant on the final pick that gives you 3 the same, up to that point its irrelevant?

But it gets far more complex when your picking until 3 the same only!

• Not clear what is the meaning of "what is the probability of: Blue: Pink: Yellow: Green" Feb 25 '16 at 18:45
• Sorry, I am trying to work out the probability of each. For example green 65% yellow 20% pink 10% and blue 5% = total 100% Feb 25 '16 at 18:50
• Clearly getting 3 green before getting 3 of any other colour is easiest but how easy? Feb 25 '16 at 18:53
• Consider your total sample space; it's not all combinations of balls. Feb 25 '16 at 18:57
• Am I on the right track of only being 104 end results? as if so I will give that a go. Feb 25 '16 at 19:01

Assuming you have plenty of time to spare, and a calculator handy, you can try solving it using this method (or maybe, as suggested above, write a computer program to do this):

This method involves using states to denote a particular situation in the problem.

Let $X_{b, p, y, g}$ denote the state that you currently have $b$, $p$, $y$ and $g$ Blue, Pink, Yellow and Green balls (out of the bag).

Then let $E(C_{b, p, y, g})$ denote the probability of getting 3 balls of colour $C$ in the state $X_{b, p, y, g}$.

Now, $b$, $p$, $y$ and $g$ can only be 0, 1 or 2 (anything else and you already have 3 balls of the same colour). Therefore you need to consider the $3^4=81$ states in total.

So for a particular colour, $C$, the probability of getting 3 of that colour is $E(C_{0, 0, 0, 0})$.

Let's say that colour is Blue, for example.

Then:

$$E(B_{0, 0, 0, 0}) = \frac{3}{20}E(B_{1, 0, 0, 0})+\frac{4}{20}E(B_{0, 1, 0, 0})+\frac{5}{20}E(B_{0, 0, 1, 0})+\frac{8}{20}E(B_{0, 0, 0, 1})$$

$$E(B_{1, 0, 0, 0}) = \frac{2}{19}E(B_{2, 0, 0, 0})+\frac{4}{19}E(B_{1, 1, 0, 0})+\frac{5}{19}E(B_{1, 0, 1, 0})+\frac{8}{19}E(B_{1, 0, 0, 1})$$

In general, if $b,p,y,g<3$:

$$E(B_{b, p, y, g}) = \frac{3-b}{20-b-p-y-g}E(B_{b+1, p, y, g})+\frac{4-p}{20-b-p-y-g}E(B_{b, p+1, y, g})+\frac{5-y}{20-b-p-y-g}E(B_{b, p, y+1, g})+\frac{8-g}{20-b-p-y-g}E(B_{b, p, y, g+1})$$

So:

$$\small E(B_{b, p, y, g}) = \frac{(3-b)E(B_{b+1, p, y, g})+(4-p)E(B_{b, p+1, y, g})+(5-y)E(B_{b, p, y+1, g})+(8-g)E(B_{b+1, p, y, g+1})}{20-b-p-y-g}$$

Note that:

$$E(B_{3, p, y, g})=1$$ $$E(B_{b, 3, y, g})=0$$ $$E(B_{b, p, 3, g})=0$$ $$E(B_{b, p, y, 3})=0$$

So unless if you want to make a lot of calculations... a computer program may come in handy.

I've made a program which has worked out the probabilities using this method. However, I cannot be 100% sure that this is correct, as I may have made a mistake. Nevertheless:

Blue: $\small 0.036239070527$
Pink: $\small 0.107921954207$
Yellow: $\small 0.209518422754$
Green: $\small 0.646320552513$

As noted at the end, I think we already have a better answer than the one below, but this offers another way to approach the problem.

You have to pick at least three balls in order to get three of one color. By the Pigeonhole Principle, if you have picked nine balls, you must have at at least three of at least one color.

So we will first get three of one color when we pick the $n$th ball, for $3 \leq n \leq 9$. Moreover, when that happens, exactly two of the first $n-1$ balls will be the same color as the $n$th ball, and there will be no more than two of any other color.

For example, consider the case in which you first get three balls of the same color on the $6$th time you pick a ball. That means you have already drawn five balls, no more than two of any one color. There are several possible ways to do this:

• Two each of two colors, one of a third color. It actually only matters what the first two colors are, so there are $\binom 42 = 6$ different combinations of colors to consider.
• Two of one color and one of each of the other colors; there are $4$ combinations of colors to consider.

One combination of colors is $2$ green, $2$ pink, $1$ either blue or yellow. There are $\binom 82$ ways to choose two green balls, $\binom 42$ ways to choose two pink balls, and $8$ ways to choose one ball of one of the remaining colors. There are altogether a total of $\binom{20}{5}$ equally likely ways to choose five balls, so the probability that the first five balls will have this combination of colors is $$P(2G,2P,1) = \frac{8 \binom 82 \binom 42}{\binom{20}{5}}.$$ If this particular combination comes up in the first five balls, we then have $6$ of $15$ remaining balls that are green, so the chance to pick this combination of the first five balls and get a third green ball is $$P(2G,2P,1) P(G \mid 2G,2P,1) = \left(\frac{8 \binom 82 \binom 42}{\binom{20}{5}}\right) \frac{6}{15}.$$

As it happens, the probability that the sixth ball will be green, given that exactly two of the first five balls are green, is the same no matter what the colors of the other three balls are, so instead of $P(G \mid 2G,2P,1)$ we can write $P(G \mid 2G,3)$.

The probability that we stop after picking $6$ balls because we have three green balls is then \begin{split} & P(2G,2P,1) P(G \mid 2G,3) \\ & \qquad + P(2G,2B,1) P(G \mid 2G,3) \\ & \qquad + P(2G,2Y,1) P(G \mid 2G,3) \\ & \qquad + P(2G,1B,1P,1Y) P(G \mid 2G,3) \\ & = (P(2G,2P,1) + P(2G,2B,1) + P(2G,2Y,1)+ P(2G,1B,1P,1Y)) P(G \mid 2G,3). \end{split}

In a similar way, we can find the probability of stopping after picking the $n$th ball for each $n$ and each color.

There are $28$ such probabilities to work out in order to determine the total probability of each color ($21$, if you simply subtract the probabilities of three colors from $1$ to get the fourth color's probability; but doing the other $7$ probabilities explicitly gives you an error check). Not all of them are as complicated to calculate as the example given; each of the four probabilities for the ninth ball is just a fraction of the form $\frac{n}{12}$ multiplied by $P(2B,2P,2Y,2G)$.

In principle you might be able to do this with a simple calculator, a pencil, and a few sheets of paper, but on second thought the recursive algorithm with $324$ probabilities (one for each color for each of $81$ "states"; see the other answer) may be preferable, since it has a relatively simple recursive formula.

The solutions already given provide the correct probabilities but they trace through all the states of the system. The only state we care about is the one where the winning ball is drawn. Thus: $$P(\text{m wins}) = \sum_{states\,S_j} P(\text{m wins on next draw}\mid S_j)P(S_j|\text{draw} \sum_{k=1}^4i_k(S_j)) P(\text{draw}\sum_{k=1}^4i_k(S_j))$$ Where $(n_1,n_2,n_3,n_4)$ is the vector of initial numbers of each class of ball and $S_j=(i_1(S_j),i_2(S_j),i_3(S_j),i_4(S_j))$ is the vector of current numbers of balls drawn. Then $m$ can only win on the current draw if $2$ balls of color $m$ and $3$ balls of no color have been drawn. $$P(\text{m wins on next draw}|S_j)=\left\{\array{\frac{n_m-i_m(S_j)}{\sum_{k=1}^4(n_k-i_k(S_j))} & i_m(S_j)=2\text{ and }\max(i_k(S_j),1\le k\le4)<3 \\ 0 &\text{ otherwise }}\right.$$ We can leverage what we know about counting to derive the probability of each state given that the number of total balls of that state have been drawn. $$P(S_j|\text{draw}\sum_{k=1}^4i_k(S_j))=\frac{\prod_{k=1}^4{n_k\choose i_k(S_j)}}{{\sum_{k=1}^4n_k\choose \sum_{k=1}^4i_k(S_j)}}$$ If we assume that drawing balls goes on until the bag is empty, even though the game is over by this point, we have $$P(\text{draw}\sum_{k=1}^4i_k(S_j))=1$$ We can express these equations in a short program:

module combinations
implicit none
contains
elemental function choose(n,k)
integer, intent(in) :: n, k
integer choose
integer i

choose = 1
do i = 1, k
choose = choose*(n-k+i)/i
end do
end function choose
end module combinations

program bag20
use combinations
implicit none
integer, parameter :: REAL64 = kind([double precision::])
integer iblue, ipink, iyellow, igreen, I(4)
integer, parameter :: N(4) = [3,4,5,8]
real(REAL64) :: P(4) = 0

do iblue = 0, 2
do ipink = 0, 2
do iyellow = 0, 2
do igreen = 0, 2
I = [iblue,ipink,iyellow,igreen]
where(I==2) P = P+product(choose(N,I))/ &
real(choose(sum(N),sum(I)),REAL64)*(N-I)/sum(N-I)
end do
end do
end do
end do
write(*,'(2(g0:1x))') 'pblue = ',P(1),'ppink = ',P(2), &
'pyellow = ',P(3),'pgreen = ',P(4)
end program bag20


edit: I just noticed that the same formula, but rearranged slightly and arrived at by different reasoning was posted by @Graham Kemp here. Paradoxically nobody admitted to understanding it in that thread, either.

• I'm reading your answer to see how the method can be improved to be more efficient, but I'm having trouble understanding "$P(m\,wins)=\sum_{states\,S_j}P(m\,wins\,on\,next\,draw|S_j)P(S_j|draw\sum_{k=1}^4i_k(S_j))P(draw\sum_{k=1}^4i_k(S_j))$". Could you please clarify how this works? In addition, I'm interested in what language your program is written in. Thanks! Feb 29 '16 at 21:06
• I am considering the probability of winning on the next draw for each possible state of the system. When we know this we can just multiply by the probability of reaching each state and sum over all states to get the answer. The first probability is 0 if at least 3 balls of any color have been drawn in the current state because the game is over. Also 0 if other than 2 balls of our color have been drawn. Otherwise, it's the number of balls of our color left $\div$ total balls left. The probability of reaching a given state may be determined by a simple counting argument. +Fortran! Mar 1 '16 at 2:56