Clock Solitaire - the proof

Someone mentioned elsewhere that they would like to see this. Additionally, I have been musing on it for quite some time. So, here's the proof of the Clock Solitaire problem I discussed a couple of weeks ago...

The problem

The game of Clock Solitaire is played as follows: shuffle a standard deck of 52 playing cards, then deal them into thirteen piles, twelve of which represent the 'numbers' on a clock face, with the thirteenth pile in the centre. Each pile should have four cards.

Take the first card from the centre pile, and place it face up beside the pile corresponding to the number on the card (with Jack = 11, Queen = 12, King = centre). Then, turn the top card on that pile, and repeat the process. Repeat until you cannot turn a card over, because the pile is empty.

You win if and only if you turn every card over before stopping. (In fact, the last card you turn over will always be the fourth King. You win if and only if this is card 52.)

Since there's no actual skill involved, the game is entirely random, and so the probability of winning is fixed.

The problem is simple: what are the chances of winning?

Solution

Imagine a two-dimensional grid of nodes. In the first dimension, the nodes are numbered from 0 to 52, and represent the number of cards that have been turned over so far in the game. Naturally, the game starts with 0 cards turned over, and each time a card is turned over, this number increases by exactly 1.

In the second dimension, the nodes are numbered from 0 to 4, and represent the number of Kings that have been turned over. Naturally, the game starts with 0 Kings turned over, and ends as soon as the 4th King is turned.

Clearly, the game starts at node (0, 0), and ends at node (x, 4), where x can be any number from 4 to 52. The game is lost if x is less than 52, and won only if x is 52.

Now, if we are at node (x, y), and turn a card over, there are two possible outcomes. Either we get a King, and move to node (x+1, y+1), or we get not-a-King, and move to node (x+1, y). The probability of getting a King is (number_of_Kings_left/number_of_cards_left), which is known (4-y / 52-x). The probability of getting not_a_King is (1 - number_of_Kings_left/number_of_cards_left), which is also known (((52-x) - (4-y))/(52-x)).

Still with me? We're nearly there now.

The probability of a path through the nodes (always starting at node (0,0)), is equal to the product of all the probabilities of all the steps along that path. Furthermore, we can say that the probability of reaching a given node is the sum of the probabilities of all the paths leading to that node.

The probability of reaching node (0,0) is, of course, 1, since you always start there. And the probability of winning the game is equal to the probability of node (52,4).

The problem now is that that is a monstrously impossible thing to work out. The sum of all the paths from node (0,0) to node (52,4)? There are millions of them!

Except that we can break the problem down further using the lovely mathematical trick of recursion.

If we want to get to node (x, y), there are two ways we can do it. We can start at node (x-1, y) and turn over not_a_King, or we can start at node (x-1, y-1) and turn over King. But we know the probabilities of drawing a King and not_a_King. And we know how to work out the probabilties of getting to nodes (x-1, y) and (x-1, y-1).

The probability of reaching node (x,y) is, therefore (P(x-1,y-1) x P(King)) + (P(x-1, y) x P(not_a_King)).

Which means we can calculate the probability of getting to node (x, y). And we can calculate the odds of getting to node (52, 4), just by plugging in the right numbers.

(There are some edge cases to deal with. Clearly, any node (x, 0) only has one input - there is no node (x-1, -1), so that input path doesn't exist, and should be ignored. Likewise, there are no paths from (x-1, 4) to (x, 4), since the game is over by that point, so we can ignore those possibilities. Finally, you cannot have turned over more Kings than you have turned over cards, so nodes (0, 1), (0, 2), (0, 3) and (0, 4) all have probability 0 - they can't happen.)

It's still a nasty nasty sum. But, since all the steps are known, it's just a big sum. And computers excel at sums. So, we can now grab an Excel spreadsheet, plug in the formulae, and known probabilities (0,0) is 1, (0,1) is 0, (0,2) is 0, (0,3) is 0 and (0,4) is 0, and the spreadsheet will do the rest.

And, lo and behold, the answer is 1 in 13! Huzzah!