A card game almost nobody wins

Nobody gets their own hat opened the subject with the oldest problem in it: hand back $n$ hats at random, and the chance that nobody gets their own tends to $1/e$, about 37 per cent. Pierre Rémond de Montmort put it as a card game in 1708, turning over a deck of cards while counting, and losing on a match. How many get their own hat followed the number of matches and found it settling into a Poisson law of mean one.

A real deck has four suits, and the game with a real deck is played as follows. Shuffle the 52 cards. Deal them one at a time, face up, calling “ace, two, three, …, queen, king” with each card and starting again at ace after each king, four times round. If the card turned is ever the rank being called, the game is lost. Getting through the deck is a win. The game is called frustration solitaire, and the name is accurate.

This essay computes the chance of winning exactly, and the computation is the one the cells a permutation must miss built: a board of forbidden cells, its rook numbers, and an alternating sum.

The obvious guess and what it misses #

The expected number of matches is easy. Each of the 52 positions calls a rank, and the card there has that rank with chance $4/52 = 1/13$; adding over positions gives $52/13 = 4$ matches on average, exactly. If the matches behaved like the hats, scattered and nearly independent, their number would be close to a Poisson law of mean four, and the chance of none would be close to $e^{-4} = 0.0183$.

The figure shows the exact law beside that guess, and they are close but not the same. The chance of no match is 1.6233 per cent rather than 1.8316. The exact law is a little narrower than the Poisson: fewer deals with no matches, fewer with ten or more, slightly more with three, four or five. The guess is off by eleven per cent at exactly the number the game is about.

The reason is the suits. In the hat problem each person has one hat and each hat one owner, so a match at one place barely affects a match anywhere else. Here the four cards of each rank compete for the four places where that rank is called. If the king of hearts lands on a “king” call, there are three kings left for the three remaining king calls, which slightly lowers the chance of more king matches; and if no king lands on a king call, the other three are a little more likely to. The matches of one rank are bunched into a small system of four cards and four places, and inside each system they repel one another. Repulsion is what makes a count less spread out than Poisson, and it is why zero is rarer than $e^{-4}$.

Thirteen squares of forbidden cells #

To count exactly, draw the problem as a board. List the 52 positions down the side, sorted by the rank called there, and the 52 cards across the top, sorted by rank. A deal is a way of putting one card in each position — a permutation, a placement of 52 non-attacking rooks on the full board — and a match is a rook on a cell where the card’s rank equals the call. Those forbidden cells form thirteen 4 × 4 squares down the diagonal, one for each rank, and the squares share no row and no column.

That separation is what makes the count easy. Inclusion–exclusion needs the rook numbers $r_k$ of the forbidden cells: the number of ways to put $k$ rooks on forbidden cells with no two in a line, which is the number of ways to choose $k$ matches that could happen together. In one 4 × 4 square, $k$ rooks can be placed in $\binom{4}{k}^2 k!$ ways — choose the rows, choose the columns, match them up — giving 1, 16, 72, 96 and 24. And because the squares share no lines, a placement on the whole board is an independent choice in each square, so the rook numbers of the board are the coefficients of

$$\left(1 + 16x + 72x^2 + 96x^3 + 24x^4\right)^{13}.$$

That is the multiplication rule from the cells a permutation must miss, used here at full scale: 208 ways to choose one match, 20,904 to choose two, 1,352,416 to choose three, up to $24^{13}$ ways to choose all 52.

The whole method on four cards #

The method is easiest to trust on a deck small enough to check by hand. Take two ranks in two suits — two aces and two twos — and call “ace, two, ace, two”. The forbidden board is two 2 × 2 squares, each with rook numbers 1, 4, 2 (no rook, four single cells, two ways to place two rooks), so the board’s rook numbers are the coefficients of $(1 + 4x + 2x^2)^2 = 1 + 8x + 20x^2 + 16x^3 + 4x^4$.

Treating the four cards as distinct, there are $4! = 24$ deals, and the alternating sum gives

$$24 - 8 \cdot 3! + 20 \cdot 2! - 16 \cdot 1! + 4 \cdot 0! = 24 - 48 + 40 - 16 + 4 = 4$$

deals with no match. Directly: no match means both aces sit on the two “two” calls and both twos on the two “ace” calls, which can be done in $2! \times 2! = 4$ ways. The chance is $4/24 = 1/6$, against the Poisson guess $e^{-2} \approx 0.135$ — here the exact answer is the larger, because with so few cards the four-card deck is far from the regime the Poisson law describes, and the sign of the error is not fixed until the deck is large enough for the second-order picture above to hold.

The full deck is the same calculation with thirteen squares of four instead of two squares of two: the middle terms reach ten rather than two, and the cancellation runs over fifty-three terms rather than five.

The sum that cancels #

With the rook numbers, the chance of no match is the alternating sum

$$P(\text{win}) = \sum_{k=0}^{52} (-1)^k\, r_k\, \frac{(52 - k)!}{52!}.$$

The $k$-th term counts, over every set of $k$ compatible matches, the deals that make at least those matches — the remaining $52 - k$ cards can go anywhere — and the signs correct the overcounting, exactly as in the sum stopped early.

The terms are not small. They start at 1 and 4, rise to 7.9, 10.2 and 9.7 for two, three and four matches, and only then fall, below 1 at nine and below a thousandth at thirteen. So the answer, about a sixtieth, is what is left when numbers ten times larger than one cancel. The running sum in the figure swings above and below while the terms are large and settles only once they are small. Computed in floating point, a sum like this loses digits to cancellation; computed in whole numbers — the rook numbers and factorials are exact integers, and the division happens once at the end — it loses nothing. The figures do it that way, and the result is

$$P(\text{win}) = 0.016232727467\ldots,$$

about one deal in 61.6. Peter Doyle, Charles Grinstead and Laurie Snell computed this value in their 1995 account of the game, and the figure’s exact integer arithmetic agrees with it.

The same arithmetic gives the whole distribution of matches in the hero figure. The number of deals with exactly $j$ matches is a second alternating sum, $\sum_k (-1)^{k-j} \binom{k}{j} r_k (52 - k)!$, and the figure checks that the 53 counts add to $52!$ and that their mean is exactly four.

Measuring the repulsion #

The repulsion inside each rank can be measured exactly, and the measurement says how large the error in the Poisson guess should be. A Poisson count has its variance equal to its mean. The number of matches in frustration solitaire has mean 4 and variance

$$\frac{64}{17} \approx 3.765,$$

which the figures compute from the exact distribution. The shortfall from 4 is the repulsion, summed.

It comes from pairs of matches. Two calls of the same rank, say the first and second “king”, can both be matched only by two different kings, and the chance of that is $\frac{4}{52} \cdot \frac{3}{51}$, a little less than $\left(\frac{4}{52}\right)^2$: matches of one rank are negatively correlated. Two calls of different ranks are matched by cards of different ranks, and those are very slightly positively correlated, because a king used up on a king call is a card not available to spoil a queen call. Adding all the pairs, the negative correlations within ranks outweigh the positive ones between them, and the variance falls short of the mean by $4/17$.

A count with less spread than Poisson is less likely to be zero, and that is the eleven per cent. The connection can be made precise. To second order, the logarithm of the chance of no match is $-\lambda$ plus half the difference between the variance and the mean; here that is $-4 - 2/17$, so the chance is $e^{-4}$ times $e^{-2/17} \approx 0.889$, against the exact ratio of $0.886$. The Poisson guess is therefore not merely wrong but wrong in a predictable direction, and the size of its error is set by a single exact number, the variance.

A Laguerre polynomial in disguise #

There is a second formula, and it explains why the sum has the shape it has. The factorial in each term can be written as an integral, $(52 - k)! = \int_0^\infty x^{52-k} e^{-x}\,dx$. Putting that into the alternating sum and collecting the powers of $x$ square by square turns it into

$$P(\text{win}) = \frac{1}{52!} \int_0^\infty e^{-x} \left(x^4 - 16x^3 + 72x^2 - 96x + 24\right)^{13} dx.$$

The polynomial inside is $4!$ times the Laguerre polynomial $L_4(x)$, a member of the family of polynomials that are orthogonal against the weight $e^{-x}$ — the same weight that appears in the integral a series that converges nowhere studied. Shimon Even and Joseph Gillis noticed in 1976 that problems of this kind always reduce to integrals of products of Laguerre polynomials: a deck of $m$ ranks in $d$ suits gives $\int e^{-x} (d!\,L_d(x))^m dx$, and a deck with suits of unequal sizes gives a product of different Laguerre polynomials.

The integral form also makes the structure of the deck visible in the formula. Each rank contributes one factor, and the factor depends only on how many cards that rank has; the order of the calls, the number of ranks and the sizes of the suits all enter only through which Laguerre polynomials are multiplied and how many times. A deck with a joker, or with one rank missing a card, changes one factor and nothing else. The sum over rook numbers says the same thing more slowly, since the rook polynomial of the board is a product over ranks, but the integral turns that product into something that can be estimated as a whole, and the asymptotic statements in the next section come from estimating it.

More ranks, more suits #

The computation runs as easily for any deck. With one suit it is the hat problem, and the chance of no match is within a hair of $1/e$ from five ranks on. With $d$ suits and $m$ ranks the expected number of matches is still $d$, and as the number of ranks grows the chance of none tends to $e^{-d}$ — but from below and slowly, because the repulsion inside each rank’s $d \times d$ square does not go away as ranks are added; it only becomes one small effect among many.

At thirteen ranks and four suits the real deck is still eleven per cent short of $e^{-4}$. At sixty ranks it is two and a half per cent short. The convergence is like $1/m$, since each rank contributes a correction of about that relative size, and a deck would need hundreds of ranks before the Poisson guess was good to the first decimal place of a percentage.

That is the same lesson the round table with no couple together drew for the ménage problem: a limit taken from the independence heuristic is right in the limit and wrong at every size anybody plays at, and only the exact count says by how much.

Two hundred thousand deals #

A computation this long deserves a check that shares nothing with it. The figure shuffles a deck two hundred thousand times with a seeded generator and plays every deal. The share won settles at 0.01654, 1.1 standard errors from the exact 0.016233, and the Poisson value $e^{-4}$ lies outside the two-standard-error band from about twenty thousand deals on.

That is the scale at which the difference between the exact answer and the heuristic becomes visible in play: a few tens of thousands of games, which a machine plays in a fraction of a second and a person in a lifetime of frustration.

A game with no decisions #

Frustration solitaire has no choices in it. Once the deck is shuffled the outcome is fixed, and the player’s part is to turn cards and call ranks, so the game is a lottery with odds of about one in sixty-two, dressed as a game. That is what makes it a good object for inclusion–exclusion: the whole of the game is a single question about a random permutation with forbidden positions, and the answer is one number.

The rest of the distribution is worth reading for what it says about how the game feels. The commonest outcomes are three and four matches, each in about a fifth of deals; a deal with exactly one match — a near miss — comes up in 6.9 per cent of deals, four times as often as a win; and fewer than one deal in a hundred has ten or more. Since the game ends at the first match, a player never sees how many matches the deal would have had, only how early the first one came, and with an average of four spread over 52 cards the first match usually arrives within the first dozen or so.

None of that changes the winning chance, which depends only on whether the count is zero. But it is the reason the game earns its name: most deals end early, many end late, and a win is rare enough that a person playing by hand will usually go dozens of games between them.

What the computation rests on #

The rook numbers are exact products of polynomials with whole-number coefficients, and the winning count is an exact integer — the number of the $52!$ deals with no match — divided once by $52!$ at the end. The distribution of matches is checked to account for every deal and to have mean exactly four, and the winning chance for one suit is checked against the hat problem’s $1/e$. The simulation is independent of all of it: it shuffles and deals rather than counting, and agrees within its sampling error.

Still open: how much the order of the calls matters #

The calls in frustration solitaire run in a fixed cycle, but the exact count above does not depend on that: any calling order that names each rank four times gives the same board up to rearranging rows, and so the same chance. What changes the answer is the deck. A deck in which ranks have different numbers of cards, or in which some calls are of ranks with no cards, gives a board of unequal rectangles, and the count is again an integral of a product of Laguerre polynomials, one for each block.

The open questions are about variants that break the block structure. If a match is forbidden not only on the rank called but on the ranks either side of it, the forbidden cells overlap from rank to rank and the board no longer splits into squares. The rook polynomial then has no product formula, the count becomes a permanent of a banded matrix, and while transfer methods compute it for decks of real size, how its value behaves as the band widens and the deck grows — and how far it sits from the Poisson guess — has no closed answer of the kind the square blocks give.