6
$\begingroup$

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.

3 Answers 3

11

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.

  • 0
    @AndréNicolas Of course that would be the result if the cards were put back into the deck after each turn. – 2012-09-06
2

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.

1

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