# Strange Patience Game

The score starts at zero. Take a shuffled pack of cards and keep dealing face up until you reach the first Ace, at which the score becomes 1. Deal on until you reach the next 2, at which the score becomes 2, although you may not reach this if all the 2s came before the first Ace. If you reach 2, deal on until you reach the first 3, at which, if you reach it, the score becomes 3, and so on. What is the most likely final score? And how do you calculate the probability of any particular score?

I once wrote a program that performed this routine millions of times on randomised packs with different numbers of suits up to about 10. To my surprise, the most likely score for any pack seemed empirically to always be the same as the number of suits in the pack. I would love to see this proved, though it is beyond my powers.

-
Usually one would expect an ask for the expected value, rather than the most likely value. btw, can you please post the results of you simulation? (It might help people get some ideas from the data etc). – Aryabhata May 15 '12 at 17:34
Thanks Dustan! Here is my version, showing raw results. Each suit was tested 10,000,000 times. docs.google.com/spreadsheet/… – gostone May 15 '12 at 19:28
I'll remove mine, since it contains superfluous information per the discussion below. – Dustan Levenstein May 15 '12 at 20:58

Getting an average score of the number of suits doesn't surprise me. Intuitively, it takes $13$ cards to get the first ace, which uses up one suit full. Then $13$ more cards should get you a $2$, etc. Clearly this is a very rough argument. But when the number of suites gets very high you can only get a score of 13.

You can exactly calculate the chance of any given score, but it gets messier as you go up. To get $1,$ you have to have all the $2$'s before the first $1$. You can ignore the rest of the cards. If there are $n$ suits, the probability of this is $\frac {n!^2}{(2n)!}$. To get $2$, you need all the $3$'s before the first $2$ that is after the first $1$. You can enumerate the allowable orders of $1$'s, $2$'s, and $3$'s and calculate the probability.

-
This intuitive argument isn't quite right, because the number of ranks can be infinite, with exactly the same results. – gostone May 15 '12 at 19:51
On second thoughts that probably makes no difference to your argument! – gostone May 15 '12 at 20:01
@gostone:to calculate the probability of any given finite number, any higher cards than the next one can be ignored. However, if the ranks are truly infinite (as opposed to very large finite), you should make an argument about convergence – Ross Millikan May 15 '12 at 20:17

For small number of suits simulation confirms the hypothesis. Here is result for $n=4$ suits and $N=10^6$ trials:

But for greater number of suits it seems to become a local maximum, the largest value being 13. For $n=8$ and $n=10$ suits, $N=10^6$ it is

-
See my answer (and gostone's comment on it): he was working with infinitely many values for the cards, and not only 13. The high value for 13 disappear in this setting: it spreads over all integers larger or equal to 13. – D. Thomine May 15 '12 at 19:50

Here is a remark which is too long to fit in the comments section.

Let us fix the number of suits $n$. Let $k$ be the number of cards in one suit. For any integer $m$, the probability that the final score is $m$ does not depend on $k$ for $k > m$. This is because if one gets a score of $m < k$, this means that the chain of cards stops at some point, and that depends only on the relative distribution of the cards corresponding to the $m+1$ first values. Higher values do not influence this event.

Going to the limit $k \to + \infty$, one gets a limit distribution for the final score (finite number of suits, infinite number of values) which depends on $n$. Then, one can wonder :

• what are the properties of this distribution? Is it finite with full probability? If so, how does it decay at infinity? What is its mean (if defined)? Its moments of higher order?

• How does it scales when one increases the number of suits $n$?

I think that these kind of question are related to what you ask, and that they may be more "natural" (or, at least, more likely to be tackled by usual methods).

PS : the limit $n \to + \infty$ at fixed $k$ produces a trivial limit, hence I took this order for the limits.

-
I should have said that in my tests the ranks are assumed to be infinite in number. – gostone May 15 '12 at 19:33
ranks? The ranks in a deck are Ace, 2, 3, 4, ..., 10, Jack, Queen, King. How can you run the game on infinitely many ranks? – Dustan Levenstein May 15 '12 at 19:36
Call them 1,2,3...infinity? This avoids the last rank accumulating all the scores that could have been assigned to bigger ranks. – gostone May 15 '12 at 19:49
how do you simulate that, though? What random distribution are you using to shuffle? – Dustan Levenstein May 15 '12 at 19:59
Having finite ranks only skews the score for the last rank. So as long as you have enough ranks to clearly start showing the downward slope, that is enough. – gostone May 15 '12 at 20:04

The question asks "What is the most likely final score? And how do you calculate the probability of any particular score?"

It's not too hard to do the analysis for a single suit. The probability that the game ends at 13 is the chance that the 13 cards land in ascending order, or $1/13!$. The chance it ends at 12, is $1/12! - 1/13!$. In general, the chance the game ends at $i$ is $1/i! - 1/(i+1)!.$ And clearly the most-likely final score here is 1, with probability 1/2.

Adding more suits substantially complicates matters, but perhaps I'll try to work it out later if no one else beats me to it.

-