2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this question not possible to solve using mathematics or is it just very difficult? I am not sure how to set this up mathematically but I did try some decks manually and I got 4 decks out of 20 that had this repeat property so it appears it is close to 20% but I am not sure how accurate that is cuz it was only 20 decks. The average card position where this happened was 34 but again, I don't think 20 decks is enough to call that accurate. Maybe this can be solved by computing the probability of no repeat exact triple and then taking the complement? $\endgroup$ – David Sep 30 '18 at 20:43
  • $\begingroup$ I think it is a very tedious question to get an exact answer for. There are many cases and sorting them out is a lot of work. It would be easy to program a statistical trial to do millions of cases. Some people have code that would make writing that easy, but not me. $\endgroup$ – Ross Millikan Oct 1 '18 at 18:10
  • $\begingroup$ I ran a simulation of 100 million decks and the maximum # of overlapping triple sequences that were previously seen in the deck was only 7. Therefore, a mathematical solution that considers this should be close enough to the correct answer to be acceptable. Any deck with more than 7 overlapping triple sequences is so rare that we can basically ignore them. $\endgroup$ – David Oct 3 '18 at 10:02
  • $\begingroup$ If the first four cards are 2's, have "the ranks of 3 adjacent cards have already been seen"? (Because 222 appeared twice?) $\endgroup$ – irchans Oct 3 '18 at 20:43
  • $\begingroup$ @irchans, no I am not counting adjacent quads as overlapping matching triples. This visually and conceptually complicates things some. My code simply checks the last 3 cards drawn (starting from the 6th card) with all previous 3 adjacent card triples (but not extending into the last 3 cards drawn). I am not sure mathematically if that makes it easier or harder to compute. It seems you can ignore adjacent quads cuz they do not count as a matching triple cuz the triple we are trying to match canNOT match part of itself, it MUST be previously seen in the drawn cards, $\endgroup$ – David Oct 4 '18 at 1:27
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I wrote a simulation program to check this, scanning 10 million decks in about 1 hour of computer runtime, and I got 20.32%. That same simulation program is telling me that on average, the first match (for those decks that have at least 1 match), is happening at drawn card # 36 (out of 52) so it takes a little more than 2/3rds of the deck to complete the match on average, but it can be interpreted as a little less (33 cards) since the first 3 cards are required before a match is even possible. 6 cards drawn is the minimum to create a match. 52 is the maximum for a match. $\endgroup$ – David Oct 2 '18 at 0:39
  • 1
    $\begingroup$ As $p$ increases in power, each successive term declines in significance. $\endgroup$ – Doug M Oct 3 '18 at 21:23
  • 1
    $\begingroup$ Doug, when you applied Inclusion-Exclusion you made an independence assumption. Let A be the event that the first three cards have the same rank sequence as cards 4,5, and 6. Let B be the event that cards 8, 9, and 10 have the same rank sequence as cards 14,15, and 16. Obviously, P(A)=P(B). But how do you know that P(B|A) = P(B) (i.e. how do you know A is independent of B) ? $\endgroup$ – irchans Oct 3 '18 at 21:26
  • 1
    $\begingroup$ @David: It sounds like your code, if it starts at cards $(4,5,6)$, will not catch all the cases where two identical triples overlap. For example, if the first four cards are all kings, then the triples at $(1,2,3)$ and at $(2,3,4)$ are the same. Also, DougM, you seem to be ignoring the possibility of overlaps altogether. $\endgroup$ – mjqxxxx Oct 3 '18 at 21:35
  • 1
    $\begingroup$ @irchans Yes, I am aware of that... that is why I said that I was taking a short cut. Also way I didn't take the inclusion exclusion to its exhaustion. I haven't had the time to investigate the problem more closely. $\endgroup$ – Doug M Oct 3 '18 at 22:20
1
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is really good analysis as the letter patterns help visually identify the repeating triples. I am happy that your simulation results match mine exactly at 20.32%. Of course this is counting any deck with at least 1 matching triple as a match, and even if that deck has up to 7 matches (the highest I have seen in my simulation of 100 million decks), that still counts the same as if the deck had only 1 match. So overall, it appears that 1 out of every 5 decks will have at least one triple repeated of this type (rank and order are the same). I will simulate 1 billion decks soon. $\endgroup$ – David Oct 4 '18 at 15:58
  • $\begingroup$ By the way, since I got 7 matched triples max in my simulation of 100 million decks and I doubt there will be more than 8 matched triples even when I simulate 1 billion decks, I think it is fair to say that using inclusion-exclusion principle, it will suffice to handle up to 8 matched triples but no more. That answer should be within a tiny epsilon of the actual answer which is close enough. Probability need not be exact in this case since we are only trying to get a feel for the likelihood, not trying to use it like at a casino to make money. It is very interesting analysis going on here. $\endgroup$ – David Oct 4 '18 at 16:03
  • $\begingroup$ Regarding your comment on the uncertainty in the last digit of our matching 20.32% (0.2032), I will run a simulation of 1 billion decks and I think it is fair to say that should give us good confidence to 4 decimal places (0.2032 for example). I should have the answer by maybe Sat morning and will post it here. I am more interested in the analysis so in the future, I can maybe try to solve similar type problems. In fact, I may concoct another similar one to see if I can solve it and then I can write a simulation program the check it. $\endgroup$ – David Oct 4 '18 at 16:36
  • $\begingroup$ One "problem" I see with using math to solve a problem like this is that all of the patterns need be identified, whereas with simulation, as soon as the first match is found, we can ignore the rest of the deck and immediately shuffle a new deck. This obviously eliminates any overcounting since we stop looking after the first match, although I can easily make the simulation so it counts all of the matching triples, even multiple per deck. $\endgroup$ – David Oct 4 '18 at 17:23
  • $\begingroup$ Absolutely... writing a simulation to get an approximate answer is easy (10 lines of Python code, easily verified to be correct, runs $10^6$ samples in 30 seconds), and you can run it longer to improve the approximation. But every time you want another digit, you need to run it $100$ times longer. So run it on a cluster, or otherwise scale up?... computer power is cheap, and human analysis is expensive and potentially error-prone, so up to a certain point simulation is the best way to go. ... $\endgroup$ – mjqxxxx Oct 5 '18 at 13:20
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you ran $10^9$ and you got $N=203233000$ hits, then the error in the mean is something like $\pm \sqrt{N} / 10^9 = \pm 1.4 \times 10^{-5}$, right? So you can say $20.323\% \pm 0.002\%$. $\endgroup$ – mjqxxxx Oct 7 '18 at 17:22

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.