5

Say I have a population that I sample from without replacement. In this population there are $a_1$ members of type 1, $a_2$ members of type two and so forth up to $a_k$ of type $k$.

What is the expected number of trials until I collect at least one member out of each type? An example here would be the expected number of cards drawn from a deck until I get one of every valor.

Benjamin Lindqvist
  • 3,112

1 Answers1

3

For $k=1$ you clearly have an expectation of $1$.

For $k=2$ you seem to have an expectation of $$\displaystyle \sum_{n=0}^{a_1+a_2} \frac{{a_1 \choose n}+{a_2 \choose n} - {0 \choose n}}{{a_1 + a_2 \choose n}}= 1+\dfrac{a_1}{a_2+1}+\dfrac{a_2}{a_1+1}$$ taking ${m \choose n}=0$ when $0 \le m \lt n$

For $k=3$ you seem to have an expectation of $$\displaystyle \sum_{n=0}^{a_1+a_2+a_3} \frac{{a_1+a_2 \choose n}+{a_1+a_3 \choose n}+{a_2+a_3 \choose n}-{a_1 \choose n}-{a_2 \choose n}-{a_3 \choose n} + {0 \choose n}}{{a_1 + a_2 +a_3\choose n}} \\=1 + \frac{a_1+a_2}{a_3+1}+\frac{a_1+a_3}{a_2+1}+\frac{a_2+a_3}{a_3+1}-\frac{a_1}{a_2+a_3+1}-\frac{a_2}{a_1+a_3+1}-\frac{a_3}{a_1+a_2+1}$$

and I would expect a similar inclusion-exclusion type calculation to apply for larger $k$.

Henry
  • 157,058
  • For your example of the expected number of cards drawn from a deck until you get one of every value, you have $k=13$ and $a_i=4$, and this gives a result of about $27.997122$ – Henry Feb 18 '16 at 08:34
  • Although it wasn't the answer I was hoping for, nonetheless it kind of highlights how hopeless some combinatorics problems are. Thanks. – Benjamin Lindqvist Feb 19 '16 at 18:50
  • @Henry, I have been enjoying this problem and I understand the proof, I just don't know how you simplify, the summation, if I could know how this result follows then everything works: $\sum ^{a_{1}+a_{2}}{n=1}\dfrac {\begin{pmatrix} a{1} \ n \end{pmatrix}}{\begin{pmatrix} a_{1}+a_{2} \ n \end{pmatrix}}=\dfrac {a_{1}}{1+a_{2}}$ – Tina Jun 25 '18 at 16:23
  • @Henry, Ok I still can't see it – Tina Jun 25 '18 at 20:17
  • I should have said related to $\sum\limits_{m=0}^b {c+m \choose c} ={b+c+1 \choose c+1} = \frac{b+c+1}{c+1} {b+c \choose c}$ with the first equality explained by looking at Pascal's triangle and the second adapting the factorials. Then you can say $\sum\limits_{n=1}^{a_1+a_2} \dfrac{a_1 \choose n}{a_1+a_2 \choose n} = \sum\limits_{n=0}^{a_1} \dfrac{a_1 \choose n}{a_1+a_2 \choose n} - 1$ $= \sum\limits_{n=0}^{a_1} \dfrac{a_2 +n \choose a_2}{a_1+a_2 \choose a_2} - 1$ $= \dfrac{a_2+a_1+1}{a_2+1}-1$ $= \dfrac{a_1}{a_2+1}$ – Henry Jun 25 '18 at 20:31
  • @Henry Thanks, I didn't get the middle step, but asked someboy and they were able to help, Now I understand but have a page of working just to prove $\sum ^{a_{1}+a_{2}}{n=1}\dfrac {\begin{pmatrix} a{1} \ n \end{pmatrix}}{\begin{pmatrix} a_{1}+a_{2} \ n \end{pmatrix}}=\dfrac {a_{1}}{1+a_{2}}$ Seems quite tricky to simplify, did you realise straight away when solving the problem? – Tina Jun 27 '18 at 13:52
  • @Tinatim - it was over two years ago so I do not remember. I seem to have used the word seem so I may or may not have used some shortcuts or an empirical calcuation – Henry Jun 27 '18 at 16:52