# Odds of guessing suit from a deck of cards, with perfect memory

While teaching my daughter why drawing to an inside straight is almost always a bad idea, we stumbled upon what I think is a far more difficult problem:

You have a standard 52-card deck with 4 suits and I ask you to guess the suit of the top card. The odds of guessing the correct suit are obviously 1 in 4. You then guess again, but the first card is not returned to the deck. You guess a suit other than the first drawn and the odds are 13/51, somewhat better than 1 in 4.

Continuing through the deck your odds continually change (never worse than 1 in 4, definitely 100% for the last card) what are your overall odds for any given draw over the course of 52 picks?

Can this be calculated? Or do you need to devise a strategy and write a computer program to determine the answer? Do these type of problems have a name?

-
The reasoning on the second guess applies to the third and fourth guess too. If you've drawn $n$ cards with $n<4$ then then some suit still has all $13$ cards in the deck, and you would guess such a suit. So then the chance of a successful guess would be $\frac{13}{52-n}$. –  alex.jordan Jan 3 '12 at 6:01
Do you mean: As a function of $n$, what is the probability of guessing right on draw $n$, averaged over all $52!$ permutations of the deck, assuming that you guess intelligently based on complete knowledge of the first $n-1$ draws? –  Brian M. Scott Jan 3 '12 at 7:14
I considered a very similar question years ago but then I was stuck in its investigation because of my weak techniques. But now, after the deal with complex recurrent sums for a bounty question and the search of a material about semiinvariants for Phani Raj, I noticed such a strategy in a problem from one Russian math olympiad. So I remembered the old problem and felt a power to continue my investigation. :-) And just now, when I already wrote my results, I found your question. –  Alex Ravsky Dec 21 '13 at 0:48

The approximate odds of guessing the suit properly is 35.4%, quite a bit higher than 25%. This is easy to calculate with Monte Carlo analysis, though that does not easily allow a more precise answer. A combination of elementary probability and MC would be best though I have not attempted this.

I can't immediately think of a good way to find the exact rational probability since there are many ways for the number of each suit to change throughout the draws. Perhaps a combinatorialist could help here?

-
Interesting Monte Carlo result! I expect the high probability of success is mainly due to contributions from guesses when the deck is close to being exhausted, say from the $40$'s on. –  André Nicolas Jan 3 '12 at 6:47
@ Andre: I think the high success rate has more to do with the following: even distributions of the four suits from the first $n$ draws leave you with a 25% chance. Uneven distributions improve your chances (you guess a suit that has been chosen the fewest times), and there are many more uneven distributions that even ones, even for small $n$. –  alex.jordan Jan 3 '12 at 6:55
@Charles: Did you just write a program and Monte Carlo this? Or is this something you've looked at previously? 35% is a little higher than I would have guessed, but seems in the ballpark. How many sample games did you run? Could you post the code? Mode: both interesting questions, but what I was originally looking for was the fair bet of running through the whole deck. Thanks to all that responded. –  Charles Kerr Jan 3 '12 at 14:15
Yes I just wrote a program. I don't have the code with me at the moment (traveling this week) but I'd say 10 million iterations, maybe 100 million. The result should be accurate to the number of decimals given (it's rounded up slightly). –  Charles Jan 4 '12 at 17:55

Here's a possibly helpful formula (that seems very hard to put in closed form). If you have already drawn $n$ cards, then $P(\mathrm{success})$ is

$$\sum_{\spadesuit+\heartsuit+\diamondsuit+\clubsuit=n;\ 0\leq \spadesuit,\heartsuit,\diamondsuit,\clubsuit\leq13}\frac{13-\min(\spadesuit,\heartsuit,\diamondsuit,\clubsuit)}{52-n}\cdot\frac{\binom{n}{\spadesuit, \heartsuit, \diamondsuit, \clubsuit}\binom{52-n}{13-\spadesuit, 13-\heartsuit, 13-\diamondsuit, 13-\clubsuit}(13!)^4}{52!}$$

(This formula uses the multinomial coefficient, which in this case counts the number of ways to choose $\spadesuit$ positions to be spades, $\heartsuit$ of the remaining positions to be hearts, etc. out of the $n$ first cards to be drawn.)

The first factor is the probability of success given a partition $\spadesuit+\heartsuit+\diamondsuit+\clubsuit=n$ (the partition represents how the first $n$ cards were distributed, disregarding the order they came in). The rest is the probability of the first $n$ cards providing that partition (counting all the possible orderings, divided by the total possible orderings of a deck).

The sum above conditions over the partition that represents the cards which have already been drawn. We could also sum over partitions that represent the cards yet to be drawn. That makes computing more efficient for the second half of the deck. If $r$ cards remain, then $P(\mathrm{success})$ is

$$\sum_{\spadesuit+\heartsuit+\diamondsuit+\clubsuit=r;\ 0\leq \spadesuit,\heartsuit,\diamondsuit,\clubsuit\leq13}\frac{\max(\spadesuit,\heartsuit,\diamondsuit,\clubsuit)}{r}\cdot\frac{\binom{r}{\spadesuit, \heartsuit, \diamondsuit, \clubsuit}\binom{52-r}{13-\spadesuit, 13-\heartsuit, 13-\diamondsuit, 13-\clubsuit}(13!)^4}{52!}$$

Evaluating these sums requires enumerating partitions. This could be done with some programming, but I did it for $r,n\leq10$ in Excel and found the following $P_n(\mathrm{success})$:

\begin{align} P_0&=0.25 & P_1&\approx0.2549 & P_2&=0.26 & P_3&\approx0.2653 \\ P_4&\approx0.2686 & P_5&\approx0.2710 & P_6&\approx0.2733 & P_7&\approx0.2762 \\ P_8&\approx0.2788 & P_9&\approx0.2809 & P_{10}&\approx0.2830 & &\cdots\\ &\cdots & &\cdots & P_{42}&\approx0.4005 & P_{43}&\approx0.4122 \\ P_{44}&\approx0.4258 & P_{45}&\approx0.4392 & P_{46}&\approx0.4548 & P_{47}&\approx0.4836 \\ P_{48}&\approx0.5201 & P_{49}&\approx0.5514 & P_{50}&\approx0.6176 & P_{51}&=1 \end{align}

-
I think that the hardest part about finding a closed form expression for this in terms of $n$ will be the restriction that the parts of the partition be $\leq13$. There may be hope to find a closed form expression for $n\leq13$, but then the second hardest thing is the presence of $\min$. –  alex.jordan Jan 3 '12 at 6:41
Alex: I think I see what you're saying. For p(50), there are only two cards left. There's roughly a .25 chance they are the same suit, in which case your probability of guessing p(50) is 100%. But there's approximately a 3/4 chance they are two different suits, in which case you've got a 50/50 chance. So (.50 * .75) + (1.00 * .25) is about .625 or close to your real value of .6176 -- is that right? –  Charles Kerr Jan 3 '12 at 20:15
@Charles That sounds about right. The discrepancy between the .625 and .6176 lies in the "roughly a .25 chance they are the same suit". –  alex.jordan Jan 4 '12 at 0:38
@Charles If it helps to understand the formula, when $r=2$, there are four terms that are permutations of $2+0+0+0=2$ with contribution $\frac{13\cdot12}{52\cdot51}$ and six terms that are permutations of $1+1+0+0=2$ with contribution $\frac{13\cdot13}{52\cdot51}$. –  alex.jordan Jan 4 '12 at 0:47
If we took the average of P(0)... P(51) that would allow me to determine the fair bet for running through the whole deck, is that right? Is it approximately what @Charles above (the other Charles!) found with his result of 35.4% ? –  Charles Kerr Jan 4 '12 at 14:40

overall odds for any given draw over the course of 52 picks

If I rephrased your question as "how much should you be willing to pay to play the game where I will show you $n$ cards out of 52 and if you guess the next remaining card then I give you a dollar" would an answer to this question be suitable? Just to be clear, in this game you would have to pay up front before you see any cards (although you know the number $n$ beforehand), and you should be willing to pay up to a quarter when $n=0$ and up to a dollar when $n=52-1$. This is not really an answer, I just wanted to understand the question.

Alternatively, would you allow the player to see the $n$ cards (rather than just the number $n$) before deciding how much to pay? Or on the other hand would you not even allow $n$ to be known, but you would require the player to decide how much to pay and then $n$ is chosen uniformly at random between 0 and 51 at the beginning of the game?

-