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.

I shuffle a standard deck and guess that I will pick an ace at my first draw. If it is indeed an ace, I win the game immediately and stop. If it is not an ace, I will claim that the next card drawn from the deck (now only 51 cards remaining) is a 2. If it is a 2, I win the game and stop. If not, I will go on: I will go though all ranks this way and if I guess the 13th card drawn incorrectly (i.e., it was not a King), then I lose the game.

I simulated this game and I got a winning probability of around .65, but now I want to solve for it mathematically. I think the exact way is too complicated (the probability that I get the fifth card right will depend on how many of it have already been drawn beforehand). So, I am satisfied with an approximate way to solve for it.

share|improve this question

3 Answers 3

up vote 10 down vote accepted

Call your game Game $1$. Game $2$ is almost the same, except that we continue for the full $13$ rounds, and we win Game $2$ if we get one or more match. The probability of winning Game $2$ is the same as the probability of winning Game $1$. So to answer your question, it is enough to find the probability of winning Game $2$.

The probability of a match at position $i$ is $\frac{4}{52}$. Now sum over all $i$ from $1$ to $13$. We get $\binom{13}{1}\frac{4}{52}$. This is $1$, and is the expected (mean) number of matches in Game $2$. But of course it is not the probability of winning Game $2$.

The problem is that we have counted twice every situation in which we have a match at $i$ and also a match at $j$. For clarity of thought, though in fact it doesn't matter, assume that $i\lt j$. The probability of a match at $i$ is $\frac{4}{52}$. Given that we have a match at $i$, the probability of a match at $j$ is $\frac{4}{51}$. So the probability of a match at $i$ and $j$ is $\frac{4}{52}\cdot \frac{4}{51}$. There are $\binom{13}{2}$ ways of picking $i$ and $j$. So from $\binom{13}{1} \frac{4}{52}$ we subtract $\binom{13}{2}\frac{4}{52}\cdot\frac{4}{51}$.

But we have subtracted too much! For we have subtracted one too many times all situations in which we had three matches. Let $i\lt j\lt k$. The probability of matches at $i$, $j$, and $k$ is $\frac{4}{52}\cdot\frac{4}{51}\cdot \frac{4}{50}$. There are $\binom{13}{3}$ ways of choosing the triple $(i,j,k)$. So we will add back $\binom{13}{3} \frac{4}{52}\cdot\frac{4}{51}\cdot \frac{4}{50}$.

But we have added back too much, for we have added back too many times the situations in which we have $4$ matches. So we must subtract $\binom{13}{4}\frac{4}{52}\cdot\frac{4}{51}\cdot \frac{4}{50}\cdot\frac{4}{49}$.

Continue. We are using the Method of Inclusion/Exclusion.

For practical work, we could probably stop. Already the term $\binom{13}{4}\frac{4}{52}\cdot\frac{4}{51}\cdot \frac{4}{50}\cdot\frac{4}{49}$ is fairly small. But it is not hard to continue to the end and get an exact answer.

Remark: Your simulation gave an answer quite close to the truth. The terms I mentioned in the post give roughly $0.639$, and the next term in the Inclusion/Exclusion is an "add" term.

share|improve this answer
    
Great answer; it makes sense now. Thanks a lot. –  Wuschelbeutel Kartoffelhuhn Sep 6 '12 at 3:10
    
@André. I must be missing something :) I thought that we draw cards without replacement. I don't quite follow why the probability of a match at position $i$ is 4/52. By the way, I cranked the sum through Mathematica and found the exact solution to be $\frac{17244702296022529}{26816424180170625}\quad \approx 0.643065$ –  shoda Sep 6 '12 at 4:03
2  
@shoda: Yes, it looks peculiar until it becomes obvious, which may take a while. The important point is that all sequences of $13$ cards are equally likely. So the probability that the $7$-th card drawn is the Ace of Spades is $\frac{1}{52}$. One can easily imagine that we should consider all the different patterns for the first $6$ cards, which is of course complicated. But that is unnecessary. As an example, let's find the probability the second card is the Ace of Spades the hard way. Either the first is the Ace of Spades, and then the probability is $0$. (To be continued) –  André Nicolas Sep 6 '12 at 4:11
    
Or else first is not the Ace of Spades (probability $\frac{51}{52}$, and then probability second is Ace of Spades is $\frac{1}{51}$. Product: $\frac{1}{52}$! If you want, calculate the probability the third is the Ace of Spades the hard way. It will simplify to $\frac{1}{52}$. Or calculate probability the second is an Ace the hard way. You will get something that is equivalent to $\frac{4}{52}$. But if we realize all sequences are equiprobable, we can calculate directly and simply. –  André Nicolas Sep 6 '12 at 4:15
    
@André. Thanks! –  shoda Sep 6 '12 at 4:29

p(winning)=1-p(losing). You lose if you don't get a 1 on the first draw and no 2 on second etc. probability of not getting a 1 on the first card is 48/52=12/13. Then probability of not getting a 2 on the second draw is 47/51 if a 2 was not drawn on the first draw and 48/51 if a 2 was drawn on the first. So the probability of not winning on the first or second draw is (48/52)(1-4/52)(47/51)+(48/52)(1-48/52)(48/51). We continue in this way assuming a 3 is not drawn on the third draw taking account of whether no 3s, one 3 or two 3s were drawn in the first 2 draws. Then it gets more complicated considering how many times 4s were drawn in the first 3 draws etc.

share|improve this answer

This problem is solved using inclusion-exclusion in Section 7.8 of Problems and snapshots from the world of probability by Blom, Holst, and Sandell.

Suppose have $s$ decks each numbered from $1$ to $n$, and you randomly select $n$ cards one at a time (without replacement) from the thoroughly shuffled super-deck of $ns$ cards. We say that the $i$th card gives a "match" if the $i$th card has the number $i$ on it.

For $k\geq 0$, the chance of exactly $k$ matches is $$p(k)={n\choose k}\sum_{i=k}^n(-1)^{i-k}\, {s^i\over i!}\,{{n-k\choose i-k}\over{ns\choose i}}.$$

Putting $n=13$, $s=4$ and $k=0$, we calculate the chance that you win as $$1-p(0)=\sum_{i=1}^{13}(-1)^{i+1}\, {4^i\over i!}\,{{13\choose i}\over {52\choose i}}=.6430649.$$

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.