Expected number of balls to pick to select three balls of the same colour

Question

A bag contains 64 balls of eight different colours, with eight of each colour. What is the expected number of balls you would have to pick (without looking) to select three balls of the same colour?

Answer 1

Let $N$ be the number of draws without replacement needed to draw three balls of the same colour. The probability of not drawing three balls of the same colour in $n$ draws is

$$ \mathsf P(N\gt n)=\binom{64}n^{-1}\sum_{p=0}^8\binom8p\binom82^p\binom{8-p}{n-2p}\binom81^{n-2p}\;, $$

where $\binom{64}n$ is the total number of ways to choose $n$ out of $64$ balls, $p$ (for “pair”) is the number of colours of which two balls are drawn, $\binom8p$ is the number of ways to select those colours, $\binom82^p$ is the number of ways to choose the pairs of balls with those colours, $n-2p$ is the number of colours of which a single ball is drawn, $\binom{8-p}{n-2p}$ is the number of ways to select those colours, and $\binom81^{n-2p}$ is the number of ways to choose the single balls with those colours. Thus, the expected number of draws needed to draw three balls of the same colour is

\begin{eqnarray*} \mathsf E[N]&=&\sum_{n=0}^\infty\mathsf P(N\gt n)\\ &=&\sum_{n=0}^\infty\binom{64}n^{-1}\sum_{p=0}^8\binom8p\binom82^p\binom{8-p}{n-2p}\binom81^{n-2p} \\ &=& \frac{961520398523}{105047234105} \\ &\approx& 9.1532 \end{eqnarray*}

(Wolfram|Alpha computation).

Here's Java code for a simulation that confirms the result.

Note that the expected number of draws required to draw three balls of the same colour is quite close to the maximal number $9$ of draws required to draw two balls of the same colour.

Answer 2

Here is a different approach.

Denote by $(x,y)$ the state when there are $x$ colors not yet drawn, $y$ colors drawn once, hence $8-x-y\geq0$ colors drawn twice so far. In this state there are $48+2x+y$ balls left in the bag, among them $8x$ balls of never drawn colors and $7y$ balls of once drawn colors. Denote by $E(x,y)$ the expected number of additional drawings when we are in state $(x,y)$. Then $E(0,0)=1$, and we want to know $E(8,0)$. The latter value can be computed by means of following recursion: $$E(x,y)=1+{8x\over 48+2x+y}E(x-1,y+1)+{7y\over 48+2x+y}E(x,y-1)\ .$$ This recursion is implemented in the following Mathematica program: