Probability of Two Consecutive Same-Value Cards in a Shuffled Deck

[murshid_islam]

Homework Statement

What is the probability that at least 2 cards of the same value will be next to each other in a pack of cards?

Relevant Equations

I don't have one yet

Not really a homework question. I was reading a book on card tricks and it said that it's almost certain that in a shuffled deck of cards, there will be at least two consecutive cards of the same value. I just wanted to know the actual probability of that. So, here's my question: in a standard deck of 52 cards, what is the probability that at least 2 cards of the same value will be next to each other? Now I get it that I need to calculate the probability that no two consecutive cards have the same value, and then subtract that from 1. But I am stuck.

This is what I did: I simulated 5 million shuffles in Python, and at least 2 consecutive cards had the same value in 95.45% of those 5 million trials. I'd still like to know the closed form of the probability. Here's my Python code in case anyone wants to check it out.

Mentor note: code from link above added to post

from random import shuffle
 
values = ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']
cards = 4 * values  # create 52 cards (only the 52 values are required; suits are irrelevant and not needed)
trials = 5_000_000
desired_outcome = 0
 
for _ in range (trials):
    shuffle(cards)  # shuffle the cards using random.shuffle()
    for i in range (51):
        if cards[i] == cards[i+1]:
            desired_outcome += 1
            break
 
print(f'Desired Outcome = {desired_outcome :,} times = {desired_outcome*100/trials :.2f}%')

 

[PeroK]

What about counting the number of ways for smaller numbers of face values and trying to spot an inductive relationship?

E.g first with only aces and twos, then aces, twos and threes etc.

You could write a program to count the ways for these smaller numbers.

 

[murshid_islam]

What about counting the number of ways for smaller numbers of face values and trying to spot an inductive relationship?

E.g first with only aces and twos, then aces, twos and threes etc.

You could write a program to count the ways for these smaller numbers.

You mean trying with 8 cards, then 12, then 16 and so on to see if I can find a pattern?

 

[PeroK]

You mean trying with 8 cards, then 12, then 16 and so on to see if I can find a pattern?

Yes. In fact you could simply adapt the program you have as the number of ways can be calculated from the probability obtained from a large number of trials.

 

[FactChecker]

I have to admit that I do not see a slick way to do this analytically, but then I am not the sharpest knife in the drawer.

 

[FactChecker]

Homework Statement:: What is the probability that at least 2 cards of the same value will be next to each other in a pack of cards?
Relevant Equations:: I don't have one yet

Not really a homework question. I was reading a book on card tricks and it said that it's almost certain that in a shuffled deck of cards, there will be at least two consecutive cards of the same value. I just wanted to know the actual probability of that. So, here's my question: in a standard deck of 52 cards, what is the probability that at least 2 cards of the same value will be next to each other? Now I get it that I need to calculate the probability that no two consecutive cards have the same value, and then subtract that from 1. But I am stuck.

This is what I did: I simulated 5 million shuffles in Python, and at least 2 consecutive cards had the same value in 95.45% of those 5 million trials. I'd still like to know the closed form of the probability. Here's my Python code in case anyone wants to check it out.

It looks like Python has some nice features for this type of simulation.

 

[PeroK]

You mean trying with 8 cards, then 12, then 16 and so on to see if I can find a pattern?

I found the sequence for effectively two suits on OEIS:

https://oeis.org/search?q=2,30,864&sort=&language=english&go=Search

I think the probabilistic estimate is not going to be good enough to pin down the integer number of arrangements (even for a few face values and only two suits) . You may need to write a program that goes through all arrangements and counts explicitly.

It'll be interesting to see whether the sequence for four suits is in OEIS ...

 

[murshid_islam]

You mean trying with 8 cards, then 12, then 16 and so on to see if I can find a pattern?

Yes. In fact you could simply adapt the program you have as the number of ways can be calculated from the probability obtained from a large number of trials.

For 8 cards (e.g., 4 Aces and 4 twos) where no two consecutive cards have the same value,

• the 1st card can be chosen in 8 different ways.
• the 2nd card cannot be the same value as the 1st card. So, the 2nd card can be chosen in 4 different ways
• the 3rd card can be chosen in 3 different ways (among the 3 remaining cards of the same value as the 1st card)
• the 4th card can also be chosen in 3 different ways (among the 3 remaining cards of the same value as the 2nd card)
• the 5th card can be chosen in 2 different ways (among the 2 remaining cards of the same value as the 1st card)
• the 6th card can be chosen in 2 different ways (among the 2 remaining cards of the same value as the 2nd card)
• the 7th and 8th cards can be chosen in only 1 way.

So, the number of different ways 8 cards can be arranged where no two cards of the same value are next to each other = 8*4*3*3*2*2 = 1152

That is also the result I got from my Python code:

from itertools import permutations

cards="AAAA2222"
cnt = 0
for p in permutations(cards):
    s = ''.join(p)
    if ('AA' not in s) and ('22' not in s):
        cnt += 1
print(cnt)

However, the calculations got super messy for 12 cards. But I tried it with this Python code:

from itertools import permutations

cards = 4*"A23"
cnt = 0
for p in permutations(cards):
    s = ''.join(p)
    if ('AA' not in s) and ('22' not in s) and ('33' in s):
        cnt += 1

print(cnt)

This gave me the result = 25,961,472 and it took almost 3 minutes to calculate that.

 

[PeroK]

You are treating the four Aces separately, which is going to be too inefficient. You need to look for permutations where the Aces etc are identical.

You can do the calculation for 8 cards as follows:

There are $\binom 8 4 = 70$ ways of placing the aces. The twos go wherever.

There are only two successful combinations.

For 12 cards:

There are $\binom {12} 4$ ways of placing the aces, and for each of these $\binom 8 4$ ways of placing the twos. That gives $34,650$ total permutations. The number of successful ones is about $1,090$. But, you need to find a way to count that precisely, rather than estimate from a large sample.

That gives a simple iteration for the total number of permutations for $4$ suits and $v$ values:
$$N(v, 4) = \binom v 4 N(v-1, 4)$$The tricky part now is to list these (or otherwise) count the number of successful ones.

One idea is to place the four aces, then place the four twos etc. Then check the resulting permutation. Or, you could be clever and keep them separate as you go along (more efficient).

You could do it with a fixed number of nested iterations or, for arbitrary $v$ you'll need a recursive algorithm.

For $v = 4$ there are already $60$ million possible permutations, so that might be the limit of what you could do checking every one. For $v = 5$ there are $3 \times 10^{11}$, which is probably too many.

The simple thing would be to write a program to count successful permutations for $v =2$ then adapt it for $v = 3$ and $v = 4$. You'll have to treat the Aces etc as identical.

Those are my thoughts.

 

[PeroK]

That said, the numbers are getting large too quickly for four suits. I'd try with two suits first and see whether a pattern emerges. Then perhaps three suits. Then try to guess the pattern for four suits.

 

[PeroK]

PS One trick is to start every permutation with $A2$ and then multiply the result by $v(v-1)$

 

[pbuk]

With 52 cards there are 51 pairings. For each pairing the chance that the second card does not match the first is $\frac{48}{51}$. The probability that at least one pairing matches is therefore $1- \left ( \frac{48}{51} \right ) ^ {51} \approx 95.46 \%$.

 

[PeroK]

With 52 cards there are 51 pairings. For each pairing the chance that the second card does not match the first is $\frac{48}{51}$. The probability that at least one pairing matches is therefore $1- \left ( \frac{48}{51} \right ) ^ {51} \approx 95.46 \%$.

The probabilities for each pair are not independent. That formula can't be right. It doesn't work for small numbers of cards. It's interesting, however, that for a large number of cards the assumption of independence gives such a good approximation.

 

[pbuk]

The probabilities for each pair are not independent.

Yes, I decided to ignore that , I was farily confident that 4 x 13 cards was enough that

for a large number of cards the assumption of independence gives such a good approximation.

 

[murshid_islam]

The probabilities for each pair are not independent.

Why aren't they independent?

 

[PeroK]

Why aren't they independent?

If you have four cards, two aces and two twos, then whether the third and fourth pairs are the same depends on whether the first pair were the same.

In this case, the correct calculation that the pairs are all different is:
$$p = \frac 2 3 \times \frac 1 2 = \frac 1 3$$Whereas, @pbuk 's calculation would give:
$$p = \big ( \frac 2 3)^3 = \frac 8 {27}$$As the number of cards increases, the pairs become approximately independent. Or, at least, the effect of non-independence averages itself out to the same result as independence.

It's still an interesting counting and programming exercise for small numbers of cards.

 

[murshid_islam]

There are $\binom {12} 4$ ways of placing the aces, and for each of these $\binom 8 4$ ways of placing the twos. That gives $34,650$ total permutations. The number of successful ones is about $1,090$. But, you need to find a way to count that precisely, rather than estimate from a large sample.

How did you get that 1090?

 

[PeroK]

How did you get that 1090?

That was an estimate based on sampling. I've got a program to count them now and it's 1092.

 

[murshid_islam]

That was an estimate based on sampling. I've got a program to count them now and it's 1092.

Yes, I got 1092 as well.

 

[PeroK]

Yes, I got 1092 as well.

Okay, I've got a rough and ready program to do the counting. I've done this up to four face "values" and up to four "suits". "Combos" are the total number of combinations, "success" are those with no adjacent pairs, the "check" probability is based on a large sample and "Pbuk" is an estimate calculated using independence of pairs as $\big ( \frac {c-s}{c-1} \big )^{c-1}$, where $s$ is the number of suits and $c$ is the number of cards.

My program needs a bit of work to generalise it further. The sequences for three and four suits are on OEIS:

https://oeis.org/A114938

https://oeis.org/A321633

Values	Suits	Cards	Combos	Success	Prob	Check	Pbuk
2​	2​	4​	6​	2​	0.3333​	0.3329​	0.2963​
3​	2​	6​	90​	30​	0.3333​	0.3331​	0.3277​
4​	2​	8​	2,520​	864​	0.3429​	0.3422​	0.3399​
2​	3​	6​	20​	2​	0.1000​	0.1000​	0.0778​
3​	3​	9​	1,680​	174​	0.1036​	0.1035​	0.1001​
4​	3​	12​	369,600​	41,304​	0.1118​	0.1120​	0.1100​
2​	4​	8​	70​	2​	0.0286​	0.0285​	0.0199​
3​	4​	12​	34,650​	1,092​	0.0315​	0.0315​	0.0301​
4​	4​	16​	63,063,000​	2,265,024​	0.0359​	0.0360​	0.0352​

 

[PeroK]

PS note that a quicker way to do the counting is to ensure that the numbers $1$ to $n$ appear in order. This is a generalisation of my idea above. Suppose we have a solution for $1, 2, 3, 4$ repeated twice (two suits). Every solution is a permutation of a solution where $1,2,3,4$ appear in that order. I.e. every sequence must start $1, 2$ and then $3$ must be the next that isn't $1$ or $2$. You can count these and then multiply by $4!$.

For $v = 4$ that should mean the program taking about 24 times less time to run.

 

[PeroK]

Here's my first cut code. It needs to be rewritten as a recursive procedure. But, it was easier just to cut and paste to start with! It takes about 24 seconds.

import itertools
#
# Program for 4 face values (1-4) and s suits
#
s = 4
rem_places = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
#
hc = 0 # successful hand count
#
# Check that no consecutive places have been chosen for a given face value:
#
def check_places(places_in):
    places_sorted = sorted(places_in)
    places_okay = True
    for i in range(0, len(places_sorted)-1):
        if places_sorted[i] + 1 == places_sorted[i+1]:
            places_okay = False
            return places_okay
#
    return places_okay
#
# Place the first face value in any valid places:
#
for places_1 in itertools.combinations(rem_places, s):
    places_1_okay = check_places(places_1)
    if not places_1_okay:
        continue
#
    rem_places_1 = rem_places.copy()
    for place_1 in places_1:
        rem_places_1.remove(place_1)
#
# Place the second face value in any valid places:
#
    for places_2 in itertools.combinations(rem_places_1, s):
       
        places_2_okay = check_places(places_2)
        if not places_2_okay:
            continue
#
        rem_places_2 = rem_places_1.copy()      
        for place_2 in places_2:  
            rem_places_2.remove(place_2)
#
        for places_3 in itertools.combinations(rem_places_2, s):
            places_3_okay = check_places(places_3)
            if not places_3_okay:
                continue
#
            rem_places_3 = rem_places_2.copy()
            for place_3 in places_3:
                rem_places_3.remove(place_3)
#
            for places_4 in itertools.combinations(rem_places_3, s):
                places_4_okay = check_places(places_4)
                if not places_4_okay:
                    continue
#
                hc += 1
#
print(hc)

 

[pbuk]

It takes about 24 seconds.

Given the size of the numbers here I think there must be a more efficient algorithm.

 

[PeroK]

Given the size of the numbers here I think there must be a more efficient algorithm.

My recursive program can do four values and four suits in 1.5s. That means finding about $100,000$ solutions and multiplying by $4!$ to get the $2.2$ million solutions. But, for five values and four suits there are about $12 \times 10^9$ solutions, which equates to finding about $100$ million and multiplying by $5!$.

So, yes, something cleverer is needed to go further. The answer is to use the recurrence relation given in OEIS.

 

[PeroK]

... 20 minutes later I get 11,804,626,080 for five values and four suits.

Even though I can calculate these numbers, it's staggering that there are so many solutions with only four suits and 10, J, Q, K, A. There are 300 billion ways to arrange them, 12 billion of which have no adjacent cards of equal face value. And that doesn't take into account the different suits!

It's just amazing, really.

 

[Prof B]

I found the answer here. Can anyone explain it?

 

[Prof B]

I found a python program on stackexchange that uses dynamic programming to calculate the probability that no consecutive cards have the same suit. It could be modified to handle ranks instead of suits, but I found a really impressive solution for ranks on AskMeta. You have to scroll past a few pages of fails to get to it. Search for DevilsAdvocate at 1:26 PM on November 17, 2006.

 

[pbuk]

I found a really impressive solution for ranks on AskMeta. You have to scroll past a few pages of fails to get to it. Search for DevilsAdvocate at 1:26 PM on November 17, 2006.

Great method although as it involves individual analysis of 7,263 states which is not published there is no guarantee the presented result is correct. 1 - 0.045476282 = 95.4523718% is pretty close to my approximation of 95.4582...% in #12 above though.

 

[PeroK]

The idea by Devil's Advocate can simply be turned into a programme. Here's my pseudo-code for the algorithm to calculate the total probability that the cards are successfully arranged.

Initialise our variables, assuming the first card has been placed:

We have a list $a(i)$ of five elements for the number of ranks with $i$ cards remaining:

$a = [0, 0, 0, 1, 12]$

$nr = 51$ (number of remaining cards)

$li = 3$ (last-i: the number of cards remaining for the last rank selected)

$p_{tot} = 0$ (Global variable to hold the total probability of all successful configurations)

$p = 1$ (Running probability for the current configuration)

Excecute the recursive procedure to select the next card:

Execute Next_Config($a$, $nr$, $li$, $p$)

Output of the program is $p_{tot}$

Recursive Procedure

Next_config($a$, $nr$, $li$, $p$)

First check for the case where no further progress is possible:

If $li = nr$ then return (failure to complete the configuration)

Check for successful config:

If $nr = 1$ and $li = 0$
then: add $p$ to $p_{tot}$ and return

Otherwise, proceed to next configuration:

For $i = 1$ to $4$:

If $a(i) = 0$ then next $i$ (no cards to chhose from)

If $i = li$ and $a(i) = 1$ then next $i$ (no valid cards to choose from - only same as last time)

Calculate the probability of choosing a valid card (i.e. not the same as the last one)

If $i = li$ then $p_{out} = p \times (\frac{i[a(i) - 1]}{nr})$ (probability of choosing a valid card)

If $i \ne li$ then $p_{out} = p\times (\frac{i[a(i)]}{nr})$ (proabability of choosing a valid card)

Set remaining output variables for next config:

$nr_{out} = nr - 1$

$li_{out} = i - 1$

$a_{out} = a$, except:

$a_{out}(i) = a(i) - 1$

$a_{out}(i-1) = a(i-1) + 1$

Execute Next_Config($a_{out}$, $nr_{out}$, $li_{out}$, $p_{out}$)

 

[PeroK]

I'll see whether I can implement the above in Python.

PS although I just realized that there are probably too many branches. I was hoping that I'd have a manageable number!

 

[Office_Shredder]

Given that there are no matches in the first 51 draws, what is the probability the last two match? Might be a helpful step for solving analytically. This doesn't seem easy to me.

 

[PeroK]

I have written a program based on the above idea to maintain the probability of each valid configuration. I.e. starting from $(0,0,0,0,13)$ the only valid configuration for 51 cards remaining is $(0,0,0,1,12); 3$ (probability $1$). And the only valid configuration for 50 cards remaining is $(0,0,0,2,11); 3$. This means that we have 2 face values with 3 cards remaining, 11 with four cards remaining; and the last card in the sequence has 3 cards of the same value remaing. The next step (49 cards remaining produces two configs):
$(0,0,1,1,11);2$ and $(0,0,0,3,10); 3$.

The key point is that the total number of valid configurations is limited to about 7,000. Although the number of valid paths exponentiates with the number of cards. By consolidating the number of valid configurations and their associated probabilities at each step, the processing is minimised. The following code only takes about 1 second to execute:

################################################################################################################
## Program to calculate the probability that in a shuffled deck of cards there are no adjacent cards with     ##
## the same face value.  The number of suits is hardcoded, but the number of face values can vary (< 100)     ##
## The idea that as each card is chosen we have a configuration that can be represented as follows:           ##
## a = ([a_0, a_1, a_2, a_3, a_4], last_i)                                                                    ##
## where a_i is the number of face values for which i cards remain; and last_i relates to the last card. E.g. ##
## a = ([1,4,1,6,1],1) indicates that there is 1 face value with 4 cards remaining; 6 with 3 remaining etc.;  ##
## and the last card in the sequence is one of the 4 with 1 card remaining.  We can also see that for this    ##
## configuration we have 24 cards in the sequence and 28 cards remaining.                                     ## 
## We also maintain the probability of achieving each configuration.                                          ##
## From this configuration we can generate valid configurations for 27 cards remaining.  E.g. we can choose   ##
## one of four cards (with probability 4/28) to achieve ([1,4,1,7,0],3).  Or, one of 18 cards to achieve      ##
## ([1,4,2,5,1], 2). Note that there are only 3 cards that we can choose to achieve ([2,3,1,6,1]) as one of   ##
## 4 singletons was the last card chosen, which we must avoid.                                                ## 
## Starting with ([0,0,0,0,13],0) (probability 1) we can proceed to generate all valid configurations after   ##
## each card, ending with the final configuration ([13,0,0,0,0],0) and the final probability of success.      ##
## Note that the variable a_0 is redundant and is not actually maintained in this program.                    ##
##                                                                                                            ##
## For ease of processing, the configurations are coded and decoded using base 100:                           ##
## code_a = last_i + 100*a[1] + (100^2)*a[2] ... (100^4)*a[4]                                                 ##
##                                                                                                            ##
## The critical reason that the program runs quickly is that there are relatively few valid configurations.   ##
## At each step duplicate configurations are combined and their probabilities added.  Otherwise, the number   ##
## of valid paths exponentiates.                                                                              ##
################################################################################################################
#
def code_config(a, last_i):
    code_a = last_i + (100*a[1]) + ((100**2)*a[2])+((100**3)*a[3])+((100**4)*a[4])
    return code_a
#
def decode_config(code_a):
    last_i_out = int(code_a % 100)
    #
    a_out = [0,0,0,0,0]
#
    code_temp = (code_a - last_i_out)/100
#    print(code_temp)
#
    for i in range(1,5):
        a_out[i] = int(code_temp % 100)
        code_temp = (code_temp - a_out[i])/100
#
    return(a_out, last_i_out)
#
# Procedure to decode and print configs (for interest and debugging)
#
def print_configs(configs, probs):
    for k in range(0,len(configs)):
        (a, last_i) = decode_config(configs[k])
        print(configs[k], a, last_i, probs[k])
#
###################################################################################################################
# Main recursive procedure to generate the next set of valid configurations and merge those that are the same.    #
###################################################################################################################
def next_configs(configs, probs, nr):
#
# When there are no cards remaining, we have the probability for the final configuration.
#
    if nr == 0:
        print(f"Probability = {probs[0]}")
        return
#
    configs_out = []
    probs_out = []
    nr_out = nr - 1
#
    for k in range(0,len(configs)):
        (a_temp, last_i_temp) = decode_config(configs[k])
        p_temp = probs[k]
#
        for i in range(1, 5):
            if a_temp[i] == 0:
                continue
#
            if i == last_i_temp and a_temp[i] ==1:
                continue
#
# Generate new probabilities for the next valid configurations
#
            if i == last_i_temp:
                p_out = p_temp*(i*(a_temp[i] -1))/nr
            else:
                p_out = p_temp*i*a_temp[i]/nr
#
# Generate and code next valid configurations
#
            last_i_out = i - 1
            a_out = [0,0,0,0,0]

            for n in range(0,5):
                if n == i:
                     a_out[n] = a_temp[n] -1
                elif n == i -1:
                    a_out[n] = a_temp[n] + 1
                else:
                    a_out[n] = a_temp[n]
#
            code_out = code_config(a_out, last_i_out)
#
# Check whether valid configuration already exists (and only add the probability if it does)
#
            code_found = False
#
            for m in range(0, len(configs_out)):
                if code_out == configs_out[m]:
                    code_found = True
                    probs_out[m] += p_out
                    break
#
            if not code_found:
                configs_out.append(code_out)
                probs_out.append(p_out)
#
    print_configs(configs_out, probs_out)
#
    next_configs(configs_out, probs_out, nr_out)
#
nr = 52
a = [0, 0, 0, 0, 13]
last_i = 0
#
code_a = code_config(a, last_i)
configs = [code_a]
probs = [1]
#
next_configs(configs, probs, nr)