3 types of non-infinite coupons in urn with halting, no replacement

Question

An urn has 6 coupons in it.

• 3 red, 2 blue, 1 green

in order to win a prize I must collect a complete set of all the coupons of a particular colour. So all three reds, two blues or just 1 green constitute a winning set. I continue to draw until I have completed a set but must halt once I do. Coupons are not replaced, I draw one at a time and each coupon has an equal chance of being picked.

Example draws: RRR, RRBR, RG, G, BRRB, RRBG, etc

---

What is the probability of completing each set?

I already used brute force and found probabilities:

Red = 54/360 ; Green = 96/360 ; Blue = 210/360

The denominator is 6!/2! because I only checked the first 4 draws, the last two are irrelevant.

---

So my question is: How do I do this using Maths? I'm looking for a general solution that can be applied to larger numbers of coupons and more colours.

Edit: Maybe involves Hypergeometric distribution, unsure how to apply.

Answer 1

You could try to use absorbing Markov chains.

For this example there will be 9 states (the first 6 listed below are transient, the last three are absorbing). We can enumerate the states as follows:

1. Initial state, no coupons observed
2. 1 Red
3. 1 Blue
4. 2 Red
5. 1 Red, 1 Blue
6. 2 Red, 1 Blue
7. Complete set of Red
8. Complete set of Blue
9. Complete set of Green

The transition matrix is then

$ P = \begin{bmatrix} 0 & 3/6 & 2/6 & 0 & 0 & 0 & 0 & 0 & 1/6 \\ 0 & 0 & 0 & 2/5 & 2/5 & 0 & 0 & 0 & 1/5 \\ 0 & 0 & 0 & 0 & 3/5 & 0 & 0 & 1/5 & 1/5 \\ 0 & 0 & 0 & 0 & 0 & 2/4 & 1/4 & 0 & 1/4 \\ 0 & 0 & 0 & 0 & 0 & 2/4 & 0 & 1/4 & 1/4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1/3 & 1/3 & 1/3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} $

With the transition matrix in hand you can use the formulas given in the wiki to calculate various different properties of the urn model. Here is a Matlab script which computes the probabilities you are interested in.

Q = [0,3/6,2/6,0,0,0;
     0,0,0,2/5,2/5,0;
     0,0,0,0,3/5,0;
     0,0,0,0,0,2/4;
     0,0,0,0,0,2/4;
     0,0,0,0,0,0;];

R = [0,0,1/6;
      0,0,1/5;
      0,1/5,1/5;
      1/4,0,1/4;
      0,1/4,1/4;
      1/3,1/3,1/3;];

N = inv(eye(6) - Q);
B = N*R;
absorption_probabilities = B(1,:)

%If only interested in absorption probabilities we can avoid explicitly
%forming (I-Q)^(-1)
%e1 = [1;0;0;0;0;0];
%absorption_probabilities = R'*(((eye(6)-Q)')\e1);

In order to generalize this, you would need to find a convenient way to enumerate the states and transition probabilities for an arbitrary number of colors/coupons.

Answer 2

Say you have $k$ colours, and $n_i$ coupons of colour $i$. Denote the set of colours by $I$. The probability that an entire subset $S\subseteq I\setminus\{i\}$ of other colours is completed before colour $i$ is completed is

$$ \frac{n_i}{n_i+\sum_{j\in S}n_j} $$

(the probability that the last coupon of all the colours in $S\cup\{i\}$ that's drawn has colour $i$).

Thus, by inclusion-exclusion, the probability to complete colour $i$ after $m$ draws without completing any of the other colours is

$$ \sum_{S\subseteq I\setminus\{i\}}(-1)^{|S|}\frac{n_i}{n_i+\sum_{j\in S}n_j}\;. $$

In your case, $k=3$, $n_1=3$, $n_2=2$, $n_3=1$, so the probability to first complete red is

$$ \frac33-\frac34-\frac35+\frac36=\frac3{20}\;, $$

the probability to first complete green is

$$ \frac22-\frac23-\frac25+\frac26=\frac4{15}\;, $$

and the probability to first complete blue is

$$ \frac11-\frac13-\frac14+\frac16=\frac7{12}\;, $$

in agreement with your results.