12
$\begingroup$

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?

$\endgroup$
5
  • 12
    $\begingroup$ mathematical boxes are always non-transparent for future reference $\endgroup$ – Jorge Dec 22 '14 at 20:54
  • $\begingroup$ @JorgeFernández Also, the colors white, yellow, red, and black exist only on the balls in the box, nowhere else. You cannot "see all four colors" unless you see all four balls. $\endgroup$ – KSmarts Dec 22 '14 at 21:00
  • 1
    $\begingroup$ lol, I had assumed that part. $\endgroup$ – Jorge Dec 22 '14 at 21:01
  • $\begingroup$ Wait, did you not see the balls as you were putting them in the box? If not, how do you know what color they are? $\endgroup$ – KSmarts Dec 22 '14 at 21:01
  • $\begingroup$ If I'm out of luck, I may get red, red, red, red, red, red,.... If such a sequence continues long enough, it'll really mess up an 'average'. $\endgroup$ – user2338816 Dec 23 '14 at 0:10
21
$\begingroup$

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).

$\endgroup$
5
  • 1
    $\begingroup$ It is interesting to notice that by putting together this proof and mine, we get a nice identity for $n H_n$ involving sign-alternating binomial coefficients. $\endgroup$ – Jack D'Aurizio Dec 22 '14 at 21:09
  • $\begingroup$ +1 for pointing out the name of the problem. Give me some time to understand the solution. $\endgroup$ – Gqqnbig Dec 22 '14 at 21:40
  • $\begingroup$ Same result as the other three answers, but so much more intuitive $\endgroup$ – Evorlor Dec 23 '14 at 2:54
  • $\begingroup$ That the average number of tries needed to hit one out of $k$ (remaining) among $n$ equal $n/k$ follows from solving a simple equation. But can it also be deduced from some form of additivity of expectations? $\endgroup$ – Marc van Leeuwen Mar 13 '15 at 20:01
  • $\begingroup$ @Marc: The reference to additivity was for adding the fractions, not for finding them. (In hindsight I'm not sure whether is muddies matters more than it clarifies). $\endgroup$ – hmakholm left over Monica Mar 13 '15 at 20:47
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}}.$$

$\endgroup$
1
$\begingroup$

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}$

$\endgroup$

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.