36
$\begingroup$

I read about this game as a kid, but my maths was never up to solving it:

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.

  • 0
    I'll remove mine, since it contains superfluous information per the discussion below.2012-05-15

4 Answers 4

7

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.

  • 0
    @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 convergence2012-05-15
4

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

<span class=n=4, $N=10^6$">

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

enter image description here

<span class=n=4, $N=10^6$">

  • 0
    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.2012-05-15
3

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.

  • 0
    ah, I should have actually read D. Thomine's remark.2012-05-15
0

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.