# A combinatorial card problem

Suppose you have a standard bridge deck of 52 cards. We will say you "have a pair" if you have two consecutive cards in the deck with the same rank (2,3,4,5,6,7,8,9,10,J,Q,K,A). If a deck is randomly shuffled, what is the probability you have a pair in the deck?

I have been able to estimate this nicely using a simulation, but finding an analytical solution remains elusive.

-

Below I explain how to enumerate all decks without bad pairs explicitly. The exact number turns out to be $$3668033946384704437729512814619767610579526911188666362431432294400.$$ Dividing by $52!$, I get roughly $$0.045476282331.$$

We are going to write a recurrence relation for $f(H,k)$, which is the number of partial decks with $t$ cards appearing $H_t$ times, the last card making its $k$th appearance. The total number of decks is then $f((0,0,0,0,13),4)$.

The base case is $f((12,1,0,0,0),1) = 52$. Now suppose we're given some $H$ and $k$ such that $H_k \geq 1$. First form $H'$ by moving one "rank" from $k$ to $k-1$. Now for each $t \neq k - 1$, we can extend each of the $f(H_k,t)$ partial decks to a new deck in $H_k(k-1) \cdot (4-(k-1))$ ways. For $t = k-1$, we can extend the $f(H_k,k-1)$ partial decks in only $(H_k(k-1)-1) \cdot (4-(k-1))$ ways (since one rank is taken).

There are only 9481 pairs $H,k$ to consider, so even my lousy python implementation which uses a hash table to keep track of all those pairs is fast enough.

Michael Lugo's method gives $(1-3/51)^{51} \approx 0.0454176$, which is quite close to the right answer. The correct probability is slightly larger since if we imagine a process in which cards are revealed one by one, the probability that the next card is bad starts at $3/51$ but eventually decreases (roughly).

His approximation $e^{-3} \approx 0.049787$ is much too big, and that's because $(1-3/n)^n$ approaches $e^{-3}$ from below.

leonbloy's approximation is also too small, for similar reasons. We can imagine a process in which ranks are revealed one by one. After the first rank is revealed, a smaller number of positions are adjacent, and so the probability decreases.

-
+1 nice (not trivial) recursion . perfect – leonbloy May 5 '11 at 2:49
Thanks! I am totally impressed with the high level of thinking on this forum. Bravo! – ncmathsadist May 5 '11 at 18:15

Lets compute the probability that a particular rank is not paired. This is like placing 4 balls in 52 cells so that there are no consecutive occupied cells. The total number of placings (considering here the balls as undistinguishable) is clearly

${52 \choose 4} = {{48 + 4} \choose 4}$

Notice that this must be equal to the number of ways of choosing five nonnegative integers $\{a_0 a_1 a_2 a_3 a_4\}$ so that they sum 48. (This comes by the interpretation of $a_i$ as the number of empty cells between ocuppied cells.)

Now, the number of arrangements with no pairings is similar to the above, with the restriction that ${a_1 a_2 a_3}$ must be greater than zero. But this is the same as choosing nonnegative integers $\{a_0 b_1 b_2 b_3 a_4\}$ ($b_i=a_i-1)$ so that they sum 48-3=45. Then, by the above argument, this must be

${45 + 4 \choose 4} = {49 \choose 4}$

So the probability that a given rank (say, K) does not form a pair is the ratio of that numbers, which gives $\approx 0.7826$.

Now, we could introduce the aproximation that the probability that no rank is paired is the product. This gives

$P \approx 0.7826^{13} \approx 0.0413$

This assumes independence, which is not justified, but I feel it should be a decent approximation. I also feel that the real probability should be a little higher, because knowing that -say- rank Q is not paired tells me that there is more probability that rank -say- K is also not paired.

-
This, too, is a plausible and nice approximation. – ncmathsadist May 4 '11 at 19:19
From some simulations, I get ~ 0.0455 , which (curiously) is half between my approximation and Michael Lugo's. – leonbloy May 4 '11 at 20:02

It's easy to find the expected number of pairs. The probability that the $k$th card and the $k+1$st card make a pair is $3/51$ -- once we know what card $k$ is, there are three possible cards $k+1$ that can be that make a pair. There are 51 possible sites for a pair, so the expected number of pairs is 3.

Now, if I had to guess, I'd say the distribution of the number of pairs is approximately Poisson. Let $A_k$ denote the event that card $k$ and card $k+1$ have the same rank. Then $A_k$ and $A_l$ are "approximately independent" for most choices of $k$ and $l$.

So without doing any simulation, I'd guess that the probability of having no pairs is near $e^{-3}$ and the probability of having at least one pair is therefore near $1-e^{-3}$. I'd be interested to know if this agrees with your simulation.

-
I ran some sims in Python. For 100000 trials I got 95053, 95103 and 95212 pairs. So your approximate argument seems quite good. – ncmathsadist May 4 '11 at 18:27