Four balls with different colors in a box, how many times do I need to pick to see all four colors? I have one white ball, one yellow ball, one red ball, one black ball. I put the four balls in a nontransparent box. I pick a ball from the box to see its color and put it back to the box.
Assuming picking is random, how many times on average do I need to pick in order to see all four colors?
If I'm lucky, I only need to pick four times. If I'm out of luck, I may get red, red, red, red, red, red,....
But what is it on average?
 A: Denote by $E(n)$ the expected number of additional draws when $n$ of the four balls have not been drawn so far. Then $E(0)=0$, and
$$E(n)=1+{n\over4} E(n-1)+{4-n\over 4}E(n)\qquad(n\geq1)\ .$$
This immediately implies
$$E(n)=E(n-1)+{4\over n}\qquad(n\geq1)\ ,$$
from which we get $E(4)={25\over3}$ by going through the motions.
A: This is known as the coupon collector's problem.
The average number of tries needed to see each of 4 colors is
$$ \frac44+\frac43+\frac42+\frac41 = 8\frac{1}{3} $$
The terms are $4/4$ for the time to take one ball; then $4/3$ for the average time it takes after the first ball until you see another code; $4/2$ for the average time it takes after the first time you see the second color until you see a third, and finally $4/1$ for the time you then have to wait until you see the last color. (These can just be added due to the additivity of expectations).
A: Obviously, we stop picking when we take a ball having a color that never occurred before, so we have to count how many strings of length $n$ have only occurrences of $A,B,C$ (no $D$), with at least one occurence of $A$, at least one occurrence of $B$, at least one occurrence of $C$. By the inclusion-exclusion principle, they are:
$$ 3^n - 3\cdot 2^n + 3$$
so the wanted expected value is:
$$ \sum_{n=4}^{+\infty}\frac{4n}{4^n}\left(3^{n-1}-3\cdot 2^{n-1}+3\right)=\color{red}{\frac{25}{3}}.$$
A: What is the probability you see all colors after exactly $n$ turns, how many sequences of length $n-1$ contain exactly three colors? first select the three colors in $4$ ways.
When using three colors there are $3^{n-1}$ sequences.
$3\cdot2^{n-1}-3$  use $2$ or $1$ colors.
Therefore $3^{n-1}-3\cdot2^{n-1}+3=3(3^{n-2}-2^{n-1}+1)$ use exactly three colors when those three colors are fixed.
Therefore there are $12(3^{n-2}-2^{n-1}+1)$ sequences.
Then the probability you see three colors for the first time in the $n$'th draw is $\frac{1}{4}\frac{12(3^{n-2}-2^{n-1}+1)}{4^{n-1}}=3\frac{(3^{n-2}-2^{n-1}+1)}{4^{n-1}}$.
Hence  you want  $3(\frac{1}{4}\sum\limits_{n=2}^\infty (n+2)\frac{3}{4}^n-\sum\limits_{n=3}^\infty (n+1)\frac{1}{2}^n+\sum\limits_{n=3}^\infty\frac{n+1}{4^n})=3(\frac{63}{16}-\frac{5}{4}+\frac{13}{144})=\frac{25}{3}$
