Deck of 52 cards, 3 card rank/order repeat pattern probability.

Question

A standard deck of 52 playing cards is well shuffled and drawn 1 card at a time without replacement. What is the probability that the ranks of the 3 most recently drawn cards (starting at drawn card 6) have already been seen in the exact same order in the already drawn cards? For example, when the 6th card is drawn, we need to check if cards 4, 5, and 6 are the same exact ranks as cards 1, 2, and 3 in the same exact order. If not, then we draw card 7 and check if cards 5, 6, and 7 have been seen in that same order in cards 1, 2, 3 or 2, 3,and 4... So basically we are checking the last 3 cards drawn against all previously drawn triples, including overlapping triples (such as cards 2,3,4 that overlap cards 1,2,3)

So for example, using A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K as the 13 possible card ranks, the following partial deck would be a pattern found scenario:

5, Q, 7, 3, K, K, 8, Q, 7, 3 because the Q, 7, 3 triple was previously seen in that exact order.

$UPDATE$: For clarification, you need not scan into the last 3 cards drawn for a match. When I said overlapping triples I did not mean into the last 3 cards drawn, but rather overlapping triples such as scanning cards 1,2,3 then 2,3,4, then 3,4,5... from the last 3 cards drawn (start scanning after card 6 is drawn and after every other drawn card after that such as 7, 8,... 51, 52).

So my question is what is the probability this will happen at least once in a well shuffled deck? That is, at least one triple pattern of ranks will repeat exactly in order in the same deck as the cards are drawn one at a time, as described above.

Answer 1

Any 3 card sequence can be: No pair, one pair, 3 of a kind.

With probabilities $\frac{52\cdot48\cdot 44}{52\cdot 51\cdot 50}, \frac{52\cdot3\cdot 48\cdot 3}{52\cdot 51\cdot 50}, \frac{52\cdot3\cdot 2}{52\cdot 51\cdot 50}$ respectively.

Verify that these sum up to 1.

If the sequence is no pair. There is a probability that a given 3 card sequence in the deck matches rank for rank is:

$\frac {3\cdot 3\cdot 3}{49\cdot 48\cdot 47}$

If a sequence has one pair, it is less likely.

$\frac {2\cdot 1\cdot 3}{49\cdot 48\cdot 47}$

If a sequence is 3 of a kind, it is impossible to have a second sequence that matches the first.

That two sequences of 3 cards match

$\frac {52\cdot 48\cdot 44\cdot 27+52\cdot 3\cdot 48\cdot 3\cdot 6}{52\cdot 51\cdot 50\cdot 49\cdot 48\cdot 47}$

How many non-overlapping pairs sequences of 3 cards are there in a 52 card deck? ${48\choose 2}$

How to explain this? If we think of the first sequence of sequence $A$ and the second sequence as sequence $B.$

We can burn some amount of cards before the beginning sequence $A$, and some amount of cards after the end of sequence $B$ lets call these $a,b$ respectively. The sum of the cards burnt must be less than or equal to 46.

The number of pairs of non-negative integers such that $a + b \le 46$ is ${48\choose 2}$

(remember $a,b$ could equal $0.$)

$\frac {52\cdot 48\cdot 44\cdot 27+52\cdot 3\cdot 48\cdot 3\cdot 6}{52\cdot 51\cdot 50\cdot 49\cdot 48\cdot 47}\cdot {48\choose 2} \approx 23.8\%$

Update....

As has been pointed out by the original poster, I have the expected number of duplicated sequences...

Inclusion-Exclusion

Taking a shortcut....

$p = \frac {52\cdot 48\cdot 44\cdot 27+52\cdot 3\cdot 48\cdot 3\cdot 6}{52\cdot 51\cdot 50\cdot 49\cdot 48\cdot 47}$

$p{48\choose 2} - p^2{48\choose 2}{42\choose 2} + p^3{48\choose 2}{42\choose 2}{43\choose 2} \approx 20.34\%$ which is $0.2034$.

Answer 2

The main factor preventing this problem from having a simple closed-form answer is the possibility of $3$, $4$, or even more non-overlapping rank-triple repeats. So we need to count carefully and correct for over-counting using the inclusion-exclusion principle.

I'm going to list patterns that a deck could match in order to have repeated rank-triples. The simplest is $$ *\;ABC*ABC\;* $$ where $*$ indicates zero or more cards and each letter is a different rank. There are $13\cdot12\cdot 11 = 1716$ ways to select $ABC$, and $(4\cdot 3)^3=1728$ ways to choose the suits of the two rank-triples, and $\frac{1}{2}(47\cdot 48) = 1128$ ways to place the two rank-triples within the remaining $46$ cards, so the probability is $$ \frac{1716\cdot 1728 \cdot 1128}{52\cdot 51 \cdot 50 \cdot 49 \cdot 48 \cdot 47} \approx 0.2281873. $$ It's also possible to have one of $$ *\;ABA*ABA* \qquad *\;AAB*AAB* \qquad *\;BAA*BAA\;*. $$ For each of these there are $13\cdot 12=156$ ways to select $A$ and $B$, and $4!\cdot 4 \cdot 3=288$ to choose the suits, and again $\frac{1}{2}(47\cdot 48)=1128$ ways to place the two rank-triples within the remaining $46$ cards, so the probability is $$ \frac{3\cdot 156 \cdot 288 \cdot 1128}{52\cdot 51 \cdot 50 \cdot 49 \cdot 48 \cdot 47} \approx 0.0103721. $$ These are the only cases with a single repeated rank-triple, and summing them gives $p_1\approx 0.238559$. Now we need to subtract the patterns for two repeated rank-triples, add the patterns for three repeated rank-triples, subtract the patterns for four, etc. These events are increasingly unlikely, and we have no hope of enumerating all of them by hand; but we can try to capture the largest contributions. The most likely pattern with two repeated rank-triples is $$ *\;ABC*ABC*DEF*DEF\;* $$ Here there are $13\cdot12\cdot11\cdot10\cdot9\cdot8=1235520$ ways to choose the ranks, $(4\cdot 3)^6=2985984$ ways to choose the suits, and $\frac{1}{8}(41\cdot 42\cdot 43 \cdot 44)=407253$ ways to place the four blocks among the remaining $40$ cards (such that $ABC$ comes before $DEF$), for a total probability of $$ \frac{1235520\cdot 2985984 \cdot 407253}{52\cdot 51\cdot 50\cdots 42 \cdot 41}\approx 0.0151984. $$ The next-most dominant contributor is $$ *\;ABCD*ABCD\;* $$ with $13\cdot12\cdot11\cdot10=17160$ ways to select $ABCD$, and $(4\cdot 3)^4=20736$ ways to choose the suits, and $\frac{1}{2}(45\cdot 46)=1035$ ways to place the blocks, for a probability of $$ \frac{17160\cdot 20736\cdot 1035}{52\cdot 51\cdot 50\cdot 49\cdot48\cdot 47\cdot46\cdot 45}\approx 0.0121376. $$ Next is $$ *\;ABA*CDE*ABA*CDE\;* $$ together with its variants with $AAB$ or $BAA$ and the permutations of the four blocks. There are $13\cdot 12\cdot 11\cdot 10\cdot 9=154440$ ways to choose $ABCDE$, and $4!\cdot(4\cdot 3)^4=497664$ ways to choose the suits, and $\frac{1}{4}(41\cdot 42\cdot 43 \cdot 44)=814506$ ways to place the four blocks among the remaining $40$ cards, so the probability here is $$ \frac{3\cdot 154440 \cdot 497664 \cdot 814506}{52\cdot 51\cdot 50\cdots 42 \cdot 41} \approx 0.0018998. $$ There are more patterns for two repeated rank-triples, but these are the most common; summing them gives $p_2\approx 0.029236$. We estimate that $$ p = p_1 - p_2 + p_3 - p_4 + \ldots \approx 0.238559 - 0.029236 = 0.209323. $$ This estimate is a bit high... my simulation also yields $p = 0.2032$, with the uncertainty in the last digit. It turns out that there are a good many additional patterns to account for even for just two repeated rank-triples, each of which is unlikely, but which together account for the discrepancy. A partial list is the following: $$ *\;ABC*ABCDE*CDE\;* $$ $$ *\;ABC*ABCD*BCD\;* $$ $$ *\;ABC*DEA*DEABC\;* $$ $$ *\;ABC*DAB*DABC\;* $$ $$ *\;ABCABCA\;* $$ $$ *\;ABC*ABC*DCE*DCE\;* \ldots $$

---

Update:

I've systematized my diagrammatic calculation and can report on the results. Starting with the first pattern ($*\;ABC*ABC\;*$), at each step I generate all new patterns (modulo permutations of the blocks and left-right reversal) that can be reached by adding a single extra constraint. I calculate the exact probability of each pattern and place new patterns in a priority queue, with the highest-probability pattern at the front of the queue. Then iterate, at each step popping the next pattern from the queue, generating all its children, and inserting any new children back into the queue.

The procedure is complicated, but I've been able to check its results when applied to simpler cases for which exact enumeration is possible: decks with only 2, 3, or 4 ranks (and still 4 suits). In these cases the diagrammatic calculation terminates, giving the following answers, which can be verified to be exactly correct:

• 2 ranks (4 diagrams): 24 of 70 shuffles (34.2857%) have rank-triple repeats
• 3 ranks (1786 diagrams): 14802 of 34650 shuffles (42.7186%) have rank-triple repeats
• 4 ranks (109307 diagrams): 25754256 of 63063000 shuffles (40.8389%) have rank-triple repeats

Running this algorithm on the actual problem, with $13$ ranks, yields an estimate of $20.316\%$ in just a few minutes, having considered only the top $56$ diagrams. I'll run it overnight and see if I can arrive at a better estimate.

Answer 3

Since this problem seems very difficult to count all the patterns without overcounting, I just ran a Monte Carlo type simulation of 1 billion 1 ($10^9 + 1$) random decks, stopping at the first match in the deck and counting them up. It took more than 24 hours to complete but I just let it run on my desktop computer while I used my laptop computer to do other things like chat...

The results I got are $20.32330$% of the decks have this property.

So I am not sure what the confidence level is from this (assuming the program and random generator are correct) but I would at least feel pretty confident about $20.323$%.

I know this solution is not mathematical, but it is still useful for checking against mathematical solutions, thus helping confirm them.

In the future what I would like to do is to store the randomly generated decks in a disk file so then later I could rerun it looking for different criteria such as a quad repeating pattern instead of a triple. Since generating the shuffled decks is the bulk of the computer time, once I do that, I can just "quickly" read it back in (a reasonable "chunk" at a time) and check for the desired patterns.