Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You have a standard 52 card deck, with 13 cards of each of the 4 suits (Hearts, Diamonds, Spades, Clubs). What is the expected number of cards you have to draw from the deck until you have all 4 suits represented in your hand?

I couldn't think of how to get the negative binomial to work, since this is sampling without replacement and has 4 suits instead of just 2. I imagine a distribution that could solve this might be called the Negative Hypergeometric Multivariate. Anyone have any ideas? Thanks very much.

share|improve this question
    
Nice question! Running some simulations, the average seems to be about $7.66$, but I don't know which distribution is appropriate here. –  TMM Jan 1 '13 at 2:03
    
Yep, you need the Multivariate Hypergeometric Distribution, see for example in wikipedia: en.wikipedia.org/wiki/… –  Bitwise Jan 1 '13 at 2:11

1 Answer 1

up vote 6 down vote accepted

Let $s=13$ denote the number of cards in each suit and $N$ denote the (random) number of cards drawn when all $k=4$ suits are represented for the first time. Hence, $k\leqslant N\leqslant(k-1)s+1$ with full probability.

For each $n\geqslant1$, the event $[N\gt n]$ depends on the $n$ first cards drawn only. There are ${ks\choose n}$ collections of $n$ cards from a full deck of $ks$ cards and each such collection has the same probability ${ks\choose n}^{-1}$ to be drawn. The event $[N\gt n]$ means that one avoids at least one suit. Using inclusion-exclusion principle, there are $A_n$ ways to do so, where $$ A_n={k\choose1}{(k-1)s\choose n}-{k\choose2}{(k-2)s\choose n}+\cdots\pm{k\choose k-1}{s\choose n}\mp{k\choose 0}{0\choose n}. $$ This yields the expectation $$ \mathbb E(N)=\sum_{n\geqslant0}\mathbb P(N\gt n)=\sum_{n\geqslant0}{ks\choose n}^{-1}A_n. $$ In the case at hand, $$ \mathbb E(N)=\sum_{n\geqslant0}{52\choose n}^{-1}\left(4{39\choose n}-6{26\choose n}+4{13\choose n}-{0\choose n}\right), $$ that is, $$ \mathbb E(N)=4+\sum_{n=4}^{39}{52\choose n}^{-1}\left(4{39\choose n}-6{26\choose n}+4{13\choose n}\right), $$ or, $$ \mathbb E(N)=4+4B_{39}-6B_{26}+4B_{13},\qquad B_i=\sum_{n=4}^{i}{52\choose n}^{-1}{i\choose n}. $$ Numerically, $$ \mathbb E(N)=\frac{4829}{630}=7+\frac23-\frac1{630}\approx7.66508. $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.