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.

  • $\begingroup$ Thanks! I am totally impressed with the high level of thinking on this forum. Bravo! $\endgroup$ 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.

  • $\begingroup$ This, too, is a plausible and nice approximation. $\endgroup$ May 4 '11 at 19:19
  • $\begingroup$ From some simulations, I get ~ 0.0455 , which (curiously) is half between my approximation and Michael Lugo's. $\endgroup$
    – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.