Probability of winning/losing a lonely card game when you shout an integer progressively each time you draw

Question

Take a standard face-down 52-deck of cards, including 13 ranks of four suits (for simplicity, assign value 1 to 13 from ace to King). Draw the cards one by one, shouting the integers from 1 to 13 (and then starting again) in the natural order (i.e. {1,2,3,4...}) at each draw. For example, you shout 'one' and draw a 7, then you shout 'two' and draw an ace, then you shout 'three' and draw a King, and so on and so forth. You lose instantly if the number you've shouted coincide with the rank of the card you've just drawn. What is the probability of winning/losing the game (whichever is easier to compute)?

**Additional information: The problem is related to the first-encounter probability of two walks (one deterministic and one random): a deterministic walk jumping to the right by one lattice site at each time-step, and resetting after 13 steps, and another walk randomly jumping among the same thirteen sites (with the constraint that no site can be visited more than four times).

Answer 1

This is the so-called "Frustration solitaire". This is a good reference: article by Doyle, Grinstead and Snell. The probability of winning is about $1/e^4\approx 0.0183$ where $4$ is related to the number of suits. That is about $2$%, this game is really frustrating!!

P.S. As pointed out by Michael Lugo below, at page 8 of the linked article we can find the exact winning probability for a 52-card deck which is about $0.0162$. Even for $n=13$, the asymptotic probability $1/e^4\approx 0.0183$ gives a reasonable estimation of the exact probability.

Answer 2

An exact solution is possible with the method of rook polynomials and a computer algebra system. Rook Polynomial

First, it helps to reformulate the problem a little to make the solution by rook polynomials easier to visualize. So let's suppose that before shuffling, the deck is in the order ace of diamonds, ace of clubs, ace of hearts, ace of spades, ace of diamonds, 2 of clubs, 2 of hearts, 2 of spades, 2 of diamonds, etc., and let's suppose that the instead of shouting out "one, two, three, ..." , the player shouts out "one, one, one, one, two, two, two, two, ...". Since the deck is shuffled randomly, this revision does not affect the probability of winning. With this formulation, the player wins if there is no ace in cards 1-4 in the shuffled deck and no 2 in cards 5-8 and no 3 in cards 9-12, etc. Since the shuffled deck may consist of any of the $52!$ possible permutations of the original order, all of which we assume are equally likely, we would like to count the permutations which result in a win.

To use the method of rook polynomials, we view a permutation of the cards as equivalent to placing 52 non-attacking rooks on a 52 by 52 board, i.e. with exactly one rook in each row and column. The winning permutations correspond to a placement of the rooks on the board below avoiding the gray squares. For reasons of space we have shown only the first twelve rows and columns,but please imagine the pattern extending into a 52 by 52 board.

...plus 40 more rows and columns (unshown).

The rook polynomial of the 4 by 4 grey square in the upper left hand corner is $$R_4(x) = 1+16x+72x^2+96x^3+26x^4$$ (See the Wikipedia page linked above.) What this means is that there are $16$ ways to place one rook on the area, $72$ ways to place two non-attacking rooks, $96$ ways to place three non-attacking rooks, and $26$ ways to place four non-attacking rooks.

The rook polynomial of the restricted area on the 52 by 52 board, consisting of 13 such 4 by 4 squares, is then $$R_{52}(x) = R_4(x)^{13} = r_0 + r_1x +r_2x^2 +r_3x^3+ \dots + r_{52}x^{52}$$ where the coefficients $r_0, r_1, r_2, r_3, \dots , r_{52}$ are not listed but can be calculated explicitly by expanding $R_4(x)^{13}$. This would be very tedious to do by hand, but it's easy with a computer algebra system. (I used Mathematica.) By the principle of inclusion/exclusion, the number of ways to place 52 non-attacking rooks on the non-excluded area of the board is $$N = \sum_{i=0}^{52} (-1)^i (52-i)! \;r_i$$ The result, calculated by Mathematica, is $$N = 1309307359844999263426548962125482317263708526033413008220015566848$$ so the probability of winning the game is $$\frac{N}{52!} = 0.0162328$$