5
$\begingroup$

This problem came up in a game I was playing. It's surely a standard combinatorics problem, but I'm having trouble searching for an exact match.

Suppose an urn contains $B$ blue balls, $R$ red balls, and $G$ green balls. Balls are drawn without replacement until you've drawn three balls of any one color (not necessarily consecutively). What's the probability of ending with three blue balls?

My reasoning is as follows: the number of ways to stop after drawing three blue balls is equal to the number of ways of drawing exactly two blue and at most two red and green balls (in any order), times the number of blue balls ending the sequence. This suggests that the number of ways of ending with blue is

$$E_B = \sum_{i=0}^2 \sum_{j=0}^2 (B-2)(2+i+j)!\binom{B}{2}\binom{R}{i}\binom{G}{j}$$

where the binomial terms select which balls are drawn and the factorial enumerates all permutations, for the sequence of balls excluding the last ball. The probability of ending with three blue balls is then $$\frac{E_B}{E_B+E_R+E_G}$$ for $E_R$ and $E_G$ computed analogously.

Is this approach correct?

EDIT: Proposed recursive solutions to the problem (e.g. Blatter's answer below) are practical if one just cares about computing a number, but I'm particularly interested in an answer to this question that 1) explains why the above formula is incorrect, and 2) salvages the formula.

$\endgroup$
  • 1
    $\begingroup$ I don't think so. You seem to be treating all sequences as equally likely. I think you would have to multiply each sequence by the probability of its occurrence. $\endgroup$ – saulspatz Jul 29 '18 at 18:15
  • $\begingroup$ @saulspatz why isn't each sequence equally likely? $\endgroup$ – user7530 Jul 29 '18 at 18:16
  • 1
    $\begingroup$ If $B=3, R=G=10,$ is the sequence $BBB$ as likely as the sequence $RGRGR$? I know you count $6$ of the former and $10\cdot9\cdot8\cdot10\cdot9$ of the latter, but to get the probability of the first, we divide by $28\cdot27\cdot26$ and to get the probability of the second we divide by $28\cdot27\cdot26\cdot25\cdot24$ $\endgroup$ – saulspatz Jul 29 '18 at 18:32
  • $\begingroup$ @saulspatz ah I see, yes I think you’re right. Should the terms be weighted by $2^{4-i-j}$ then? Is there a rigorous way of seeing this? $\endgroup$ – user7530 Jul 29 '18 at 18:49
  • $\begingroup$ I don't see where that factor would come from. I'd need to see the whole formula, I think. I also think Christian Blatter's answer looks reasonable. $\endgroup$ – saulspatz Jul 29 '18 at 20:06
1
$\begingroup$

As was mentioned in the comments, you cannot just count the number of sequences ending in three blues and divide by the total number. Not all sequences are equally likely (the longer the sequence, the less likely it is).

To fix your method, you need to add up probabilities instead of numbers. For each $0\le i\le 2$ and $0\le j\le 2$, you need to compute the probability of getting your third blue ball after getting $i$ red and $j$ green balls, then sum. The result is $$ \sum_{i=0}^2\sum_{j=0}^2\frac{\binom{B}2\binom{R}i\binom{G}j}{\binom{B+R+G}{2+i+j}}\cdot \frac{B-2}{(R-i)+(G-j)+(B-2)} $$ The first factor is the probability that the first $i+j+2$ balls consist of $i$ reds, $j$ greens and $2$ blues. The next factor is the probability that the subsequent ball is blue.

$\endgroup$
  • $\begingroup$ Letting $b=13$, $r=21$, $g=17$ your formula and my answer give the same result $3\,223\,077/18\,009\,460$. $\endgroup$ – Christian Blatter Jul 30 '18 at 16:01
  • $\begingroup$ @ChristianBlatter Excellent, thanks for pointing out the mistake. $\endgroup$ – Mike Earnest Jul 30 '18 at 16:02
0
$\begingroup$

There aren't all that many possibilities.

If $(r,g,b)$ is the ending state with $r$ red balls, $g$ green balls, and $b$ blue balls, then the possibilities for $(r,g,b)$ ending with three blue balls are (0,0,3), (0,1,3), (1,0,3), (0,2,3), (2,0,3), (1,1,3), (1,2,3), (2,1,3), and (2,2,3). The probability of each case can be computed from a hypergeometric distribution. Work out all nine cases and add up the probabilities.

$\endgroup$
  • $\begingroup$ Does that work out to a modification of the formula in the OP? $\endgroup$ – user7530 Jul 29 '18 at 21:42
  • $\begingroup$ @user7530 No, I don't think the formulas are equivalent. $\endgroup$ – awkward Jul 29 '18 at 23:48
0
$\begingroup$

The following is a full solution of the problem, but the final formula gives no insight.

Note that the game ends after at most $7$ moves. It is played on the vertices and grid lines of the lattice cube $[0..2]^3$, hence has $27$ nonterminal states.

Denote by $p(x,y,z)$ the probability that the game ends with three drawn blue balls, given that we already have drawn $x$ blue, $y$ red, and $z$ green balls. This function satisfies $$p(3,y,z)=1,\quad p(x,3,z)=0,\quad p(x,y,3)=0\qquad \bigl(x,\>y,\>z\in[0..2]\bigr)$$ and the backwards recursion $$p(x,y,z)={b-x\over n-j}\>p(x+1,y,z)+{r-y\over n-j}\>p(x,y+1,z)+{g-z\over n-j}\>p(x,y,z+1)\ ,$$ whereby $n:=b+r+g$ and $j:=x+y+z$.

The quantity $t:=p(0,0,0)$ then is the probability you are looking for. Here is a Mathematica implementation of this approach, together with a numerical example:

enter image description here

$\endgroup$
  • $\begingroup$ The lattice cube is a neat way of visualizing. $\endgroup$ – qwr Jul 30 '18 at 13:27

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.